Summary
The problem of scheduling in permutation flowshops is considered with the objectives of minimizing the makespan and total flowtime of jobs. A multi-objective ant-colony algorithm (MOACA) is proposed. The salient features of the proposed multi-objective ant-colony algorithm include the consideration of two ants (corresponding to the number of objectives considered) that make use of the same pheromone values in a given iteration; use of a compromise objective function that incorporates a heuristic solution’s makespan and total flowtime of jobs as well as an up per bound on the makespan and an upper bound on total flowtime of jobs, coupled with weights that vary uniformly in the range [0, 1]; increase in pheromone intensity of trails by reckoning with the best solution with respect to the compromise objective function; and updating of pheromone trail intensities being done only when the ant-sequence’s compromise objective function value is within a dynamically updated threshold level with respect to the best-known compromise objective function value obtained in the search process. In addition, every generated ant sequence is subjected to a concatenation of improvement schemes that act as local search schemes so that the resultant compromise objective function is improved upon. A sequence generated in the course of the ant-search process is con sidered for updating the set of heuristically non-dominated solutions. We consider the benchmark flowshop scheduling problems proposed by Taillard (1993), and solve them by using twenty variants of the MOACA. These variants of the MOACA are obtained by varying the values of parameters in the MOACA and also by changing the concatenation of improvement schemes. In order to benchmark the proposed MOACA, we rely on two recent research reports: one by Minella et al. (2008) that re ported an extensive computational evaluation of more than twenty existing multi-objective algorithms available up to 2007; and a study by Framinan and Leisten (2007) involving a multi-objective iterated greedy search algorithm, called MOIGS, for flowshop scheduling. The work by Minella concluded that the multi-objective simulated annealing algorithm by Varadharajan and Rajendran (2005), called MOSA, is the best performing multi-objective algorithm for permutation flowshop scheduling. Framinan and Leisten found that their MOIGS performed better than the MOSA in terms of generating more heuristically non-dominated solutions. They also obtained a set of heuristically non-dominated solutions for every benchmark problem instance provided by Taillard (1993) by consolidating the solutions obtained by them and the solutions reported by Varadharajan and Rajendran. This set of heuristically non-dominated solutions (for every problem instance, up to 100 jobs, of Taillard’s benchmark flowshop scheduling problems) forms the reference or benchmark for the present study. By considering this set of heuristically non-dominated solutions with the solutions given by the twenty variants of the MOACA, we form the net heuristically non-dominated solutions. It is found that most of the non-dominated solutions on the net non-dominated front are yielded by the variants of the MOACA, and that in most problem instances (especially in problem instances exceeding 20 jobs), the variants of the MOACA con tribute more solutions to the net non-dominated front than the corresponding solutions evolved as benchmark solutions by Framinan and Leisten, thereby proving the effectiveness of the MOACA. We also pro vide the complete set of heuristically non-dominated solutions for the ninety problem instances of Taillard (by consolidating the solutions obtained by us and the solutions obtained by Framinan and Leisten) so that researchers can use them as benchmarks for such research attempts.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Problem Instance
- Flow Shop
- Flowshop Schedule Problem
- Multiobjective Genetic Algorithm
- Local Search Scheme
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allahverdi, A.: A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness. Computers & Operations Research 31, 157–180 (2004)
Allahverdi, A., Aldowaisan, T.: New heuristics to minimize total completion time in m-machine flowshops. International Journal of Production Economics 77, 71–83 (2002)
Armentano, V.A., Arroyo, J.E.C.: An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem. Journal of Heuristics 10, 463–481 (2004)
Arroyo, J.E.C., Armentano, V.A.: Genetic local search for multi-objective flowshop scheduling problems. European Journal of Operational Research 167, 717–738 (2005)
Bagchi, T.P.: Multiobjective scheduling by genetic algorithms. Kluwer Academic Publishers, Boston (1999)
Ben-Daya, M., Al-Fawzan, M.: A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research 109, 88–95 (1998)
Campbell, H.G., Dudek, R.A., Smith, M.L.: A heuristic algorithm for the n-job, m-machine sequencing problem. Management Science 16, B630–B637 (1970)
Chakravarthy, K., Rajendran, C.: A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization. Production Planning and Control 10, 707–714 (1999)
Chang, P.-C., Hsieh, J.-C., Lin, S.G.: The development of gradual priority weighting approach for the multi-objective flowshop scheduling problem. International Journal of Production Economics 79, 171–183 (2002)
Chung, C.-S., Flynn, J., Kirca, O.: A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems. International Journal of Production Economics 79, 185–196 (2002)
Corne, D.W., Knowles, J.D., Oates, M.J.: The pareto envelope-based selection algorithm for multiobjective optimization. In: Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Guervos, J.J.M., Schwefel, H.P. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 839–848. Springer, Heidelberg (2000)
Corne, D.W., Jerram, N.R., Knowles, J.D., Oates, M.J.: PESA-II: Region-based selection in evolutionary multiobjective optimization. In: Spector, L., Goodman, E.D., Wu, A., Langdon, W.B., Voigt, H.M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M.H., Burke, E. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 283–290. Morgan Kaufmann, San Francisco (2001)
Daniels, R.L., Chambers, R.J.: Multiobjective flow-shop scheduling. Naval Research Logistics 37, 981–995 (1990)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 182–197 (2002)
Dong, X., Huang, H., Chen, P.: An improved NEH-based heuristic for the permutation flowshop problem. Computers & Operations Research 35, 3962–3968 (2008)
Dorigo, M.: Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy (1992)
Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics – Part B 26, 29–41 (1996)
Framinan, J.M., Leisten, R.: An efficient constructive heuristic for flowtime minimisation in permutation flow shops. OMEGA 31, 311–317 (2003)
Framinan, J.M., Leisten, R.: A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness. International Journal of Production Economics 99, 28–40 (2006)
Framinan, J.M., Leisten, R.: A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria. OR Spectrum, published online before print, August 4 (2007)
Framinan, J.M., Leisten, R., Ruiz-Usano, R.: Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation. European Journal of Operational Research 141, 559–569 (2002)
Framinan, J.M., Ruiz-Usano, R., Leisten, R.: Comparison of heuristics for flowtime minimisation in permutation flowshops. Computers & Operations Research 32, 1237–1254 (2005)
Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1, 117–129 (1976)
Geiger, M.J.: On operators and search space topology in multi-objective flow shop scheduling. European Journal of Operational Research 181, 195–206 (2007)
Gelders, L.F., Sambandam, N.: Four simple heuristics for scheduling a flow-shop. International Journal of Production Research 16, 221–231 (1978)
Ho, J.C.: Flowshop sequencing with mean flow time objective. European Journal of Operational Research 81, 571–578 (1995)
Ignall, E., Schrage, L.: Application of the branch-and-bound technique to some flowshop scheduling problems. Operations Research 13, 400–412 (1965)
Ishibuchi, H., Murata, T.: A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Sys¬tems, Man and Cybernetics – Part C: Applications and Reviews 28, 392–403 (1998)
Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1, 61–68 (1954)
Kalczynski, P.J., Kamburowski, J.: On the NEH heuristic for minimizing the makespan in permutation flow shops. OMEGA 35, 53–60 (2007)
Kalczynski, P.J., Kamburowski, J.: An improved NEH heuristic to minimize makespan in permutation flow shops. Computers & Operations Research 35, 3001–3008 (2008)
Laha, D., Chakraborty, U.K.: A constructive heuristic for minimizing makespan in no-wait flow shop scheduling. International Journal of Advanced Manufacturing Technology (2008) (DOI: 10.1007/s00170-008-1454-0)
Liao, C.-J., Tseng, C.-T., Luarn, P.: A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research 34, 3099–3111 (2007)
Liu, J., Reeves, C.R.: Constructive and composite heuristic solutions to the P//∑C i scheduling problem. European Journal of Operational Research 132, 439–452 (2001)
Merkle, D., Middendorf, M.: An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Oates, M.J., Lanzi, P.L., Li, Y., Cagnoni, S., Corne, D.W., Fogarty, T.C., Poli, R., Smith, G.D. (eds.) EvoIASP 2000, EvoWorkshops 2000, EvoFlight 2000, EvoSCONDI 2000, EvoSTIM 2000, EvoTEL 2000, and EvoROB/EvoRobot 2000. LNCS, vol. 1803, pp. 287–296. Springer, Heidelberg (2000)
Minella, G., Ruiz, R., Ciavotta, M.: A review and evaluation of multi-objective algorithms for the flowshop scheduling problem. INFORMS Journal on Computing published online before print, April 2 (2008)
Miyazaki, S., Nishiyama, N.: Analysis for minimizing weighted mean flowtime in flowshop scheduling. Journal of the Operations Research Society of Japan 23, 118–132 (1980)
Miyazaki, S., Nishiyama, N., Hashimoto, F.: An adjacent pairwise approach to the mean flowtime scheduling problem. Journal of Operations Research Society of Japan 21, 287–299 (1978)
Murata, T., Ishibuchi, H., Tanaka, H.: Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering 30, 957–968 (1996)
Nawaz, M., Enscore Jr., E.E., Ham, I.: A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. OMEGA 11, 91–95 (1983)
Pasupathy, T., Rajendran, C., Suresh, R.K.: A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. International Journal of Advanced Manufacturing Technology 27, 804–815 (2006)
Rajendran, C.: Two-stage flowshop scheduling problem with bicriteria. Journal of the Operational Research Society 43, 871–884 (1992)
Rajendran, C.: Heuristic algorithm for scheduling in a flowshop to minimize total flowtime. International Journal of Production Economics 29, 65–73 (1993)
Rajendran, C.: A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria. International Journal of Production Research 32, 2541–2558 (1994)
Rajendran, C.: Heuristics for scheduling in flowshop with multiple objectives. European Journal of Operational Research 82, 540–555 (1995)
Rajendran, C., Ziegler, H.: Ant-colony algorithms for permutation flowshop scheduling to minimize makespan / total flowtime of jobs. European Journal of Operational Research 155, 426–438 (2004)
Rajendran, C., Ziegler, H.: Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Computers & Industrial Engineering 48, 789–797 (2005)
Ruiz, R., Stuetzle, T.: A simple and iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research 177, 2033–2049 (2007)
Ruiz, R., Maroto, C., Alcaraz, J.: Two new robust genetic algorithms for the flowshop scheduling problem. OMEGA 34, 461–476 (2006)
Sridhar, J., Rajendran, C.: Scheduling in flowshop and cellular manufacturing systems with multiple objectives – a genetic algorithmic approach. Production Planning & Control 7, 374–382 (1996)
Srinivas, N., Deb, K.: Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation 2, 221–248 (1994)
Stuetzle, T.: An ant approach to the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT 1998), Verlag Mainz, Aachen, pp. 1560–1564 (1998)
Taillard, E.: Benchmarks for basic scheduling problems. European Journal of Operational Research 64, 278–285 (1993)
Tasgetiren, M.F., Liang, Y.-C., Sevkli, M., Gencyilmaz, G.: A particle-swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research 177, 1930–1947 (2007)
T′kindt, V., Billaut, J.-C.: Multicriteria scheduling: Theory, models and algorithms. Springer, Berlin (2002)
T′kindt, V., Monmarche, N., Tercinet, F., Lauegt, D.: An ant colony optimization algorithm to solve a two-machine bicriteria flowshop scheduling problem. European Journal of Operational Research 142, 250–257 (2002)
Varadharajan, T.K., Rajendran, C.: A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. European Journal of Operational Research 167, 772–795 (2005)
Widmer, M., Hertz, A.: A new heuristic method for the flowshop sequencing problem. European Journal of Operational Research 41, 186–193 (1989)
Wang, C., Chu, C., Proth, J.-M.: Heuristic approaches for n/m/F/∑C i scheduling roblems. European Journal of Operational Research 96, 636–644 (1997)
Woo, H.S., Yim, D.S.: A heuristic algorithm for mean flowtime objective in flowshop scheduling. Computers and Operations Research 25, 175–182 (1998)
Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation 3, 257–271 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Rajendran, C., Ziegler, H. (2009). A Multi-Objective Ant-Colony Algorithm for Permutation Flowshop Scheduling to Minimize the Makespan and Total Flowtime of Jobs. In: Chakraborty, U.K. (eds) Computational Intelligence in Flow Shop and Job Shop Scheduling. Studies in Computational Intelligence, vol 230. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02836-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-02836-6_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02835-9
Online ISBN: 978-3-642-02836-6
eBook Packages: EngineeringEngineering (R0)