Application Of Differential Evolution For Solving Job Shop Scheduling Problem

Pajaree Punnawat, Komkrit Leksakul

Abstract


Job Shop Scheduling problem (JSSP) is a famous problem in which jobs are assigned to machines at particular times, while trying to minimize the total length of the schedule (Makespan). This characteristic of the problem make it be NP-Hard problem that cannot be solved by using the exact algorithms in polynomial time. So this study used the Differential Evolution (DE) algorithm, one of the approximate algorithms, to solve Job Shop Scheduling problem. Based on our experiment, we could indicate that the results of small and medium size problems using DE approach obtained the optimal solution reliably and effectively.


Full Text:

PDF

References


Banharnsakun, A., Sirinaovakul, B., & Achalakul, T. (2012). “Job Shop Scheduling with the Best-so-far ABC”. Engineering Applications of Artificial Intelligence, 25(3), 583-593. doi:http://dx.doi.org/10.1016/j.engappai.2011.08.003

Gonçalves, J. F., de Magalhães Mendes, J. J., & Resende, M. c. G. C. (2005). “A hybrid genetic algorithm for the job shop scheduling problem”. European Journal of Operational Research, 167(1), 77-95. doi:http://dx.doi.org/10.1016/j.ejor.2004.03.012

Gromicho, J. A. S., van Hoorn, J. J., Saldanha-da-Gama, F., & Timmer, G. T. (2012). “Solving the job-shop scheduling problem optimally by dynamic programming”. Computers & Operations Research, 39(12), 2968-2977. doi:http://dx.doi.org/10.1016/j.cor.2012.02.024

Qing, R., & Wang, Y. (2012). “A new hybrid genetic algorithm for job shop scheduling problem”. Computers & Operations Research, 39(10), 2291-2299. doi:http://dx.doi.org/10.1016/j.cor.2011.12.005

Wisittipanich, W., & Kachitvichyanukul, V. (2011). “Two enhanced differential evolution algorithms for job shop scheduling problems”. International Journal of Production Research, 50(10), 2757-2773. doi:http://dx.doi.org/10.1080/00207543.2011.588972.


Refbacks

  • There are currently no refbacks.