考量機台維修與機器何適度限制之平行機台排程問題

Scheduling the Jobs and Maintenance Activity on Parallel Machines with Eligibility Constraints

洪崇賓(Chung-pin Hung)

指導教授 ： 沈國基

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

摘要

在此研究中，我們考慮當極小化最大延遲時間時，在機器合適度限制與變動機器維修時間下，n個不可分割的工作和m台平行機台的排程問題。每台機器累積一段工作時間後必須進行維修以確保作業正確性，每個工作也只能被安排在某些特定的機器上‧進行機器維修的時間點並未固定，在給定機台最大連續工作時間下，決定何時進行維修‧
在極小化最大延遲時間的目標式下，首先我們將允許工作切割的排程問題，利用網路流技術轉變成最大流量問題；接著我們提出一個演算法其結合網路流技術與二元搜尋法尋找其問題的最佳解；最後，將結果作為分支界限法的下界，求取不允許工作切割排程問題的最佳解‧
實驗的分析顯示，分支界限法所產生的節點數比例非常小，顯示提出的淘汰法則強而有力‧我們的演算法能用於12個工作和5台機器問題下而得到一個最佳解。

關鍵字

機器可用時間限制 ； 平行機台 ； 網路流 ； 分枝界限法 ； 機器維修工作 ； 機器合適度限制

並列摘要

In this paper we consider the problem of scheduling n independent and non-preemptive jobs into m parallel machines with eligibility constraints and variable machine maintenance intervals while minimizing the maximum lateness. Each machine is not always available for processing and should be shut down for maintenance to prevent malfunction. Each job is only allowed to be processed on a specific machine set. The maintenance of machine is not a fixed time interval known in advance, and the length of each interval is restricted to the given maximum continuously processing time.
To minimizing the Lmax firstly, we utilize a network flow technique 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 solve the problem optimally. Finally, we use the result of the preemptive scheduling problem as the lower bound of the proposed branch and bound algorithm to get the optimal solution of the study problem.
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 12 jobs and 5 machines.

並列關鍵字

parallel machine ； Network flow ； branch and bound

參考文獻

1. Adiri, I., J. Bruno, E. Frostig, A. H. G. Rinnooykan. 1989. Single machine flow-time scheduling with a single breakdown. ACTA Information 26 679-696.

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

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

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

5. Centeno, G., R. L. Armacost. 2004. Minimizing the makespan on parallel machines with release time and machine eligibility restricitions. International Journal of Production Research 42 1243-1256.