Abstract
The flexible job shop scheduling problem (FJSP) is to assign each operation to an appropriate machine and to sequence the operations on the machines. The paper describes the development and the application of the artificial immune system (AIS) and the particle swarm optimization (PSO) for solving the flexible job shop scheduling problem with sequence-dependent setup times (SDST-FJSP). A series of the experiments have been designed using the analysis of variance to recognize best settings of parameters. Finally, 30 examples of the different sizes in the SDST-FJSP with the objective of minimizing makespan and mean tardiness have been used to verify the performance of the proposed algorithms, and to compare them with the existing meta-heuristic algorithms in the literature, such as the genetic algorithm (GA), the parallel variable neighborhood search (PVNS), and the variable neighborhood search (VNS). The obtained results show that the proposed PSO outperforms the GA and the PVNS approaches. It is found that the average best-so-far solutions obtained from the proposed AIS are better than those produced by the GA, the PVNS, the VNS, and the PSO algorithms for all the examples.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bagheri A., Zandieh M.: Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—variable neighborhood search approach. J. Manuf. Syst. 30, 8–15 (2011)
Xia, W.; Wu, Z.: An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput. Indus. Eng. 48, 409–425 (2005)
Kurz, M.E.; Askin, R.G.: Comparing scheduling rules for flexible flow lines. Int. J. Product. Econ. 85(2), 371–388 (2003)
Luh, P.B.; Gou, L.; Zhang, Y.; Nagahora, T.; Tsuji, M.; Yoneda, K.; et al.: Job shop scheduling with group dependent setups, finite buffers, and long time horizon. Ann. Oper. Res. 76, 233–259 (1998)
Sule, D.R.: Industrial Scheduling. PWS, Boston (1997)
Zandieh, M.; Mozaffari, E; Gholami, M.: A robust genetic algorithm for scheduling realistic hybrid flexible flow line problems. J. Intell. Manuf. 21, 731–743 (2010)
Manikas, A.; Chang, Y.L.: A scatter search approach to sequence-dependent setup times job shop scheduling. Int. J. Prod. Res. 1, 1–20 (2008)
Li, B.; Wu, S.; Yang, J.; Zhou, Y.; Du, M.: A three-fold approach for job shop problems: a divide-and-integrate strategy with immune algorithm. J. Manufac. Syst. doi:10.1016/j.jmsy.2011.05.005 (2011)
Imanipour, N.: Modeling and solving flexible job-shop problem with sequence dependent setup times. In: Proceedings of the International Conference on Service Systems and Service Management, pp. 1205–1210 (2006)
Saidi-Mehrabad, M.; Fattahi, P.: Flexible job shop scheduling with tabu search algorithms. Int. J. Adv. Manufac. Technol. 32, 563–570 (2007)
Yazdani, M.; Zandieh, M.; Amiri, M.: Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Syst. Appl. 37(1), 678–687 (2009)
Pezzella, F.; Morganti, G.; Ciaschetti, G.: A genetic algorithm for the flexible job-shop scheduling problem. Comput. Oper. Res. 35(10), 3202–3212 (2008)
Farmer, J.D.; Packard, N.H.; Perelson, A.S.: The immune system, adaption, and machine learning. Physica D 22, 187–204 (1986)
Goldberg, D.E.: Genetic Algorithms in Search, Optimisation and Machine Learning. Addison-Wesley, Reading (1989)
Ko, C.H.; Wang, S.F.: Precast production scheduling using multi-objective genetic algorithms. Expert Syst. Appl. 38, 8293–8302 (2011)
Khoo, L.P.; Situmdrang, T.D.: Solving the assembly configuration problem for modular products using an immune algorithm approach. Int. J. Prod. Res. 41, 3419–3434 (2003)
Murphy, K.; Travers, P.; Walport, M.: Janeway’s Immunobiology. Garland Science, London (2007)
Musilek, P.; Lau, A.; Reformat, M.; Wyard-Scott, L.: Immune programming. Inform. Sci. 176(8), 972–1002 (2006)
Tavakkoli-Moghaddam, R.; Rahimi-Vahed, A.; Mirzaei, A.H.: A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Inform. Sci. 177, 5072–5090 (2007)
De Castro, L.N.; Timmis, J.: Artificial Immune Systems: A New Computational Intelligent Approach. Springer, Berlin (2002)
Dasgupta, D.: An overview of artificial immune systems and their applications. In: Artificial Immune Systems and their Applications, pp. 3–18. Springer, Berlin (1998)
Gu, F.; Greensmith, J.; Aickelin, U.: Exploration of the dendritic cell algorithm using the duration calculus. In: Proceedings of the 8th International Conference on Artificial Immune Systems (ICARIS), pp 54–66 (2009)
Dasgupta, D.: Advances in artificial immune systems. IEEE Comput. Intell. Magazine 1, 40–49 (2006)
Ulutas, B.H.; Islier, A.A.: A clonal selection algorithm for dynamic facility layout problems. J. Manufac. Syst. 28, 123–131 (2009)
De Castro, L.N.; Von Zuben, F.J.: The clonal selection algorithm with engineering applications. In: Proceedings of the Workshop on Artificial Immune Systems and Their Applications, Las Vegas, pp. 36–37 (2000)
Matzinger P.: The danger model: a renewed sense of self. Science 296, 301–305 (2002)
Forrest, S.; Perelson, A.S.; Allen, L.; Cherukuri, R.: Self–nonself discrimination in a computer. In: Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy, Oakland, California, pp. 202–212 (1994)
Zandieh, M.; Fatemi Ghomi, S.M.T.; Moattar Husseini, S.M.: An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Appl. Math. Comput. 180(1), 111–127 (2006)
Ada, G.L.; Nossal, G.J.V.: The clonal selection theory. Sci. Am. 257, 50–57 (1987)
Burnet, F.M.: The Clonal Selection Theory of Acquired Immunity. Vanderbilt University Press, Nashville (1959)
Engin, O.; Doyen, A.: Artificial immune systems and applications in industrial problems. Gazi Univ. J. Sci. 17(1), 71–84 (2004)
Kacem, I.; Hammadi, S.; Borne, P.: Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans. Syst. Man Cybern. Part C 32(1), 1–13 (2002)
Thapatsuwan, P.; Pongcharoen, P.; Hicks, C.; Chainate, W.: Development of a stochastic optimisation tool for solving the multiple container packing problems. Int. J. Prod. Econ. doi:10.1016/j.ijpe.2011.05.012 (2011)
Engin, O.; Doyen, A.: A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Gener. Comput. Syst. 20, 1083–1095 (2004)
Clerc, M.; Kennedy, J.: The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evol. Comput. 6(1), 58–73 (2002)
Eberhart, R.; Shi, Y.: Tracking and optimizing dynamic systems with particle swarms. In: Proceedings of the IEEE congress on evolutionary computation (CEC), Seoul, Korea, pp. 94–107 (2001)
Eberhart, R.; Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, pp. 39–43 (1995)
Al-Duwaish, H.N.: Identification of Hammerstein models with known nonlinearity structure using particle swarm optimization. Arab. J. Sci. Eng. 36(7), 1269–1276 (2011)
Kuo, R.J.; Lin, L.M.: Application of a hybrid of genetic algorithm and particle swarm optimization algorithm for order clustering. Decis. Support Syst. 49, 451–462 (2010)
Yang, I.T.: Performing complex project crashing analysis with aid of particle swarm optimization algorithm. Int. J. Proj. Manage. 25, 637–646 (2007)
Bonabeau, E.; Meyer, C.: Swarm intelligence: a whole new way to think about business. Harv Bus. Rev. 79(5), 107–114 (2001)
Li, Y.; Yao, D.; Yao, J.; Chen, W.: A particle swarm optimization algorithm for beam angle selection in intensity-modulated radiotherapy planning. Phys. Med. Biol. 50(15), 3491–3514 (2005)
Eberhart, R.; Shi, Y.: Comparison between genetic algorithms and particle swarm optimization. In: Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, San Diego, CA, pp. 611–666 (1998)
Haixiang, G.; Kejun, Z.; Chang, D.; Lanlan, L.: Intelligent optimization for project scheduling of the first mining face in coal mining. Expert Syst. Appl. 37, 1294–1301 (2010)
Maghsoudi, M.J.; Ibrahim, Z.; Buyamin, S.; Rahmat, M.F.: Data clustering for the DNA computing readout method implemented on lightcycler and based on particle swarm optimization. Arab. J. Sci. Eng. doi:10.1007/s13369-012-0196-3(2012)
Clerc, M.: The swarm and the queen: towards a deterministic and adaptive particle swarm optimization. In: Proceedings of Congress on Evolutionary Computation, Washington, DC, pp. 1951–1957 (1999)
Taleizadeh, A.A.; Akhavan Niaki, S.T.; Haji Seyedjavadi, S.M.: Multi-product multi-chance-constraint stochastic inventory control problem with dynamic demand and partial back-ordering: a harmony search algorithm. J. Manufac. Syst. doi:10.1016/j.jmsy.2011.05.006 (2011)
Zhang, H.; Li, H.; Tam, C.M.: Particle swarm optimization for resource-constrained project scheduling. Int. J. Proj. Manage. 24, 83–92 (2006)
Fan, H.: A modification to particle swarm optimization algorithm. Eng. Comput. 19(8), 970–989 (2002)
Kennedy, J.; Eberhart, R.; Shi, Y.: Swarm Intelligence. Morgan Kaufman Publishers, San Francisco (2001)
Shi, Y.; Eberhart, R.: Parameter selection in particle swarm optimization. In: Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, New York, pp. 591–600 (1998)
Kennedy, J.; Eberhart, R.: Particle swarm optimisation. In: Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, pp. 1942–1948 (1995)
Shi, Y.; Eberhart, R.: A modified particle swarm optimizer. In: Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 69–73 (1998)
Wang, K.P.; Huang, L.; Zhou, C.G.; Pang, W.: Particle swarm optimization for traveling salesman problem. In: Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xian, pp. 1583–1585 (2003)
Cuiru, W.; Jiangwei, Z.; Jing, Y.; Chaoju, H.; Jun, L.: A modified particle swarm optimization algorithm and its application for solving traveling salesman problem. In: Proceedings of the International Conference on Neural Networks and Brain, ICNN&B ‘05, pp. 689–694 (2005)
Kök, M.: Modeling and assessment of some factors that influence surface roughness for the machining of particle reinforced metal matrix composites. Arab. J. Sci Eng 36(7), 1347–1365 (2011)
Sadrzadeh A.: A genetic algorithm with the heuristic procedure to solve the multi-line layout problem. Comput. Indus Eng. 62(4), 1055–1064 (2012)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sadrzadeh, A. Development of Both the AIS and PSO for Solving the Flexible Job Shop Scheduling Problem. Arab J Sci Eng 38, 3593–3604 (2013). https://doi.org/10.1007/s13369-013-0625-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-013-0625-y