應用改善式啟發解與基因演算法求解晶圓針測排程問題之最大完成時間最小化

Abstract

晶圓廠針測區排程問題(Wafer Probing Scheduling Problem, WPSP)是平行機台排程問題的實例應用，另外也可應用在積體電路(IC)製造業以及其他的工業用途。求解目標式為最小化機台總工作量之晶圓廠針測區排程問題可能會導致平行機台間負荷的不平衡，而無法被現場監控者所接受。因此，在本篇論文中我們把目標式改為最小化最大完成時間之晶圓廠針測區排程問題並用一整數規劃問題來描述之。為了有效解決晶圓針測區排程問題之最大完成時間最小化，我們提出了結合初估產能負荷及晶圓廠針測區排程問題的演算法來做重複的求解之改善式啟發解法。此外，我們還提出了不同於以往的混合式基因演算法，其使用之初始母體為晶圓廠針測區排程問題的演算法所求得的排程解與部分排程保留導向的基因交配法來對問題作排程的流程。為了有效評估兩演算法在不同問題情境下的績效，本論文使用了四種影響晶圓廠針測區排程問題之特性來產生產生多組不同的問題。測試結果發現改善式啟發解在我們所設計的問題下其平行機台排程工件之最大完工時間比混合式基因演算法來的好。且當混合式基因演算法使用改善式啟發解之排程解當作初始母體時，其在某些問題情境下還可對改善式啟發解的排程解做更進一步的改善。

The wafer probing scheduling problem (WPSP) is a practical version of the parallel-machine scheduling problem, which has many real-world applications including the integrated circuit (IC) manufacturing industry and other industries. WPSP carries the objective to minimize the total machine workload, which might lead to unbalanced workloads among the parallel machines and be unaccepted for the shop floor supervisors. Therefore, we consider WPSP with the objective to minimize the maximum completion time and formulate the WPSP with minimum makespan as an integer-programming problem. To solve the WPSP with minimum makespan effectively, we proposed the improving heuristics, which add the expected machine load into savings and insertion algorithms for solving problems repeatedly. Besides, we also provide hybrid GA including initial population by WPSP algorithms and sub-schedule preservation crossover to solve the considered problem. To evaluate the performance of the two proposed approaches under various conditions, the performance comparison on a set of test problems involving four problem characteristics are provided. The computational result shows that improving heuristics are better than hybrid GA in scheduling solutions and velocities of WPSP with minimum makespan. When hybrid GA is using initial population by improving heuristics, it can make further improvement for the best solution of improving heuristics in some situations.