An Improved Genetic Algorithm For Just-In-Time Job-Shop Scheduling Problem

Abstract:

This paper studies a just-in-time job-shop scheduling problem (JITJSSP) in which each operation has an earliness cost or a tardiness cost if it is completed before or after its due date and the objective function is to minimize the total earliness and tardiness costs of all operations. In order to solve this problem, an improved genetic algorithm (IGA) is introduced in this paper. IGA utilizes an operation-based scheme to represent schedules as chromosomes. Then, each chromosome is processed through a three-stage mechanism. Firstly, the semi-active decoding process is employed to expand the search space of solutions and guarantee comprehensive solutions. Secondly, the greedy insertion mechanism for tardy operations is executed to move the tardy operations left to the appropriate idle time to reduce the tardiness costs. Finally, the greedy insertion mechanism for early operations is proposed to shift the early operations right to the suitable idle time to decrease the earliness costs. After the maximum number of generations is reached, IGA continues with selection, crossover and mutation. The experimental results finally show that most of solutions on the benchmarks are improved by our algorithm.

• Periodical: Advanced Materials Research (Volumes 472-475)
• Pages: 2462-2467
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.472-475.2462
• Online since: February 2012
• Authors: Hong An Yang, Jin Yuan Li, Liang Liang Qi
• Keywords: Improved Genetic Algorithm (IGA), JIT, Job-Shop, Three-Stage Decoding Mechanism

References

[1] Baptiste, P., Flamini, M., Sourd, F: Computers & Operations Research 35, 906–915 (2008)

DOI: 10.1016/j.cor.2006.05.009

[2] Monette J.N., Devill Y., Hentenryck P: Just-In-Time Scheduling with Constraint Programming. Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (2009), 241-248.

DOI: 10.1609/icaps.v19i1.13356

[3] Araujo, R.P., Santos, A.G., Arroyo J: Genetic Algorithm and Local Search for Just-in-Time Job–Shop Scheduling. The IEEE Congress on Evolutionary Computation, CEC'09, Trondheim (2009), 955-961.

DOI: 10.1109/cec.2009.4983048

[4] Araujo, R.P., Santos, A.G., Arroyo J: Learning and Intelligent Optimization (2010), 6073: 10-24.

[5] Chaoyong Zhang, Yunqing Rao, Peigen Li, et al:China Mechanical Engineering, 2004 (23):2149-2153 (In Chinese).

[6] Cheng R: A study on genetic algorithms-based optimal scheduling techniques. Ph. D Dissertation, Tokyo Institute of Technology (1999).