非等速平行機下之工作延遲個數最小化問題

Scheduling on uniform parallel machines to minimize the number of tardy jobs

林昆賢(Kun-Sian Lin)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200900310

摘要

本研究旨在探討非等速(Uniform)平行機製程下延遲工作個數最小化排程問題，目標為延遲工作個數（The Number Of Tardy Jobs）最小化，這是個NP-Hard問題；提出啟發式演算法與分支界限演算法；啟發式演算法主要是以工作焦點和機台焦點為主，機台焦點應用擴大Moore’s演算法解單機延遲個數最小化。分支界限演算法利用本研究所提出的二個下限值，並以最佳解和最佳的演算法做成果衡量；在各種參數水準下，以機台速率因子和交貨日期的寬緊二個水準的影響最為明顯。

關鍵字

啟發式演算法 ； 分支界限演算法 ； 延遲工作個數 ； 非等速平行機台

並列摘要

This study considers the problems of scheduling a given set of independent jobs on uniform parallel machines to minimize the number of tardy jobs. The problem is known to be NP-Hard. Efficient heuristic and branch and bound algorithms are developed. Heuristic algorithm is based on the job-focused approach and the machine-focused heuristic. The application of the machine-focused approach here amplifies Moore’s algorithm to solve the problem is which is given set of jobs on one machine to minimize the number of tardy jobs. Branch and bound algorithm will use the two lower bound algorithms. The performance of the optimum heuristic is H1. Under various kinds of parameter level, factor and delivery date wide to have two more urgent influence of competence the most obvious with machine station speed.

並列關鍵字

branch and bound algorithm ； heuristic algorithm ； uniform parallel machines ； the number of tardy jobs

參考文獻

Chen W.Y., Sheen G.J., Single-machine scheduling with multiple performance measures: Minimizing job-dependent earliness and tardiness subject to the number of tardy jobs. International Journal of Production Economics 109, 214-229, (2007).

Gupta J.N.D., Ruiz-Torres A.J., Webster S., Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time. Journal of the Operational Research Society 54, 1263-1274, (2003).

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

Jolai F., Minimizing number of tardy jobs on a batch processing machine with incompatible job families. European Journal of Operational Research 162, 184-190, (2005).

Koulamas C., Kyparisis G.J., Makespan minimization on uniform parallel machines with release times. European Journal of Operational Research 157, 262-266, (2004).