過去的相關文獻探討不相關平行機台排程問題的限制與假設條件,大都將資源設定為無限的情況下,但在業界中,工件在機台上加工時,往往需要其他特定的資源去配合操作,且可用資源的數量通常是有限制的,因此在考量排程問題時,加入資源限制的考量才是符合業界真正的情況。這一類的問題大多都是複雜度極高的組合最佳化問題,計算此類問題時,除了少數的題型外,利用最佳化的方法,大部分都需要相當長的時間才能取得最佳解,因此欲發展一個有效率的方式去取得最佳解。 本研究是使用最佳化方法中的分支界限法,依照資源限制以及考量機台的相依整備時間,建構一個以加權完工時間最小化為目標的不相關平行機台排程模式。為了增加求解的效率,本研究針對此問題,發展出不同的分支方式,一般的分支方法大都以工件去發展分支,而本研究根據例題的特性,利用資源去發展分支,並配合動態排程去選擇工件,利用基因演算法的近似最佳解做為上界值,並且根據問題的特性去發展分支界限法。本研究根據例題的大小以及例題的結構來設計不同的測試例題,藉著測試例題的結果,可以說明以資源去發展出來的分支界限法的求解效率較佳。
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.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。