An Improved Immune Algorithm for Manufacturing Scheduling

Abstract:

This paper addresses an n-job, m-machine permutation flow shop scheduling problem to minimize makespan criterion. We present a modification of the best-known immune algorithm of Engin and Döyen (2004) [A new approach to solve hybrid flowshop scheduling problems by artificial immune system. Future Generations Computer Systems 2004;20:1083-1095] for this problem. To evaluate the solution quality and efficiency of the proposed method, the experiments are carried out in two phases on a set of benchmark problems and analyzed. We show, through computational experimentation, that this modification considerably improves its performance without affecting its time complexity. The proposed method also has been compared with the currently best simulated annealing from the literature.

• Periodical: Advanced Materials Research (Volumes 488-489)
• Pages: 1109-1113
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.488-489.1109
• Online since: March 2012
• Authors: Dipak Laha, Indranil Ghosh, Pranab K. Dan, Sagar U. Sapkal
• Keywords: Flow Shops, Immune Algorithm, Make Span, Manufacturing, Optimization, Scheduling

References

[1] J. Gao, L. Sun and M. Gen: Computers and Operational Research Vol. 35 (2008), p.2892.

[2] K. Mori, M. Tsukiyama and T. Fukuda: Transactions of IEEE Japan Vol. 113C (1993), p.872.

[3] R. Agarwal, M.K. Tiwari and S.K. Mukherjee: International Journal of Advanced Manufacturing Technology Vol. 43 (2006), p.584.

[4] L.N. De Castro and J. Timmis: Artificial immune systems: A new computational intelligence approach ( London, Springer-Verlag 2002).

[5] D. Dasgupta and S. Forrest: Artificial immune systems in industrial applications, in: Proceedings of the Second International Conference on Intelligent Processing and Manufacturing Materials Honolulu (1999).

DOI: 10.1109/ipmm.1999.792486

[6] L.N. De Castro and F.J. Von Zuben: The clonal selection algorithm with engineering applications, in: Proceedings of the Workshop Las Vegas (2000).

[7] D. Dasgupta (Ed. ), Artificial Immune Systems and their applications (Springer-Verlag 1999).

[8] E. Hart and J. Timmis: Applied Soft Computing Vol. 8 (2008), p.191.

[9] A.P.G. Brown and Z.A. Lomnicki: Operational research Quarterly Vol. 17 (1966), p.173.

[10] M. Nawaz, E.E. Enscore and I. Ham: Omega Vol. 11 (1983), p.91.

[11] D. Laha and S. C. Sarin: Omega Vol. 37 (2009), p.734.

[12] C.R. Reeves: Computers and Operations Research Vol. 22 (1996), p.5.

[13] D. Laha and U.K. Chakraborty: Engineering Applications of Artificial Intelligence Vol. 20 (2007), p.851.

[14] M. Zandieh, S.M.T.F. Ghomi and S.M.M. Husseini: Applied Mathematics and Computation Vol. 180 (2006), p.111.

[15] M.E. Kurz and R.G. Askin: European Journal of Operational Research Vol. 159 (2004), p.66.

[16] A. Bagheri, B. Zandieh, M. Iraj, M. Yazdani and C. Future: Generation Computer Systems Vol. 26 (2010), p.533.

[17] W. Xia and Z. Wu: Computers and Industrial Engineering Vol. 48 (2005), p.409.

[18] I. Kacem, S. Hammandi and N. Borne: IEEE Transaction on systems, man and cybernetics, Part C Vol. 32 (2002), p.1.

[19] H. Zhang and M. Gen: International Journal of Complexity Vol. 11 (2005), p.223.

[20] O. Engin and A. Döyen: Future Generations Computer Systems Vol. 20 (2004), p.1083.

[21] I.H. Osman and C.N. Potts: Omega Vol. 17 (1989), p.551.

[22] T. Gonzalez and S. Sahni: Operations Research Vol. 26 (1978), p.36.

[23] E. Taillard: European Journal of Operational Research Vol. 47 (1990), p.64.