平行機台排程問題下考量工單釋放時間與機台適合度之最小化總完工時間

Identical Parallel Machine Scheduling Problem with Release Dates and Machine Eligibility Restriction to Minimize Total Completion Time

蔡承益(Cheng-I Tsai)

指導教授 ： 葉英傑

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

摘要

在現實環境中，每個作業在開始作業前，皆有所謂的備料時間，造成作業能開始執行的時間有所不同。除此之外，作業和機台(服務人員)被賦予不同的等級或條件，針對不同作業將會有不同機台負責執行但有著相同的服務速率。在此研究中，我們考慮當極小化總作業之完工時間時，在具有工單釋放時間與機台適合度的限制條件下有n個不可分割的工作和m台相同工作效率的平行機台排程問題。
求解此排成問題，我們使用分支界限法求得最佳解。在提出的基本作業排序規則下，首先提出了下限值的計算方式，計算方式是運用允許作業切割及使用最短剩餘工作時間者先排的規則來產生，計算所得的下限值將用來比較現有可行解並判斷該節點是否繼續分支，接著由Chu和Yalaoui (2006)所提出的減少分支規則做衍伸，改成屬於本篇文章能使用的規則，來減少不必要的節點產生進而提升求解效率。根據上述方法，我們將在此篇論文中將求解方式條列成演算法，並根據演算法的邏輯以java來協助我們求得題目之最佳解。
實驗分析結果，我們提出的分支界線演算法能正確的求解出Pm |rj,Mj |∑Cj 排程問題最佳解。節點也能有效率的產生，在2台機台15個工作的環境下相較於窮舉法，減少99.99%以上的節點數。我們的演算法在2機台環境下能求解到15個工作數，在有適合度條件下3機台環境能求解15個工作數而4機台環境能求解10個工作數。

關鍵字

排程 ； 平行機台 ； 機台適合度限制 ； 工單釋放時間 ； 分支定界演算法

並列摘要

In practice, there is a waiting time which is generated by preparing materials before job is scheduled, then jobs will be scheduled with different starting time. In addition, jobs and machines(servers) are classified into different level or with different conditions, then jobs will be assigned to own machines but still have same speed when they are processed. In this research, we consider the problem of scheduling n non-preemptive jobs on m identical parallel machines with release dates and machine eligibility restriction to minimize total completion time.
For the scheduling problem, we use branch and bound to find the optimal solution. Following basic proposition, we propose a lower bound first. With splitting job is allowed and using extended shortest remaining processing time rule to calculate the value of bound and compare with feasible solutions to determine the node is branched or not. We also propose dominance rules which are modified from Chu and Yalaoui (2006) to discard redundant nodes and improve efficiency of searching process. According above methods, we will present the branch and bound algorithm step by step and code the logistic to java programming and solve the scheduling problem.
In computational result, we validate our branch and bound can find the optimal solution for Pm |rj,Mj |∑C_j scheduling problem. Compare complete branching method with our branch and bound algorithm we can eliminate 99.99% created nodes efficiently. The solvable size of problem is up to 15 jobs with condition of 2 machines, 15 jobs with condition of 3 machines machine eligibility restriction and 10 jobs with condition of 4 machines.

參考文獻

Belouadah, H., Posner M.E., Potts, C.N. (1992), Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Applied Mathematics, 36, 213-231.

Baptiste, P. (2000), Scheduling equal-length jobs on identical parallel machines, Discrete Applied Mathematics, 103, 31-32.

Brucker, P., Kravchenko, S.A. (2008), Scheduling jobs with equal processing times and time windows on identical parallel machines, Journal of Scheduling, 11, 229-237.

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

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