A Three-Fold Approach to Solve Dynamic Job Shop Scheduling Problems by Artificial Immune Algorithm

Abstract:

This paper aims to propose a novel three-fold approach to solve dynamic job-shop scheduling problems by artificial immune algorithm. The proposed approach works in three phases. Firstly, priority rules are deployed to decrease problem scale instead of using scheduling algorithms directly. Secondly, immune algorithm is applied to optimize the individual scheduling modules. Finally, integration schema is employed to reschedule operations and minimize makespan of gross schedule. The integration schema is carried out in a dynamic manner that the previous modules’ machine idle time is searched continuously. In this way, the machine utilization is increased while the objective of makespan minimization is maintained. Efficacy of the proposed approach has been tested with test instances of job-shop scheduling problems. The experimentation results clearly show effectiveness of the proposed approach.

• Periodical: Advanced Materials Research (Volumes 139-141)
• Pages: 1666-1669
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.139-141.1666
• Online since: October 2010
• Authors: Shan Shan Wu, Bei Zhi Li, Jian Guo Yang
• Keywords: Decomposition, Immune Algorithm, Job Shop Scheduling, Make Span

References

[1] M.R. Garey and D.S. Johnson: Computers and Intractability (Freeman, San Francisco 1979).

[2] M. Zandieh, S.M.T. Fatemi Ghomi and S. M. Moattar Husseini: Appl. Math. Comput. Vol. 180(2006), p.111.

[3] B. M. Naderi, R. Khalili and T. Moghaddam: Comput. Ind. Eng. Vol. 56(2009), p.1494.

[4] L.N. De Castroand and F.J. von Zuben: IEEE Trans. Evol. Comput. special issue on the artificial immune system, Vol. 6(2002), pp.239-251.

[5] S. Lawrence: Technical Report (GSIA, Carnegie Mellon University 1984).

[6] F. Pezzella and E. Merelli: Eur. J. of Oper. Res. Vol. 120(2000), pp.297-310.