考慮機台限制下平行機台之工作延遲個數最小化問題

Minimizing number of tardy jobs on identical parallel machines with machine eligibility restriction

林伶容(Ling-Jung Lin)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2008年)

https://doi.org/10.6840/cycu200900313

摘要

本研究探討有機台限制下平行機台之排程問題，研究目標為工作延遲個數最小化。機台限制是指並非所有機台都可加工所有的工作。本問題為NP-Hard，故本研究提出了五個啟發式演算法與分支界限演算法；啟發式演算法分為以工作為基準和以機台為基準兩種概念。以機台為基準的演算法是延伸Moore在單一機台對工作延遲個數最小化的問題所提出的方法。分支界限法會利用本研究所提出的下限值，來減少分支界限法所分支的節點數，加快其求解時間。實驗結果可知在五個演算法中，以啟發式演算法二和三的求解時間最快，但求解品質則是啟發式演算法五最好。

關鍵字

工作延遲個數 ； 機台限制 ； 等效平行機台

並列摘要

This research explores identical parallel machines with machine eligibility and the main purpose is to minimize the number of tardy jobs. Machine eligibility means not all machines can process all the jobs. The problem is known to be NP-Hard. This paper proposes five heuristics and branch and bound algorithm. Five Heuristics are based on job-focused approach and machine-focused approach. The machine-focused approach heuristic is an extension of Moore’s algorithm to solve the number of tardy jobs on one machine problem. A lower bound is proposed for the branch and bound to reduce its nodes and execution time. Experiment results show that the CPU time for heuristic two and three is less than the others, and the solution for heuristic five is the best.

並列關鍵字

number of tardy jobs ； machine eligibility ； identical parallel machine

參考文獻

Baptiste, P., Peridy, L. and Pinson, E., 2003, A branch and bound to minimize the number of late jobs on a single machine with release time constraints. European Journal of Operational Research Vol. 144,1-11

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

Garey, M.R. and Johnson, D.S., 1979, Computer and intractability:A guide to the theory of NP-completeness, Freeman, San Franciso.

Ho, J.C. and Chang, Y.L., 1995, Minimizing the number of tardy jobs for m parallel machines. European Journal of Operational Research Vol. 84, 343-355

Kise, H., Ibaraki T. and Mine, H.,1978, A solvable case of the one machine scheduling problem with ready and due times. Operations Research Vol. 26, No. 1, 121-126