在具機器可用時間與機器合適度限制之平行機台排程問題下運用分枝界限法尋求最佳解

Branch and Bound Algorithm for Parallel Machine Scheduling with Availability and Eligibility Constraints

林正峰(Cheng-Feng Lin)

指導教授 ： 沈國基

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

摘要

在此研究中，我們考慮當極小化最大延遲時間時，在具機器可用時間與機器合適度限制下，n個不可分割的工作和m台平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上，每個工作和機器上的每個可用的時間區段都有特定的服務水準，而只有當這個時間區段的服務水準高於或等於工作的服務水準時，此工作才能被安排在這個時間區段內。
我們提出一個分枝界限法去尋找這個問題的最佳解。首先，網路流技術用來闡述可分割工作的排程問題並將其轉變成最大流量問題。然後，我們提出一個演算法其結合網路流技術和二元搜尋法去找到其問題的最佳解，並將其結果作為我們的下限。最後，我們提出五個支配的法則來提升分枝界限法的效率。
實驗的分析顯示，所提出的淘汰法則是非常強而有力的並且在分枝界限法中只有非常小的比例的節點被產生。我們的演算法能用於20個工作和7台機器問題下而得到一個最佳解。

關鍵字

排程 ； 網路流 ； 平行機台 ； 分枝界限法 ； 服務水準限制 ； 合適度限制 ； 可用時間限制

並列摘要

In this paper we consider the problem of scheduling n non-preemptive jobs on m identical machines with machine availability and eligibility constraints when minimizing the maximum lateness. Each machine is not always available for processing and each job is only allowed to be processed on specific machines. Each job and availability interval of machines has a specific service level. Each job has to be processed at availability interval with the service level specified or higher one.
We propose a branch and bound algorithm to find out the optimal solution of this problem. Firstly, network flow technique is used to formulate the scheduling problem of the preemptive jobs into a series of maximum flow problems. Then, we propose an algorithm which combines a network flow technique and a binary search procedure to find an optimal solution for the problem and use this result as our lower bound. Finally, we propose five dominance rules to increase the efficiency of the branch and bound algorithm.
Computational analysis shows that the effectiveness of eliminating rules proposed is powerful and very low percentage of nodes is generated by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 20 jobs and 7 machines.

並列關鍵字

Scheduling ； network flow ； branch and bound ； parallel machine ； availability constraint ； service level constraint ； eligibility constraint

參考文獻

[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., P. Dell’Olmo, M. Drozdowski, and P. Maczka (2003), “Scheduling multiprocessor tasks on parallel processors with limited availability,” European Journal of Operational Research, 149, 377-389.

[5] Bollapragada, S., H. Cheng, M. Phillips, M. Garbiras, M. Scholes, T. Gibbs, and M. Humphreville (2002), “NBC’s Optimization System Increase Revenues and Productivity,” Interfaces, 32(1), 47-60.

[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.

[7] Centeno, G., and R.L. Armacost (2004), “Minimizing makespan on parallel machines with release time and machine eligibility restrictions,” International Journal of Production Research, 42(6), 1243-1256.