非等效平行機台在有機台限制下之總完工時間最小化排程問題

Minimizing total completion time on unrelated parallel machine with machine eligibility restriction

李俊緯(Chun-Wei Li)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200700586

摘要

本研究考慮在有機台限制的非等效平行機台（Unrelated Parallel Machine）下之排程問題，本研究目標為使總完工時間（Total Completion Time）最小化。本問題為NP-Hard，故本研究提出啟發式演算法與分支界限演算法；啟發式演算法主要是以能最早完工的工作進行指派，但是因為每一個排入的工作皆會對未排的工作造成影響，故本研究的啟發式演算法會利用已排與未排工作的估計總完工時間來加以判斷工作排入的位置；分支界限演算法會利用本研究所提出的改善後的下限值，來減少分支界限法所分支的節點數，加快其求解時間；經實驗後證明本研究所提出的啟發式演算法與最佳解整體平均誤差不會超過0.46%。

關鍵字

總完工時間 ； 非等效平行機台 ； 分支界限演算法 ； 啟發式演算法 ； 機台限制

並列摘要

This article considers the problems of scheduling a given set of independent jobs on unrelated parallel machines to minimize the total completion time. The problem is known to be NP-Hard. Efficient heuristic and branch and bound algorithms are developed. Heuristic algorithm is based on the solution of an assignment problem, and assign job by the earliest completion time. Each assigning job makes a significant influence to unscheduled jobs. Therefore, the heuristic algorithm will use the total completion time of scheduled and unscheduled jobs to be estimated total completion time for the assignment. Branch and bound algorithm will use the improve lower bound to reduce its nodes and execution time. Computational experience indicates that the deviation of the heuristic and optimal is not more than 0.46%.

並列關鍵字

unrelated parallel machine ； branch and bound algorithm ； machine eligibility ； heuristic algorithm ； total completion time

參考文獻

Azizgolu M. and Kirca O., Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Transactions, 31, 153–9, (1999).

Bruno J., E. G. Coffman Jr., and Sethi R., Scheduling in-dependent tasks to reduce mean finishing time. Communications of the ACM, 17, 382±387, (1974).

Ching-Fang Liaw, Yang-Kuei Lin, Chun-Yuan Cheng, Mingchin Chen, Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers and Operations Research 30, 1777-1789, (2003).

Chung-Lun Li, Scheduling unit-length jobs with machine eligibility restrictions. European Journal of Operational Research 174, 1325-1328, (2006).

Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, (1979).