- 學位論文
探討具有學習效應與位置加權之單機排程
A Single-Machine Scheduling Problem with Learning Effect and Position-Weight
摘要
本論文主要探討具有時間相依的學習效應與位置加權的單機排程問題，研究如何將工作分配至機台的順序，主要目標為加權總完工時間最小化(Minimize Total Weighted Complication Time)。本研究主要探討加權最短處理時間(Weighted Shortest Processing Time；WSPT)的派工法則，並分析其最差情況誤差邊界(Worst-Case error bound)。本文在績效評估共可分為兩部份進行，第一部份為工作件數6到9，主要是使用窮舉法求得該問題的最佳解，並與WSPT派工法則進行比較，並分析它們的最差情況誤差邊界；第二部份為工作件數分別為20、30、40、50、60、70、80、90、100、110與120的工作件數下，使用基因演算法(Genetic Algorithms；GA)求其近似解，並與WSPT派工法則做比較。經由電腦模擬得到以下的結果，在工作件數6至9的情況下，當與時間相依之學習效應固定時，而工作位置的學習效應進行變動時，隨著學習效應的減少，雖然整體平均績效也隨著改變，但彼此差異性較小。在工作件數20、30、40、50、60、70、80、90、100、110與120的情況下，使用基因演算法進行求解亦能求得近似於WSPT派工法則的解。第三部分為使用WSPT派工法則所求得之解，作為基因演算法的起始解，進行運算。由於在現實的生產環境中較單機的生產環境複雜，因此未來可套用至其它更複雜的多機排程問題環境及使用其他的學習效應與位置加權值的生產模式。
並列摘要
This thesis mainly explores the time-dependent learning effect and position weighted single machine scheduling issue as well as studies how and the order of distributing work to the machine with the goal of minimizing Total Weighted Complication Time. This research mainly explores the dispatching rule of Weighted Shortest Processing Time (WSPT) and analyzes the Worst-Case error bound. This thesis’s results evaluation can be separated into two parts. The first part includes work number 6 to 9 mainly using the exhaustion method to obtain the best solution, compares with dispatching rule of WSPT, and analyzes the Worst-Case error bound. The second part includes work number 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, and 120 using Genetic Algorithms (GA) to find approximate solution and compare with dispatching rule of WSPT. The third part is to use WSPT dispatching rule’ solutions as the initial solution for Genetic Algorithms to calculate. Through computer stimulation to obtain the following results under work number 6 to 9: when time-dependent learning effect is constant, and work position’s learning effect is variable, as learning effect is decreasing, the overall average effect is changing as a result of learning effect’s change but the difference between the two is smaller. In work number 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, and 120, the solution found using Genetic Algorithms is approximately the same as dispatching rule of WSPT’s solution. Due to the practical production environment’s more single machine’s complicated production environment, can apply to other more complicated multi-machine scheduling issue and other learning effect and position weighted production mode in the future.