具機器可用時間與機器合適度限制下之平行機台最佳化排程問題

Optimal Parallel Machine Scheduling with Machine Availability and Eligibility Constraints

廖祿文(Lu-Wen Liao)

指導教授 ： 沈國基

國立中央大學/管理學院/工業管理研究所/博士(2006年)

摘要

本論文主要在探討有限規劃時間幅度下，具機器可用時間與機器合適度限制下之平行機台最佳化排程問題。機器可用時間限制(Machine availability constraint)，意指每一機台具有服務時間之限制；而機器合適度限制(Machine eligibility constraint)，意指每一工件被限定在特定機台服務之限制。目前尚無研究同時考慮上述二限制，然而實務上如電視台廣告、半導體製程等等之排程問題，皆須同時納入此二限制。本研究首先將理論研究，延伸至含此二限制之問題，分別探討:一、極小化最大完工時間(Makespan, Cmax)之排程問題； 二、極小化最大延遲時間(Maximum lateness, Lmax)之排程問題。本論文最後將上述研究成果，推廣應用至工件的操作時間具不可分割特性下(Job preemption is not allowed)之平行機台排程問題，此為本論文第三個所探討的排程問題。
針對極小化最大完工時間之排程問題，我們利用網路流量分析方法(Network flow approach)，將排程問題轉換成多個最大流量網路問題(Maximum network flow problem)，並建構相對應之網路流量模型。每一個網路流量模型，描述了工件與機台可操作時間，在給定不同的「最大完工時間」下之相互關係。本研究利用二元搜尋方法與最大流量網路問題演算法，建構一多項式演算法(Polynomial time algorithm)。此一多項式演算法依序求解問題中之最大流量網路問題，以得到最小之「最大完工時間」。針對極小化最大延遲時間之排程問題，本研究利用臨界值(Critical values)之概念，與運用相類似上述極小化最大完工時間之排程問題之網路流量分析方法，提出兩階段之二元搜尋演算法來求解此一排程問題。本論文最後，將以極小化最大延遲時間之排程問題的結果，進一步應用到第三類排程問題上，以求解問題之下界值(Lower bound)。並依據工件與機台間之相互特性，整理出相關命題(Propositions)，發展分支定界法(Branch and bound algorithm)，以求取問題之最佳解。

關鍵字

機器合適度限制 ； 排程 ； 平行機台 ； 網路流量 ； 分支定界演算法 ； 機器可用時間限制

並列摘要

In this dissertation we consider the parallel machine scheduling problem with machine availability and eligibility constraints under a given planning horizon. Machine availability constraint indicates that each machine is not continuously available at all times throughout the planning horizon; machine eligibility constraint means that each job can only be processed on specified machines. We observe that there is a little published works in machine scheduling considered machine availability and eligibility constraints simultaneously. But this type of scheduling problem can be found in some practical environments, such as TV advertising scheduling and the testing of fabricated wafers in semiconductor manufacturing. In this dissertation, therefore, we extend the existing works to consider the following three types of scheduling problems with machine availability and eligibility constraint simultaneously. We first consider the first type of the scheduling problem where the objective is to minimizing the maximum makespan (Cmax). Then, we consider the second type of scheduling problem where the objective is to minimizing the minimum lateness (Lmax). Finally, we extend the result of the second type of scheduling problem to deal with the more general scheduling problem where the job preemption is not allowed.
For the minimization of Cmax, we utilize a network flow approach to formulate the scheduling problem into a series of maximum flow problem, and propose a polynomial time algorithm to solve the scheduling problem optimally. For the minimization of Lmax, we first introduce the concept of the critical values, and then apply the network flow approach for developing a two-phase binary search algorithm to solve the problem optimally. Finally, we extend the result of the second type of scheduling problem to derive a lower bound of the scheduling problem in which job preemption is not allowed; and then we investigate the characteristics of jobs and machines to find related propositions for developing a branch and bound algorithm to solve the scheduling problem optimally.

並列關鍵字

Scheduling ； Parallel machines ； Network flows ； Branch and bound algorithm ； Machine availability constraint ； Machine eligibility constraint

參考文獻

2. Ahuja, R.K., and J.B. Orlin (1989), A fast and simple algorithm for the maximum flow problem, Operations Research 37 (5), 748-759.

3. Blazewicz, J., M. Drozdowski, P. Formanowicz, W. Kubiak, and G. Schmidt (2000), Scheduling preemptable tasks on parallel processors with limited availability, Parallel Computing 26, 1195-1211.

4. Blazewicz, J., K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz (2001), Scheduling Computer and Manufacturing Processes (Springer, Berlin).

5. Blazewicz, J., K. Ecker, G. Schmidt, and J. Weglarz (1993), Scheduling in Computer and Manufacturing Systems (Springer, Berlin).

6. Centeno, G., and R.L Armacost (1997), Parallel machine scheduling with release time and machine eligibility restrictions, Computers & Industrial Engineering 33(1-2), 273-276.