×

An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. (English) Zbl 1082.90592

Summary: Consider the 2-machine flowshop scheduling problem with the objective of minimizing both the total completion time and the makespan criteria. The latter is assumed to be optimized prior to the former. In view of the NP-hardness of the problem an Ant Colony Optimization approach is proposed to solve it. The heuristic also uses feature of Simulated Annealing search and local search algorithms. Computational experiments show its effectiveness compared to existing heuristics. The extension to the total completion time problem is also studied.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C.-L. Chen, R.L. Bulfin, Complexity of multiple machines, multicriteria scheduling problems, in: Third Industrial Engineering Research Conference (IERC’94), Atlanta (USA), 1994, pp. 662 -665; C.-L. Chen, R.L. Bulfin, Complexity of multiple machines, multicriteria scheduling problems, in: Third Industrial Engineering Research Conference (IERC’94), Atlanta (USA), 1994, pp. 662 -665
[2] Colorni, A.; Dorigo, M.; Maniezzo, V., Distributed optimization by ants colonies, (Varela, F.; Bourgine, P., First European Conference on Artificial Life (1991)), 134-142
[3] Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job-shop scheduling, Belgian Journal of Operations Research Statistics and Computer Science (JORBEL), 34, 39-53 (1994) · Zbl 0814.90047
[4] DellaCroce, F.; Ghirardi, M.; Tadei, R., An improved branch and bound algorithm for the two-machine total completion time flow shop problem, European Journal of Operational Research, 139, 2, 293-301 (2002) · Zbl 1001.90065
[5] F. Della Croce, M. Ghirardi, R. Tadei, Recovering Beam Search: A hybrid heuristic method for combinatorial optimization problems. Submitted to Operations Research, 2002; F. Della Croce, M. Ghirardi, R. Tadei, Recovering Beam Search: A hybrid heuristic method for combinatorial optimization problems. Submitted to Operations Research, 2002 · Zbl 1061.90093
[6] Dileepan, P.; Sen, T., Bicriterion static scheduling research for a single machine, Omega, 16, 1, 53-59 (1988)
[7] Dorigo, M.; Di Caro, G.; Gambardella, L. M., Ant algorithms for discrete optimization, Artificial Life, 5, 3, 137-172 (1999)
[8] Fry, T. D.; Armstrong, R. D.; Lewis, H., A framework for single machine multiple objective sequencing research, Omega, 17, 6, 595-607 (1989)
[9] Gambardella, L. M.; Taillard, E.; Dorigo, M., Ants colonies for the qap, Journal of the Operational Research Society, 5, 167-176 (1999) · Zbl 1054.90621
[10] Gupta, J. N.D; Hennig, K.; Werner, F., Local search heuristic for the two-stage flowshop problems with secondary criterion, Computers and Operations Research, 29, 2, 113-149 (2002)
[11] Gupta, J. N.D; Neppalli, V. R.; Werner, F., Minimizing total flow time in a two-machine flowshop problem with minimum makespan, International Journal of Production Economics, 69, 3, 323-338 (2001)
[12] Gupta, J. N.D; Palanimuthu, N.; Chen, C.-L, Designing a tabu search algorithm for the two-stage flowshop problem with secondary criterion, Production Planning and Control, 10, 3, 251-265 (1999)
[13] J.N.D. Gupta, F. Werner, On the solution of 2-machine flow and open shop scheduling problems with secondary criteria, in: 15th ISPE/IEE International Conference on CAD/CAM, Robotics, and Factories of the Future, Aguas de Lindoia (Brasil), 1999, pp. MW4.1-MW4.6; J.N.D. Gupta, F. Werner, On the solution of 2-machine flow and open shop scheduling problems with secondary criteria, in: 15th ISPE/IEE International Conference on CAD/CAM, Robotics, and Factories of the Future, Aguas de Lindoia (Brasil), 1999, pp. MW4.1-MW4.6
[14] J.A. Hoogeveen, Single-Machine Bicriteria Scheduling, Ph.D. Thesis, CWI, Amsterdam, 1992; J.A. Hoogeveen, Single-Machine Bicriteria Scheduling, Ph.D. Thesis, CWI, Amsterdam, 1992 · Zbl 0749.90042
[15] Johnson, S. M., Optimal two and three stage production schedules with set-up time included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[16] D. Laügt, F. Tercinet, N. Monmarché, V. T’kindt, Une heuristique basée sur les colonies de fourmis pour résoudre un problème d’ordonnancement bicritère, Research report 231, E3i/Université de Tours (France), in French, 2000; D. Laügt, F. Tercinet, N. Monmarché, V. T’kindt, Une heuristique basée sur les colonies de fourmis pour résoudre un problème d’ordonnancement bicritère, Research report 231, E3i/Université de Tours (France), in French, 2000
[17] Nagar, A.; Haddock, J.; Heragu, S. S., Multiple and bicriteria scheduling: A literature survey, European Journal of Operational Research, 81, 88-104 (1995) · Zbl 0913.90178
[18] Nagar, A.; Heragu, S. S.; Haddock, J., A branch-and-bound approach for a two-machine flowshop scheduling problem, Journal of the Operational Research Society, 46, 721-734 (1995) · Zbl 0832.90058
[19] Neppalli, V. R.; Chen, C.-L; Gupta, J. N.D, Genetic algorithms for the two-stage bicriteria flowshop problem, European Journal of Operational Research, 95, 356-373 (1996) · Zbl 0943.90584
[20] N.A. Rahman, A course in theoretical statistics, Griffin (London), 1968; N.A. Rahman, A course in theoretical statistics, Griffin (London), 1968
[21] Rajendran, C., Two-stage flowshop scheduling problem with bicriteria, Journal of the Operational Research Society, 43, 9, 871-884 (1992) · Zbl 0757.90037
[22] Sayin, S.; Karabati, S., A bicriteria approach to the two-machine flow shop scheduling problem, European Journal of Operational Research, 113, 435-449 (1999) · Zbl 0957.90064
[23] Serifoglu, F. S.; Ulusoy, G., A bicriteria two-machine permutation flowshop problem, European Journal of Operational Research, 107, 414-430 (1998) · Zbl 0943.90041
[24] Stützle, T., An ant approach to the flow shop problem, (Proceedings of EUFIT’98, Aachen (Germany) (1998)), 1560-1564
[25] V. T’kindt, J.-C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms, Springer, forthcoming (2002); V. T’kindt, J.-C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms, Springer, forthcoming (2002)
[26] V. T’kindt, J.N.D. Gupta, J.-C. Billaut, Two-machine flowshop scheduling with a secondary criterion, Computers and Operations Research, forthcoming (2002); V. T’kindt, J.N.D. Gupta, J.-C. Billaut, Two-machine flowshop scheduling with a secondary criterion, Computers and Operations Research, forthcoming (2002)
[27] Yeh, W.-C, A new branch-and-bound approach for the \(n/2\)/flowshop/\( αf + βc_{max}\) flowshop scheduling problem, Computers and Operations Research, 26, 1293-1310 (1999) · Zbl 0967.90052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.