應用分支界限法於資源限制下的不相關平行機台排程問題

A Branch and Bound for Unrelated Parallel-Machine Scheduling Problems with Constrained Resources

賴佑華(Yu-Hua Lai)

指導教授 ： 蔡啟揚

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

摘要

過去的相關文獻探討不相關平行機台排程問題的限制與假設條件，大都將資源設定為無限的情況下，但在業界中，工件在機台上加工時，往往需要其他特定的資源去配合操作，且可用資源的數量通常是有限制的，因此在考量排程問題時，加入資源限制的考量才是符合業界真正的情況。這一類的問題大多都是複雜度極高的組合最佳化問題，計算此類問題時，除了少數的題型外，利用最佳化的方法，大部分都需要相當長的時間才能取得最佳解，因此欲發展一個有效率的方式去取得最佳解。
本研究是使用最佳化方法中的分支界限法，依照資源限制以及考量機台的相依整備時間，建構一個以加權完工時間最小化為目標的不相關平行機台排程模式。為了增加求解的效率，本研究針對此問題，發展出不同的分支方式，一般的分支方法大都以工件去發展分支，而本研究根據例題的特性，利用資源去發展分支，並配合動態排程去選擇工件，利用基因演算法的近似最佳解做為上界值，並且根據問題的特性去發展分支界限法。本研究根據例題的大小以及例題的結構來設計不同的測試例題，藉著測試例題的結果，可以說明以資源去發展出來的分支界限法的求解效率較佳。

關鍵字

分支界限法 ； 不相關平行機台 ； 有限資源

並列摘要

When considering machine scheduling problems, it is usually assumed that only available machines are required for the processing of jobs. However, in many practical cases, additional resources such as operators, part holders, or tools, are needed when processing jobs and the amount of these resources are limited. Therefore, one needs to put resource constraints into consideration in order to form feasible job schedules. Parallel machine scheduling problems become more complicated when resource constraints are involved. The goal of this study is to develop effective algorithms that can find optimal solution to the problems with reasonable computation time.

This study applies branch and bound approach on unrelated parallel machine scheduling problem with constrained resources. Sequence-dependent setup time is also considered and the objective is to minimize weighted completion time. Two algorithms are developed. In the first algorithm, the search tree is formed according to the assignment of jobs on machines. The second algorithm, on the other hand, is resource oriented. That is, the branches are formed as resources are assigned to machines. The solutions obtained by applying genetic algorithm are used as the upper bounds in the branch and bound algorithms. A variety of numerical examples are designed with different sizes and resource strength. Numerical experiments are conducted to evaluate the performance of the proposed algorithms.

並列關鍵字

branch and bound ； unrelated parallel-machine ； constrained resources

參考文獻

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

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

7. 蕭陳鴻，「基因演算法於非等效平行機台排程之應用」，元智大學工業工程研究所，碩士論文 (2000)。

8. 葉麗芬，「雙目標非等效平行機台排程問題之探討」，元智大學工業工程與管理研究所，碩士論文 (2001)。

10. Allahverdi, A. and J. Mittenthal, “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time,” Naval Research Logistics, 41, 677-682 (1994).