頁籤選單縮合
題名 | A Branch-and-Bound Algorithm for Identical Parallel Machine Total Tardiness Scheduling Problem with preemption= |
---|---|
作者 | Liaw, Ching-fang; Liaw, Ching-fang; |
期刊 | 工業工程學刊 |
出版日期 | 20160900 |
卷期 | 33:6 2016.09[民105.09] |
頁次 | 頁426-434 |
分類號 | 494.542 |
語文 | eng |
關鍵詞 | Scheduling; Parallel machine; Branch-and-bound; Preemption; |
英文摘要 | This article examines the problem of scheduling preemptive jobs on identical parallel machines to minimize total tardiness. The problem is known to be NP-ard. An efficien the uristicis developed for solving large-sized problems. A lower bound scheme is also presented. Both of the proposed heuristic and lower bound are incorporated into abranch-and bound algorithm to optimally solves mall-sized problems. Computational results are reported. The branch-and-ound lgorithm can handle roblems of up to 16 jobs and 5 machines in size with inareasonable a mount of time. The olution obtained by the heuristich as an average percentage deviation of 4.01% from the optimal value, hile the initial lower bound has an average percentage deviation of 41.55% from the optimal value. Moreover, the heuristic finds approved optimal solutions for more than 45% of the problem instances tested. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。