本研究考慮在有機台限制的非等效平行機台(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%.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。