Abstract
Ant colony optimization (ACO) is a novel intelligent meta-heuristic originating from the foraging behavior of ants. An efficient heuristic of ACO is the ant colony system (ACS). This study presents a multi-heuristic desirability ACS heuristic for the non-permutation flowshop scheduling problem, and verifies the effectiveness of the proposed heuristic by performing computational experiments on a well-known non-permutation flowshop benchmark problem set. Over three-quarters of the solutions to these experiments are superior to the current best solutions in relevant literature. Since the proposed heuristic is comprehensible and effective, this study successfully explores the excellent potential of ACO for solving non-permutation flowshop scheduling problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dudek RA, Panwalkar SS, Smith ML (1992) The lessons of flowshop scheduling research. Oper Res Soc Am 40:7–13
Koulamas C (1998) A new constructive heuristic for the flowshop scheduling problem. Eur J Oper Res 105:66–71
Reisman A, Kumar A, Motwani J (1997) Flowshop scheduling/sequencing research: a statistical review of the literature, 1952–1994. IEEE Trans Eng Manage 44:316–329
King JR, Spachis AS (1980) Heuristics for flow-shop scheduling. Int J Prod Res 18:345–357
Park YB, Pegden CD, Enscore EE (1984) A survey and evaluation of static flowshop scheduling heuristics. Int J Prod Res 22:127–141
Turner S, Booth D (1987) Comparison of heuristics for flow shop sequencing. OMEGA 15:75–85
Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129
Widmer M, Hertz A (1989) A new heuristic method for the flow shop sequencing problem. Eur J Oper Res 41:186–193
Ogbu FA, Smith DK (1990) The application of the simulated annealing algorithm to the solution of the n / m / Cmax flowshop problem. Comput Oper Res 17:243–253
Chen CL, Vempati VS, Aljaber N (1995) An application of genetic algorithms for flow shop problems. Eur J Oper Res 80:389–396
Potts CN, Van Wassenhove LN (1991) Single machine tardiness sequencing heuristics. IIE Trans 23:346–354
Dorigo M, Di Caro G, Gambardella LM (1999) Ant algorithms for discrete optimization. Arti Life 5:137–172
Colorni A, Dorigo M, Maniezzo V (1991) Distributed optimization by ants colonies. In: Verela F, Bourgine P (eds) Proceedings of the first European Conference on Artificial Life (ECAL’91). MIT Press, Cambridge, Mass, USA, pp 134–142
Dorigo M (1992) Optimization, learning and natural algorithms. PhD Thesis, DEI, Politecnico di Milano, Italy
Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evolu Comput 1:53–66
Gambardella LM, Dorigo M (1997) HAS-SOP: hybrid ant system for the sequential ordering problem. Technical Report IDSIA-11-97, IDSIA, Lugano, Switzerland
Gambardella LM, Taillard E, Dorigo M (1999) Ant colonies for the quadratic assignment problem. J Oper Res Soc 50:167–176
Bullnheimer B, Hartl RF, Strauss C (1999) An improved ant system algorithm for the vehicle routing problem. Ann Oper Res 89:319–334
Costa D, Hertz A (1997) Ants can colour graphs. J Oper Res Soc 48:295–305
Kuntz P, Layzell P, Snyers D (1997) A colony of ant-like agents for partitioning in VLSI technology. Proceedings of the Fourth European Conference on Artificial Life. The MIT Press, Cambridge, MA
Song YH, Chou CS (1998) Application of ant colony search algorithms in power system optimization. IEEE Power Eng Rev 18:63–64
Di Caro G, Dorigo M (1998) AntNet: distributed stigmergetic control for communications networks. J Arti Intel Res 9:317–365
Gagnë C, Price WL, Gravel M (2002) Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. J Oper Res Soc 53:895–906
Ying KC, Liao CJ (2003) An ant colony system approach for scheduling problem. Prod Plan Cont 14:68–75
Rajendran C, Ziegler H (2004) Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res 155:426–438
Ying KC, Liao CJ (2004) An ant colony system for permutation flow-shop sequencing. Comput Oper Res 31:791–801
Colorni A, Dorigo M, Maniezzo V, Trubian M (1994) Ant system for job-shop scheduling. Belgian J Oper Res Stat Comput Sci (JORBEL) 34:39–53
Christian B (2005) Beam-ACO¯hybridizing ant colony optimization with beam search: an application to openshop scheduling. Comput Oper Res 32:1565–1591
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discete Math 5:287–362
James ED, Michael PH (1970) Review of sequencing research. Nav Res Log Q 17:11–39
Haupt R (1989) A survey of priority rule-based scheduling. OR Spek 11:3–16
Chang YL, Toshiyuki S, Robert SS (1996) Ranking dispatching rules by data envelopment analysis in a job shop environment. IIE Trans 28:631–642
Holthaus O, Rajendran C (2000) Efficient jobshop dispatching rules: further developments. Prod Plan Cont 11:171–178
Demirkol E, Mehta S, Uzsoy R (1998) Benchmarks for shop scheduling problems. Euro J Oper Res 109:137–141
Pinedo M (1995) Scheduling: theory, algorithms and system. Prentice-Hall, New Jersey
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
1.1 Simple constructive heuristics and its formulas of RI kl
-
1.
SPT: Select the job with the shortest processing time; \(RI_{{kl}} = p_{{kl}} .\)
-
2.
LPT: Select the job with the longest processing time; \(RI_{{kl}} = p_{{kl}} .\)
-
3.
LWKR: Select the job with the least work remaining; \(RI_{{kl}} = {\sum\limits_{u = l}^m {p_{{ku}} } }.\)
-
4.
MWKR: Select the job with the most work remaining; \(RI_{{kl}} = {\sum\limits_{u = l}^m {p_{{ku}} } }.\)
-
5.
SRM: Select the job with the shortest remaining work, excluding the operation under consideration; \(RI_{{kl}} = {\sum\limits_{u = l + 1}^m {p_{{ku}} } }.\)
-
6.
LRM: Select the job with the longest remaining work, excluding the operation under consideration; \(RI_{{kl}} = {\sum\limits_{u = l + 1}^m {p_{{ku}} } }.\)
-
7.
SPT/TWK: Select the job with the smallest ratio of the processing time to the total work; \(RI_{{kl}} = {p_{{kl}} } \mathord{\left/ {\vphantom {{p_{{kl}} } {{\sum\limits_{u = 1}^m {p_{{ku}} } }}}} \right. \kern-\nulldelimiterspace} {{\sum\limits_{u = 1}^m {p_{{ku}} } }}.\)
-
8.
LPT/TWK: Select the job with the largest ratio of the processing time to the total work; \(RI_{{kl}} = {p_{{kl}} } \mathord{\left/ {\vphantom {{p_{{kl}} } {{\sum\limits_{u = 1}^m {p_{{ku}} } }}}} \right. \kern-\nulldelimiterspace} {{\sum\limits_{u = 1}^m {p_{{ku}} } }}.\)
-
9.
SPT/TWKR: Select the job with the smallest ratio of the processing time to the total work remaining; \(RI_{{kl}} = {p_{{kl}} } \mathord{\left/ {\vphantom {{p_{{kl}} } {{\sum\limits_{u = l}^m {p_{{ku}} } }}}} \right. \kern-\nulldelimiterspace} {{\sum\limits_{u = l}^m {p_{{ku}} } }}.\)
-
10.
LPT/TWKR: Select the job with the largest ratio of the processing time to the total work remaining; \(RI_{{kl}} = {p_{{kl}} } \mathord{\left/ {\vphantom {{p_{{kl}} } {{\sum\limits_{u = l}^m {p_{{ku}} } }}}} \right. \kern-\nulldelimiterspace} {{\sum\limits_{u = l}^m {p_{{ku}} } }}.\)
-
11.
SPT·TWK: Select the job with the smallest value of the processing time multiplied by the total work; \(RI_{{kl}} = p_{{kl}} \cdot {\sum\limits_{u = 1}^m {p_{{ku}} } }.\)
-
12.
LPT·TWK: Select the job with the largest value of the processing time multiplied by the total work; \(RI_{{kl}} = p_{{kl}} \cdot {\sum\limits_{u = 1}^m {p_{{ku}} } }.\)
-
13.
SPT·TWKR: Select the job with the smallest value of the processing time multiplied by the total work remaining; \(RI_{{kl}} = p_{{kl}} \cdot {\sum\limits_{u = l}^m {p_{{ku}} } }.\)
-
14.
LPT·TWKR: Select the job with the largest value of the processing time multiplied by the total work remaining; \(RI_{{kl}} = p_{{kl}} \cdot {\sum\limits_{u = l}^m {p_{{ku}} } }.\)
-
15.
SSO: Select the job with the shortest subsequent operation; \(RI_{{kl}} = p_{{k,{\text{ }}l + 1}} .\)
-
16.
LSO: Select the job with the longest subsequent operation; \(RI_{{kl}} = p_{{k,{\text{ }}l + 1}} .\)
-
17.
SPT+SSO: Select the job with the smallest value of the processing time of the current plus the subsequent operation; \(RI_{{kl}} = p_{{kl}} + p_{{k,{\text{ }}l + 1}} .\)
-
18.
LPT+LSO: Select the job with the largest value of the processing time of the current plus the subsequent operation; \(RI_{{kl}} = p_{{kl}} + p_{{k,{\text{ }}l + 1}} .\)
-
19.
SPT/LSO: Select the job with the smallest ratio of the processing time to the subsequent operation; \(RI_{{kl}} = {p_{{kl}} } \mathord{\left/ {\vphantom {{p_{{kl}} } {p_{{k,{\text{ }}l + 1}} }}} \right. \kern-\nulldelimiterspace} {p_{{k,{\text{ }}l + 1}} }.\)
-
20.
LPT/SSO: Select the job with the largest ratio of the processing time to the subsequent operation; \(RI_{{kl}} = {p_{{kl}} } \mathord{\left/ {\vphantom {{p_{{kl}} } {p_{{k,{\text{ }}l + 1}} }}} \right. \kern-\nulldelimiterspace} {p_{{k,{\text{ }}l + 1}} }.\)
Rights and permissions
About this article
Cite this article
Ying, KC., Lin, SW. Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems. Int J Adv Manuf Technol 33, 793–802 (2007). https://doi.org/10.1007/s00170-006-0492-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-006-0492-8