| 摘要: | 在半導體環境中，考慮 n 個不可被分割的工件及 m 台平行機台的排程問題，根據每個工件都有不同的加工配方，相同的配方才可以做批量加工，而每一個批量加工的時間為該批量中加工時間最長的工件。我們針對每台機台對於配方裝載具有機器合適度，且不同工件會有時間上的限制，必須在一定時間內加工完畢，否則產生報廢現象，造成製程成本上的負擔。因此我們的研究目標是在這些環境條件限制下找出最小化最大完工時間，且減少總物料浪費。
為了求出此問題的解，本研究方法以基因演算法為底，加上傳統派車問題中的節省法，在染色體架構上結合批量特性及機器合適度，改良前人所研究的交換及突變理論，並加入節省法則於演算法中。接著以混整數規劃來比較傳統基因演算法及結合節省法則的基因演算法，探討在統計上是否有顯著效果。
根據研究我們發現在小問題的排程環境中並不會使結合節省法則之基因演算法造成顯著上的差異，但在大問題的排程環境中，有節省法則的基因演算法有效降低了完工時間及物料浪費，也因此找出更佳解。
;In the semiconductor environment, consider the scheduling of n jobs and m parallel machines. Each job has a different recipe, the same recipe can be batched together, and the batch processing time is given by the longest job processing time included in the batch processing. We have machine eligibility for each machine, and different jobs will have time window constraints, they must be processed within a certain time, otherwise scrapping will occur, causing a burden on the process cost. Therefore, our research objective is to find the minimum makespan under these environmental conditions and reduce the total waste of material.
In order to find a solution to this problem, this research methodology is based on genetic algorithm, coupled with the saving method in the traditional car dispatching problem, combined with batch characteristics and machine eligibility on the chromosome structure, and improved the crossover and mutation researches studied by previous researchers and add the saving method to the algorithm. Then we use mixed integer programming to compare the traditional genetic algorithm and the saving based genetic algorithm. Finally, we explore whether there is a statistically significant effect.
According to research, we found that in the scheduling environment of small problems, the saving based genetic algorithm will not cause a significant difference, but in the scheduling environment of the big problem, the saving based genetic algorithm effectively reduces the makespan and materials were wasted, so a better solution was found. |
