探討同時具有退化性工作與學習效果之單機 排程研究-以加權完工時間最小化為目標

Study on single machine scheduling problems with deteriorating jobs and learning effects to Minimize Total Weighted Completion Time

王群裕(Chun-Yu Wang)

指導教授 ： 楊達立

國立虎尾科技大學/管理學院/資訊管理研究所/碩士(2010年)

摘要

生產排程是製造業中重要的一環，當人們在各方面不斷追求進步，排程問題也跟著日趨複雜，因此有很多限制條件的問題產生，並受到研究學者的關注及探討。本篇論文主旨是在研究單機排程同時具有退化性工作(deteriorating jobs)及學習效果(learning effects)之問題，主要是針對加權完工時間最小化(Minimize Total Weighted Completion Time)問題指標來做績效衡量。本研究提出兩個模式來做探討，分別為加權最短作業時間(Weight Shortest Process Time, WSPT)及另外提出一個特例Λ-Shaped排法來與窮舉法求得最佳解進行比較，並推導出誤差界限值(worst-case error bound)。接著利用電腦程式執行小工作件模擬及分析，但對於現實生活或求解目標的規模及複雜度日亦增加。因此本研究最後利用啟發式求解模擬大工作件數與WSPT派工法則求其近似解，基因演算法(Genetic Algorithm,GA)是目前最佳化求解方式中相當優異的求解方法之ㄧ，故使用基因演算法來有效率的解決大工作件數之複雜排程問題。經由電腦模擬執行結果得到以下結論，在小工作件數n=6~11的情況下，WSPT及Λ-Shaped排法分別都能求解出近似最佳解。基因演算法求解方面，在大工作件數n=20,30,...,120的情況下，基因演算法一開始在短時間內能有效求解到近似WSPT排法的結果，但當工作件在n=80,90,...,120時，求解比值不只慢慢增大且消耗時間也隨著變長。

關鍵字

單機排程 ； 退化性工作 ； 學習效果 ； 基因演算法 ； 誤差界限值

並列摘要

A production scheduling is one of important issue in the manufacturing industry. When people pursue the progress continuously and the scheduling problem also becomes complicated. Therefore, there are lots of problems to happen and get scholar's discussion. This thesis subject is studying the list machine scheduling to have the problem that deteriorating jobs and learning effects at the same time. It is aim at the problem of Minimize Total Weighted Completion Time sign to measure. This research proposes two models to make the discussion, namely Weight Shortest Process Time and the other proposes a special case of Λ-Shaped method to compare with the exhaustive method, than infers the worst-case error bound. Finally, it is closer to solve the questions and answer approximate to an optimal solution by using the heuristic and WSPT. Genetic Algorithm is the best one of all the ways to solve problems efficiently. Then using the computer program to carry out the small jobs to imitate and analyze, but it is more complicated day by day for real life or solve the target. The implementation of the results by computer simulation the following conclusions, in the small number of jobs n = 6 ~11, both WSPT and Λ-Shaped sequenced are approximate to an optimal solution. From Genetic algorithms of view, when the large number of jobs n = 20, 30,…,120,the Genetic algorithms can approximate to an optimal solution effectively with WSPT at the beginning. On the other hand, when the jobs n = 80, 90,….,120, not only to solve the ratio of consumption gradually become larger and longer with time.

並列關鍵字

Single machine ； Deteriorating job ； Learning effect ； Genetic algorithmt ； Worst-case error bound

參考文獻

7. 湯璟聖,2003, “動態彈性平行機群排程的討論”,中原大學碩士學位論文。

9. 蔡仁皓,2007, “雙機流線型批次排程問題探討”,虎尾科技大學碩士學位論文。

10. 錢明淦,1998, “遺傳演算法應用於具有多種資源組態及資源限制專案計畫排程問題之研究”,元智大學碩士論文。

11. Biskup, D., 1999.“Single-machine scheduling with learning considerations” uropean Journal of Operational Research 115 ,173-178.

12. Browne S., Yechiali U.,1990. “ Scheduling deteriorating jobs on a single processor”Operations Research 38, 495-498.