以分枝界限法求解允許中斷 完全相同平行機總延遲時間最小化排程問題

A Branch-and-Bound Algorithm for Scheduling Preemptive Identical Parallel Machines to Minimize Total Tardiness Problems

何嘉展(Chia-Chan Ho)

指導教授 ： 廖經芳

朝陽科技大學/理工學院/工業工程與管理系/碩士(2016年)

摘要

本研究針對完全相同平行機(Identical Parallel Machines)允許中斷(Preemption)條件下，探討總延遲時間最小化(Minimizing Total Tardiness)排程問題，此排程問題可表示成Pm|pmtn|∑Tj ，此問題為NP-hard問題。
本研究利用分枝界限法(Branch-and Bound Algorithm)求解所探討的排程問題，以派工法則決定工件的完工順序，並根據Prot[12]所提出的線性規劃(Linear Program)求解所對應的PFS-like排程進而得到起始上限值，接著根據Schaller[7]提出的下限值演算法(LB4)，針對每一節點所代表之次問題求解下限值，並在分枝的過程中，刪除不必要的節點，增加求解的效率。
本研究探討完全相同平行機總延遲時間最小化排程問題，並透過電腦隨機產生大量的測試例題評估所發展上限值、下限值及整體分枝界限法之求解績效，並分析控制到期日寬鬆程度(τ)與控制到期日範圍(R)這兩個參數對問題困難度及求解效能的影響。
本研究之上限值演算法與最佳解之平均誤差為4.01%，下限值演算法與最佳解之平均誤差為41.55%，本研究所發展之分枝界限法可在有限時間內正確求解16個工件及5部機器的問題。

關鍵字

總延遲時間 ； 允許中斷 ； 完全相同平行機 ； 分枝界限法

並列摘要

This study examines the problem of scheduling preemptive jobs on identical parallel machines to minimize total tardiness.The problem can be expressed as Pm|pmtn|∑Tj , and is known to be NP-hard.
An efficient heuristic is developed for solving large sized problems. In this heuristic, a job completion sequence is first determined by a dispatching rule, and then the linear program from Prot[12] is used to find the corresponding PFS-like schedule. A lower bound scheme from Schaller[7] is also presented. Both of the proposed heuristic and lower bound are incorporated into a branch-and-bound algorithm to optimally solve small sized problems.
Computational results are reported. The branch-and-bound algorithm can handle problems of up to 16 jobs and 5 machines in size within a reasonable amount of time. The solution obtained by the heuristic has an average percentage deviation of 4.01% from the optimal value, while 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.

並列關鍵字

Total Tardiness Time ； Preemption ； Identical Parallel Machines ； Branch-and-Bound

參考文獻

[32]邱垂慶，「以啟發式演算法求解可中斷是總延遲時間最小化開放工廠排程問題」，碩士論文，私立朝陽科技大學工業工程與管理系，(2012)。

[1]Naidu, and Jaideep T., “A note on a well-known dispatching rule to minimize total tardiness,” Omega 31(2), pp.137-140 (2003).

[2]Alidaee, Bahram, and Suresh Gopalan.,“A note on the equivalence of two heuristics to minimize total tardiness,” European Journal of Operational Research 96(3), pp.514-517 (1997).

[3]Luo, Xiaochuan, and Feng Chu, “A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness,” Applied Mathematics and Computation 183(1), pp.575-588 (2006).

[4]Gupta, Skylab R., and Jeffrey S. Smith., “Algorithms for single machine total tardiness scheduling with sequence dependent setups,” European Journal of Operational Research 175(2), pp. 722-739 (2006).