運用混合式演算法求解工件可分段加工之平行機台排程問題

Identical parallel machine Scheduling Problems with Distribtive Manufacture

陳宥任(You-Ren Chen)

指導教授 ： 蔡啟揚 ； 梁韵嘉 ； 吳炎崑

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

摘要

本研究深入探討工件的可分段性排程問題，但其分段數量和分段點事先已知，針對問題的可分段性提出部分分段演算法加以探討，期望產生近似最佳解，並且大幅降低產生解的時間，而全分段排程是將工件所有加工階段都視為獨立工件，其工件數量較多因此產生解的速度較慢，但相對的解的品質較佳；不分段排程所指的是依照原始工件數量進行排程，其工件數量較少因此產生解的時間較快，但相對的解的品質較差。
根據工件可分段特性發展混合式演算法，外層演算法在求解適合的分段情況，內層演算法在求解適合的排列方式，並利用模擬退火法和基因演算法互相搭配，發展四組內外迴圈混合式演算法進行求解。
藉由敏感度分析求取適合參數，並且依據問題大小和工件分段難易度設計不同規模測試例題，最後以三種類型共8組演算法驗證部分分段演算法的求解品質和效率，並且深入探討何種演算法適合運用在部分分段排程問題。

關鍵字

等效平行機台 ； 工件可分段性 ； 部分分段排程 ； 內外迴圈演算法

並列摘要

This research considers scheduling problems with jobs which can be divided into sub-jobs and do not required to be processed immediately following one another. It is assumed available cut points of a job into sub-jobs are fixed and known. Solving the problems with all sub-jobs that can be possibly divided from all jobs may find the best solutions. However, the run time can be long due to the large number of sub-jobs considered. Solving the problems without any job cut takes less run time, but solution quality may not be good.
Heuristic algorithms considering whether to or how to divide jobs are proposed in an attempt to find near-optimal solutions while reduce run time. The algorithms contain two loops which are executed recursively. The outer loop determines how jobs should be divided while the inner loop solves the scheduling problem given the sub-jobs established in the outer loop. Simulated annealing and genetic algorithm are applied for the inner and outer loops. Therefore, four inner-outer loop heuristic algorithms are established. Numerical experiment is conducted to determine the best parameter values for the heuristic algorithms. Examples with different sizes and levels of complexity are generated. Performance of the proposed algorithms is evaluated.

並列關鍵字

Identical parallel scheduling ； Dividable jobs ； Inner-outer loop algorithms

參考文獻

7. 陳百棧，2002，「以啟發式演算法求解時窗限制車輛途程問題」，中原大學產工業工程研究所，碩士論文。

11. 鄭志傑，2006，「基因演算法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與工程管理研究所，碩士論文。

1. 王苡宸，2008，「資源限制下比例式非等效平行機台排程問題研究」，元智大學工業工程與工程管理研究所，碩士論文。

3. 吳思農，2005，「模擬退火法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與工程管理研究所，碩士論文。

5. 范雅喬，2009，應用基因演算法於工件可分段處理下不相關平形機台問題之研究，碩士論文。