×

Double layer ACO algorithm for the multi-objective FJSSP. (English) Zbl 1175.90201

Summary: Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. In this work, a double layer Ant Colony Optimization (ACO) algorithm is proposed for the Flexible Job Shop Scheduling Problem (FJSSP). In the proposed algorithm, two different ACO algorithms are applied to solve the FJSSP with a hierarchical way. The primary mission of upper layer ACO algorithm is achieving an excellent assignment of operations to machines. The leading task of lower layer ACO algorithm is obtaining the optimal sequencing of operations on each machine. Experimental results suggest that the proposed algorithm is a feasible and effective approach for the multi-objective FJSSP.

MSC:

90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
90C29 Multi-objective and goal programming

Software:

FJSSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kolonko, M., ”Some new results on simulated annealing applied to the job shop scheduling problem,” European Journal of Operational Research 113, 1, pp. 123–136, 1999. · Zbl 0933.90029
[2] Wu, D.W., Lu, T.D. and Liu, X.B., et al., ”Parallel simulated annealing algorithm for solving job-shop scheduling problem,” Computer Integrated Manufacturing Systems 11, 6, pp. 847–850, 2005.
[3] Pezzella, F. and Merelli, E., ”A tabu search method guided by shifting bottleneck for the job shop scheduling problem,” European Journal of Operational Research 120, 2, pp. 297–310, 2000. · Zbl 0953.90026
[4] Liang, X. and Huang, M. ”Application of tabu search-parallel genetic algorithm for job-shop scheduling,” Computer Integrated Manufacturing Systems 11, 5, pp. 678–681, 2005.
[5] Park, B.J., Choi, H.R. and Kim, H.S., ”A hybrid genetic algorithm for the job shop scheduling problems,” Computers and Industrial Engineering 45, 4, pp. 597–613, 2003.
[6] Mattfeld, D.C. and Bierwirth, C., ”An efficient genetic algorithm for job shop scheduling with tardiness objectives,” European Journal of Operational Research 155, 3, pp. 616–630, 2004. · Zbl 1044.90035
[7] Yang, X.M. and Zeng, J.C., ”Multi-individual-crossover genetic algorithm for job shop scheduling problem,” Computer Integrated Manufacturing Systems 10, 9, pp. 1114–1119, 2004.
[8] Goncalves, J.F., et al., ”A hybrid genetic algorithm for the job shop scheduling problem,” European Journal of Operational Research 167, 1, pp. 77–95, 2005. · Zbl 1075.90028
[9] Watanabe, M., Ida, K. and Gen, M., ”A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem,” Computers and Industrial Engineering 48, 4, pp. 743–752, 2005.
[10] Wang, C.Q., Cao, Y.F. and Dai, G.Z., ”Bi-directional convergence ACO for job-shop scheduling,” Computer Integrated Manufacturing Systems 10, 7, pp. 820–824, 2005.
[11] Huang, K.L. and Liao, C.J., ”Ant colony optimization combined with taboo search for the job shop scheduling problem,” Computers and Operations Research 35, 4, pp. 1030–1046, 2008. · Zbl 1180.90123
[12] Wang, X.H., Qiao, Q.L. and Wang, Z.O., ”A Method to Solve Job-shop Schedule Problems by Neural Network with Transient Chaos,” System Engineering 19, 3, pp. 43–48, 2001.
[13] Fonseca, D.J. and Navaresse, D., ”Artificial neural networks for job shop simulation,” Advanced Engineering Informatics 16, 4, pp. 241–246, 2002. · Zbl 05388074
[14] He T., Liu W.H., and Liang L.P., ”A Class of Job Shop Scheduling Based on the Evolutionary Algorithm,” Computer Integrated Manufacturing Systems 7, 1, pp. 47–50, 2001.
[15] Tanev, I.T., Uozumi, T. and Morotome, Y., ”Hybrid evolutionary algorithmbased real-world flexible job shop scheduling problem: application service provider approach,” Applied Soft Computing 5, 1, pp. 87–100, 2004. · Zbl 05391450
[16] Asano, M. and Ohta, H., ”A Heuristic for Job Shop Scheduling to Minimize Total Weighted Tardiness,” Computers and Industrial Engineering 42, 2–4, pp. 137-147, 2002.
[17] Tarantilis, C.D. and Kiranoudis, C.T., ”A list-based threshold accepting method for job shop scheduling problems,” International Journal of Production Economics 77, 2, pp. 159–171, 2002.
[18] Chen, H. and Luh, P.B., ”An alternative framework to Lagrangian relaxation approach for job shop scheduling,” European Journal of Operational Research 149, 3, pp. 499–512, 2003. · Zbl 1033.90036
[19] Huang, W.Q. and Yin A.H., ”An improved shifting bottleneck procedure for the job shop scheduling problem,” Computers and Operations Research 31, 12, pp. 2093–2110, 2004. · Zbl 1036.90039
[20] Jansen, K., Mastrolilli, M. and Solis-Oba R., ”Approximation schemes for job shop scheduling problems with controllable processing times,” European Journal of Operational Research 167, 2, pp. 297–319, 2005. · Zbl 1075.90029
[21] Bruker, P. and Schlie, R., ”Job-shop scheduling with multi-purpose machines,” Computing 45, 4, pp. 369–375, 1990. · Zbl 0813.90058
[22] Xia, W.J. and Wu, Z.M., ”An effective hybrid optimization approach for multiobjective flexible job-shop scheduling problems,” Computers and Industrial Engineering 48, 2, pp. 409–425, 2005.
[23] Brandimarte, P., ”Routing and scheduling in a flexible job shop by taboo search,” Annals of Operations Research 22, 2, pp. 157–183, 1993. · Zbl 0775.90227
[24] Tung, L.F., Li, L. and Nagi, R., ”Multi-objective scheduling for the hierarchical control of flexible manufacturing systems,” The International Journal of Flexible Manufacturing Systems 11, 4, pp. 379–409, 1999.
[25] Kacem, I., Hammadi, S. and Borne, P., ”Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Transactions on Systems, Man, and Cybernetics, Part C 32, 1, pp. 1–13, 2002. · Zbl 1006.90044
[26] Kacem, I., Hammadi, S. and Borne, P., ”Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic,” Mathematics and Computers in Simulation 60, 3-5, pp. 245–276, 2002. · Zbl 1006.90044
[27] Hurink, E., Jurisch, B. and Thole, M., ”Tabu search for the job shop scheduling problem with multi-purpose machines,” Operations Research Spektrum 15, pp. 205–215, 1994. · Zbl 0798.90086
[28] Mastrolilli, M. and Gambardella, L.M., ”Effective neighborhood functions for the flexible job shop problem,” Journal of Scheduling 3, 1, pp. 3–20, 2002. · Zbl 1028.90018
[29] Dauzere-Peres, S. and Paulli, J., ”An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search,” Annals of Operations Research 70, pp. 281–306, 1997. · Zbl 0890.90097
[30] Yager R.R., ”Quantifiers in the Formulation of Multiple Objective Decision Functions,” Information Sciences 31, pp. 107–139, 1983. · Zbl 0551.90084
[31] Petrovic D., Duenas A. and Petrovic S., ”Decision support tool for multiobjective job shop scheduling problems with linguistically quantified decision functions,” Decision Support Systems 43, pp. 1527–1538, 2007.
[32] Dorigo M. and Stutzle T., Ant colony optimization, Cambridge, MA: MIT Press, 2004. · Zbl 1092.90066
[33] Ho N.B., Tay J.C. and Lai E.M.K., ”An Effective Architecture for Learning and Evolving Flexible Job-shop Schedules,” European Journal of Operational Research 179, pp. 316–333, 3007. · Zbl 1180.90121
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.