Single Objective Evolutionary Algorithm for Job Shop Scheduling Problem

G. Uma Sankar; Dr. D. Saravanan

doi:https://doi.org/10.14445/22315373/IJMTT-V3I1P507

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 3 | Issue 1 | Year 2012 | Article Id. IJMTT-V3I1P507 | DOI : https://doi.org/10.14445/22315373/IJMTT-V3I1P507

Single Objective Evolutionary Algorithm for Job Shop Scheduling Problem

G. Uma Sankar, Dr. D. Saravanan

Citation :

G. Uma Sankar, Dr. D. Saravanan, "Single Objective Evolutionary Algorithm for Job Shop Scheduling Problem," International Journal of Mathematics Trends and Technology (IJMTT), vol. 3, no. 1, pp. 38-42, 2012. Crossref, https://doi.org/10.14445/22315373/IJMTT-V3I1P507

Abstract

we discuss approaches to developing single objective evolutionary algorithm for solving the job shop scheduling problem. Initial population is generated randomly. Two-row chromosome structure is adopted based on working procedure and machine distribution. The relevant crossover and mutation operation is also designed. It jumped from the local optimal solution, and the search area of solution is improved. Finally, the algorithm is tested on instances of 8 working procedure and 5 machines. The result shows that the evolutionary algorithm has been successfully applied to the job shop scheduling problems efficiency.

Keywords

Job shop scheduling, Evolutionary algorithm

References

[1] Lars Monch, Rene Schabacker, Detlef Pabst et al,“Evolutionary algorithm-based Sub-problem Solution Procedures for a Modified Shifting Bottleneck Heuristic for Complex Job Shops”, European Journal of Operational Research, Vol.3 No.177,pp.2100-2118， 2007.
[2] Young Su Yun, “Genetic Algorithm with Fuzzy Logic Controller for Preemptive and non-Preemptive Job Shop Scheduling roblems”, Computers & Industrial Engineering, Vol.3 No.43 pp.623-644，2007.
[3] Dessouky, M.M, Leachman et al, “Dynamic models of production with multiple operations and general processing times”, Journal of the Operational Research Society, Vol.6 No.48 pp:983-997，1997.
[4] Makoto Asano, Hiroshi Ohta, “A Heuristic for Job Shop Scheduling to Minimize Total Weighted Tardiness”, Computers & Industrial Engineering, Vol. 2-4 No 42 pp:137-147，2002.
[5] Gomes, M.C., Barbosa-Povoa et al, “Optimal scheduling for flexible job shop operations”, International Journal of Production Research, Vol.11 No.43 pp:2323-2353，2005.
[6] Taicir Loukil, Jacques Teghem, Philippe Fortemps , “A multi-objective production scheduling case study solved by simulated annealing”, European Journal of Operation Research, Vol.3 No.179 pp:709-722，2007.
[7] Jason Chao-Hsien Pan, Jen-Shiang Chen, “Mixed–Binary Integer Programming Formulations for the Reentrant Job Shop Scheduling Problem”, Computers & Operations Research, Vol.5 No.32 pp:1197-1212, 2005.
[8] S.Q.Liu, H.L.Ong,K.M.Ng(2005), “Metaheuristics for Minimizing the Makespan of the Dynamic Shop Scheduling Problem”, Advances in Engineering software, Vol.3 No.36 pp: 199-205.
[9] Bortjan Murovec, Peter Suhel, “A repairing technique for the local search of the job-shop problem”, European Journal of Operational Research, Vol.1 No.153.
[10] Chen Hua-ping, Gu Feng, Lu Bing-yuan et al, “Application of Self-adaptive Multi-objective Evolutionary algorithm in Flexible Job Shop Scheduling”, Journal of System Simulation, Vol.8 No.18 pp: 2271-2274. 2006.
[11] Hong Zhou, Yuncheng Feng, Limin Han, “The Hybrid Heuristic Evolutionary algorithm for Job Shop Scheduling”, Computers & Industrial Engineering, Vol.3 No.40 pp:191-200, 2001.