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

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.

Authors:

• Ahmad Rabanimotlagh

Keywords:

• Scheduling
• Flow shop
• Ant colony optimization
• Makespan
• Flow time

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.