Multi-Objective Optimization Approach with Job-Based Encoding Method for Semiconductor Final Testing Scheduling Problem

Abstract:

The semiconductor final testing scheduling problem (SFTSP) is a variation of the complex scheduling problem, which deals with the arrangement of the job sequence for the final testing process. In this paper, we present an actual SFTSP case includes almost all the flow-shop factors as reentry characteristic, serial and batch processing stages, lot-clusters and parallel machines. Since the critical equipment needs to be utilized efficiently at a specific testing stage, the scheduling arrangement is then playing an important role in order to reduce both the makespan and penalty cost of all late products in total final testing progress. On account of the difficulty and long time it takes to solve this problem, we propose a multi-objective optimization approach, which uses a lot-merging procedure, a new job-based encoding method, and an adjustment to the non-dominated sorting genetic algorithm II (NSGA-II). Simulation results of the adjusted NSGA-II on this SFTSP problem are compared with its traditional algorithm and much better performance of the adjusted one is observed.

• Periodical: Advanced Materials Research (Volumes 622-623)
• Pages: 152-157
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.622-623.152
• Online since: December 2012
• Authors: Yi Sun, Xin Wei, Shigeru Fujimura, Gen Ke Yang
• Keywords: Job-Based Encoding, Make Span, Multi-Objective Scheduling Problem, Penalty Cost, Reentrant Flow-Shop

References

[1] W.L. Pearn, S.H. Chung, A.Y. Chen and M.H. Yang: A case study on the multistage IC final testing scheduling problem with reentry. Int. J. Production Economics 88 (2004), pp.257-267.

DOI: 10.1016/s0925-5273(03)00186-5

[2] Pan JC and Chen JS: Mixed binary integer programming formulations for the reentrant job shop scheduling problem. Comput Opns Res 32 (2005), pp.1197-1212.

DOI: 10.1016/j.cor.2003.10.004

[3] S-W Choi and Y-D Kim: Minimizing makespan on a two-machine re-entrant flowshop. Journal of the Operational Research Society 58 (2007), pp.972-981.

DOI: 10.1057/palgrave.jors.2602220

[4] Jen-Shiang Chen, Jason Chao-Hsien Pan and Chien-Min Lin: A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Systems with Applications 34 (2008), pp.570-577.

DOI: 10.1016/j.eswa.2006.09.021

[5] Choi, S-W, Kim, Y-D and Lee, G-C: Minimizing total tardiness of orders with reentrant lots in a hybrid flow shop. International Journal of Production Research 43 (2005), pp.2149-2167.

DOI: 10.1080/00207540500050071

[6] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal and T. Meyarivan: A fast and elitist multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, Vol.6, No.2 (April 2002).

DOI: 10.1109/4235.996017

[7] Xin Wei, Wenqiang Zhang, Wei Weng and Shigeru Fujimura: Multi-objective local search combined with NSGA-II for bi-criteria permutation flow shop scheduling problem. IEEJ Transactions on Electronics, Information and Systems, Vol.132, Issue 1(2012), pp.32-41.

DOI: 10.1541/ieejeiss.132.32

[8] Hand-Min Cho, Suk-Joo Bae, Jungwuk Kim and In-Jae Jeong: Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Computers & Industrial Engineering 61(3) (October 2011), pp.529-541.

DOI: 10.1016/j.cie.2011.04.008