機器具可用區間限制與工件迴流特性之零工式生產排程問題

Job Shop Scheduling with Machine Availability Constraint and Recirculation Jobs

黃偉婷(Wei-ting Huang)

指導教授 ： 沈國基

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

摘要

本研究主旨將探討機器具可用區間限制以及工件迴流特性下之零工式生產排程(Job Shop Scheduling)問題。在機器具可用區間限制下，在傳統零工式生產排程中，一般假設機台作業時間為連續性不中斷的情形，但在實際的生產排程環境中，機器設備會執行一段時間後，機台會做維修保養，在生產過程中發生故障造成工廠成本的損失；而工件迴流(Recirculation Jobs)現象係指工件重複拜訪機器兩次以上之情形。因此，本論文將主要研究方向為如何生產一個合理且最佳的排程，並極小化最短完工時間(makespan)。
本研究先將機器具可用區間限制轉成虛擬作業，並利用離散圖形(Disjunctive Graph)呈現。為了提供最佳解，本文採用分支定界法(Branch and Bound Algorithm)來求解此類問題。首先，安排最少虛擬作業於各機台中並加入no-wait特性，並修正虛擬作業和其他作業間排定情形；後來將利用分支法則，決定分枝的作業節點並計算下界值。在過程中，分支過程可能為不可解，透過Propositions發展新增虛擬作業方式來變成可行解。反覆持續更新分支節點的完工時間以及下界值，如此便可順利的使用刪除法則剔除毋須的分支，以求得最佳配置與最佳順序。
實驗結果透過窮舉法和分支定界法相比較，可知道14題測試題中兩者方法計算最佳解的結果為相同。而評估分支定界法的效率，分為2組實驗測試，每組均有6題測試題，透過評估本文在刪除節點數有比窮舉法來的有效率。

關鍵字

零工式生產 ； 分支定界法 ； 機器可用區間限制 ； 迴流

並列摘要

In the thesis we consider the job shop scheduling with machine availability restrictions and recirculation jobs while minimizing the makespan. Each machine is not continuously available at all time. On the other hand, each machine is not always available for processing. Besides, each job may visit a machine more than once and has to be processed at an available interval.
We propose the branch and bound algorithms to solve the scheduling problem optimally. First, we decide that the minimum number of each machine unavailable interval. Then, we modify disjunctive graph technique to model the scheduling problem with the dummy jobs that is denoted by each machine unavailable interval. Also, each dummy job is no-wait attribute. Second, we develop the branching scheme to generate the entire tree and use propositions to transfer infeasible solutions to feasible. Then, determine the lower bound of the makespan as the length of the longest path. Finally, we use algorithm to recalculate the scheduling problem until find an optimal solution.
Experimental designs are used to evaluate and analyze the performance of the algorithm. Computational analysis shows that the lower bound proposed is effective and can eliminate more than 60% node when the total operation numbers. The results show that the lower bound affect the solution time used by branch and bound algorithm.

並列關鍵字

Machine available interval constraint ； Reentrant ； Job shop scheduling ； Branch and bound algorithm

參考文獻

1. Bartusch, M., R.H. Mohring, and F.J. Radermacher. 1988. Scheduling project networks with resource constraints and time windows. Annals of Operation Research 16 201-240.

2. Birger, F., K. Neumann, and C. Schwindt. 2001. Project scheduling with calendars. OR Spektrum 23 325–334.

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. Brucker, P., A. Drexl, R. Mohring, K. Neumann and E. Pesch. 1999. Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112 3–41.