An Efficient Ant Colony Optimization Algorithm for Multiobjective Flow Shop Scheduling Problem

Authors: Ahmad Rabanimotlagh

Abstract:

In this paper an ant colony optimization algorithm is developed to solve the permutation flow shop scheduling problem. In the permutation flow shop scheduling problem which has been vastly studied in the literature, there are a set of m machines and a set of n jobs. All the jobs are processed on all the machines and the sequence of jobs being processed is the same on all the machines. Here this problem is optimized considering two criteria, makespan and total flow time. Then the results are compared with the ones obtained by previously developed algorithms. Finally it is visible that our proposed approach performs best among all other algorithms in the literature.

Keywords: Scheduling, Flow shop, Ant colony optimization, Makespan, Flow time

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077155

References:

[1] S. M. Johnson.Optimal two- and three-stage production schedules with setup times included,Naval Research Logistics Quarterly,Vol. 1, pp 61- 68, 1954.
[2] M. RGarey, D. S. Johnson, RSethi. The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research,vol. 1, pp.117-129, 1976.
[3] JBlazewicz, EPesch, MSterna, FWerner. Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date, Computers & Operations Research,vol. 35, no. 2, pp. 574-599, 2008.
[4] G.LZobolas, C.DTarantilis, GLoannou. Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm, Computers & Operations Research,Vol.36, no. 4, pp. 1249- 1267, 2009.
[5] X Li, M. FBaki, Y. PAneja. Flow shop scheduling to minimize the total completion time with a permanently present operator: Models and ant colony optimization metaheuristic Original Research Article, Computers & Operations Research,vol. 38, no. 1, pp. 152-164, 2011. A. C Andreas, CNearchou. A novel metaheuristic approach for the flow shop scheduling problem. Engineering Applications of Artificial Intelligence, vol. 17, no. 3, pp. 289-300, 2004.
[6] NSalmasi, RLogendran, M. R. Skandari. Total flow time minimization in a flowshop sequence-dependent group scheduling problem, Computers & Operations Research,vol. 37, no. 1, pp. 199-212, 2010.
[7] D. G. Dannenbring. An evaluation of flowshop sequencing heuristics. Management Science,vol. 23, no. 11, pp. 1174-1182, 1977.
[8] K. C. Ying, and C. J. Liao, Ant colony system for permutation flowshop sequencing, Computers & Operations Research,vol. 31, no. 5, pp. 791-801, 2004
[9] RRuiz, CMaroto, JAlcaraz. Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics, European Journal of Operational Research,vol. 165, no. 1, pp. 34-54, 2005
[10] AJaniak, EKozan, MLichtenstein, CO─ƒuz, Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion, International Journal of Production Economics,vol. 105, no. 2, pp. 407- 424, 2007.
[11] ENowicki, CSmutnicki. A fast tabu search algorithm for the permutation flow-shop problem, European Journal of Operational Research,vol. 91, no. 1, pp. 160-175, 1997.
[12] V. R. Neppalli, C. L. Chen, J. N. D.Gupta. Genetic algorithms for the two stage bicriteriaflowshop problem. European Journal of Operational Research,vol. 95, no. 2, pp. 356-373, 1996.
[13] J. M. Wilson. Alternative formulations of a flowshop scheduling problem, Journal of Operations Research Society,vol. 40, no. 4, pp. 395-399, 1989.
[14] Nagar A, Haddock, J, Heragu S. S. A branch-and-bound approach for a two-machine flowshop scheduling problem. Journal of the Operational Research Society,vol. 46, no. 6, pp. 721-734, 1995.
[15] W. C. Yeh. A memetic algorithm for the n/2/flow shop/╬▒F+βC_max scheduling problem. The International Journal of Advanced Manufacturing Technology,vol. 20. No. 6, pp. 464-473, 2002.
[16] CRajendran. Heuristics for scheduling in flowshop with multiple objectives. European Journal of Operational Research,vol. 82, pp. 540- 555, 1995.
[17] J. M. Framinan,RLeisten, RRuiz-Usano. Efficient heuristics for flowshop sequencing with objectives of makespan and flowtime minimization. European Journal of Operational Research, vol. 141, pp. 561-571, 1996.
[18] DRavindran, ANoorulHaq, S. J. Selvakuar, RSivaraman. Flow shop scheduling with multiple objective of minimizing makespan and total flow time. International Journal of Advanced Manufacturing Technology,vol. 25, pp. 1007-1012, 2005.
[19] BYagmahan, M. M. Yenisey. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications,vol. 37, pp. 1361-1368, 2010.
[20] J. C. Ho, Y. L. Chang. A new heuristic for the n-job, m-machine flow shop problem. European Journal of Operational Research,vol. 52, pp. 194-202, 1991.
[21] C. Rajendran. A heuristic algorithm for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria. International Journal of Production Research,vol. 32, pp. 2541-2558, 1994.
[22] C. Sridhar, C. Rajendran. Scheduling in flowshop and cellular manufacturing systems with multiple objectives: A genetic algorithmic approach. Production Planning and Control,vol. 7, pp. 374-382, 1996.
[23] B. Yagmahan, M. Yenisey. M. Ant colony optimization for multiobjective flow shop scheduling problem. Computers & Industrial Engineering,vol. 54, pp. 411-420, 2008.
[24] M. Pinedo. Scheduling: theory, algorithms and systems. 2nd ed, Englewood Cliffs, NJ: Prentice-Hall; 2002.
[25] M. Dorigo,V. Maniezzo, A. Colorni. Positive feedback as a search strategy,Technical report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1991.
[26] M. Dorigo. Optimization, Learning and Natural Algorithms
[in Italian]. PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1992.
[27] B. Bullnheimer,R. F.Hartl,C. Strauss. A new rank-based version of the Ant System: A computational study. Central European Journal for Operations Research and Economics,vol. 7, no. 1, pp. 25-38, 1999.
[28] T. Stutzle, H. H. Hoos. The MAX-MIN Ant System and local search for the traveling salesman problem. In T. Back, Z. Michalewicz, & X. Yao (Eds.), Proceedings of the 1997 IEEE International Conference on Evolutionary Computation (ICEC-97) (pp. 309-314), Piscataway, NJ, IEEE Press.
[29] M. Dorigo, L. M. Gambardella. Ant colonies for the traveling salesman problem. BioSystems,vol. 43, no. 2, pp. 73-81, 1997.
[30] M. Widmer, A. Hertz. A new heuristic method for the flowshop sequencing problem. European Journal of Operational Research,vol. 41, pp. 186-193, 1989.
[31] M. Dorigo, T. Stutzle. Ant colony optimization, Massachusetts Institute of Technology,2004, pp. 31-32.
[32] www.lifl.fr/~liefooga/benchmarks/benchmarks/index.html.