- 學位論文
同時具有學習效應與退化性工作之單機排程-考慮加權總完工時間最小化為目標
Single-machine scheduling with both deterioration and learning effects to Minimize Total Weighted Completion Time
摘要
本論文主要研究為同時具有學習效應及退化性工作的單機排程問題，探討如何將工作分配到機台的工作順序，目標是使得加權總完工時間最小化(Minimize Total Weighted Completion Time)。本研究主要探討當在加權最短作業時間的派工法則(Weight Shortest Process Time, WSPT)下，分析其最大誤差界限(worst-case error bound)。本文在評估績效方面共分為兩部分進行，首先在工作件數6到12，利用窮舉法獲得此問題之最佳解，來與WSPT派工法則比較，並且分析它們的誤差界限；其次在20到120之工作件數下，使用基因演算法(genetic algorithms,GA)求其近似解，並與WSPT派工法則做比較。經由電腦模擬執行結果得到以下結果，在6到12工作件數的情況下，當退化率固定，學習效應進行變動時，隨著學習效應的減少，雖然整體平均績效也隨著改變，但差異幅度較小。在20到120工作件數的情況下，使用基因演算法求解時亦能獲得近似WSPT派工法則的解。由於現實中生產作業的環境較單機台環境複雜，未來可延伸至更複雜的雙機台或多機台排程問題環境及其他的學習效應與退化率生產模式。
並列摘要
This thesis mainly studies the single machine scheduling problem of works that owns learning effects and deterioration and discusses the operation sequence concerning how to distribute works to machines. And the target of this thesis is to minimize total weighted completion time to make full use of the machine. This study mainly discusses the analysis of its worst-case error bound under the dispatching rules of the weight shortest process time. It conducts performance evaluation in two parts, for one part of works from 6 to 12; it adopts the method of exhaustion Brute-force method to get the optimum solution to the problem to compare it with the WSPT method, and analyzes the error margin between them. And for the other part of works from number 20 to 120, it adopts genetic algorithms to obtain an approximate solution and compare that method with the method. The following results are obtained from the simulation results of execution by the computer, for the sixth to twelfth works, when the deteriorated rate is fixed and the learning effects reduces, although the overall average performance also changes, the extent of difference is small. And for the works from 20 to 120, a solution that is approximate to the WSPT rule can also be obtained when using the genetic algorithms. Because the actual environment of production operation is more complicated than the environment of single machine, in the future, it can be extended into the environments of two-machine or multi-machine scheduling problem that are more complicated as well as other production modes with different learning effects and deteriorated rates.