資料重組法於生產排程之研究

Abstract

在生產排程的領域中，存在許多的問題其求取最佳解過程是極為費時的。為達成獲 得最佳解的目標，分支界定法是最常採用的列舉法之一。在設計分支界定法的過程中， 上下限函數扮演著決定演算法效率的重要角色。過去研究顯示經由諸如Lagrangian relaxation 等方式來發展界定函數需要精細的推算與設定multiplier，而且有時需要複雜 的數學技巧與嘗試才能獲致較佳之效果。在本計畫中，我們將應用資料重組的概念，針 對多個生產排程問題開發界定函數，一則可以作為理論研究，二則可以作為分支與界定 法操作時刪除節點之用。就我們以往經驗可以得知，對於某些排程問題，資料重組在減 少探索搜尋樹的運算上相當有效率；以雙機流線型求訂單平均等待時間之最小化 ( F2// ΣCi)這個典型問題為例，文獻中最佳演算法之解題能力約為35 個工作，資料重組 方法可將解題能力提昇至65 個工作。職是之故，我們的研究目標是要擴展此一重組的 方法至不同甚或更加複雜的排程問題上，我們期待藉此針對幾個文獻中重要的典型問題 求取最佳解，將文獻中已知演算法所可解的問題規模加以提昇。本計劃預期之成果，除 了是能夠於個別問題之解題提供更快速知方法，更可廣泛印證資料重組方法之效能，並 期可以建立一些成功經驗作為其他最佳化問題之參考。

In the area of production scheduling, there are numerous computationally challenging problems that demand exceedingly long execution time to derived optimal schedules. With the aim at deriving optimal solutions, branch-and-bound method is one of the most well adopted implicit enumerative approaches. In the design and development of branch-and-bound algorithms, bounding functions play a vital role in determining the efficiency of proposed algorithms. Nevertheless, developing bounding functions via such techniques as Lagrangian relaxation is some kind of art and sometimes requires sophisticated mathematics. In this project, we shall develop bounding functions for several difficult scheduling problems using a new scheme, called data rearrangement. Our previous experiences suggest that for some scheduling problems, data rearrangement is effective in reducing the computational efforts required for exploring the enumeration trees. As an example, data arrangement technique can successfully solve the classical total completion time minimization problem in a two-machine flowshop with 65 jobs, while the best algorithm known in the literature can deal with up to 35 jobs. Our study is to extend and sharpen the rearrangement techniques to scheduling problems with different, even more complicated, structures. For the targeted problems, we expect to override the largest scales that have been optimally solved in the literature. Our endeavors will not only make the related techniques more solid and enrich the application success of data rearrangement, but also provide possible clues to the resolution of some other combinatorial optimization problems.