以分枝界限法求解允許中斷且工件起始時間不同的相同平行機排程問題

A Branch-and-Bound Algorithm to Minimize Total Completion Time on Identical Parallel Machines for Scheduling Preemptive jobs With Release Dates

林淑雁(SHU-YEN LIN)

指導教授 ： 廖經芳

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

摘要

總完工時間為工廠生產排程中評估在製品成本的績效指標，降低總完工時間即可有效的減少在製品的數量，進而降低生產成本。
本研究將探討完全相同平行機器在作業處理允許中斷且工件有不同起始時間的條件下，求解總完工時間最小化的排程問題，以排程符號表示為P_m |pmtn,r_i |∑_(i=1)^n▒C_i ，此問題已被證明為NP-hard問題。
本研究使用Kravchenko (2009)的線性規劃及Baptiste (2009)的下限值演算法並針對本研究做修改，與本研究設計之上限值演算法，做完整的最佳解法，並加以分析。
本研究發展之上限值演算法及下限值演算法，可在分枝過程中有效的刪除無用節點，加快求解速度；最後透過電腦產生大量隨機的測試例題，針對上限值演算法、下限值演算法及整體分枝界限法進行績效評估。
本研究之上限值演算法之結果與最佳值平均誤差為0.18%，且上限值演算法可找到超過80%問題的最佳解，下限值演算法之結果與最佳值平均誤差為5.36%，求解能力較不理想。

關鍵字

平行機排程 ； 總完工時間 ； 線性規劃 ； 分枝界限法

並列摘要

The total completion time is an important performance criterion for production schedules. Reducing the total completion time can reduce the number of WIP effectively which can then reduce production costs.
This study aims to investigate the identical parallel-machine total completion time scheduling problem with preemption and release times.
This problem is denoted by P_m |pmtn,r_i |∑▒C_i , and is proved to be NP-hard.
In this study, we present a branch-and- bound algorithm in which the linear program for a given job completion sequence from Kravchenko(2009) and the lower bound from Baptiste (2009) are used along with an upper bound designed by the author. A large number of randomly generated problems are used to evaluate the performance of the proposed algorithm.
The upper bound has an average percentage deviation of 0.18%, and it equals to the optimal value for over 80% of the problems. The lower bound has an average percentage deviation of 5.36%. The proposed branch-and- bound algorithm can solve 11x4 problems within a reasonable amount of time.

並列關鍵字

Parallel Machines ； Total Completion Time ； Linear Programmnig ； Branch-and-Bound

參考文獻

[35]　陳盈如，「以改良式分枝界限演算法求解允許中斷開放式工廠排程問題」，碩士論文，私立朝陽科技大學工業工程與管理研究所，台中(2013)

[36]　曾佳盈，「以分枝界限法求解可中斷式開放工廠排程問題」，碩士論文，私立朝陽科技大學工業工程與管理研究所，台中(2011)

[11]　Xiong, Bo, and Christine Chung., Completion time scheduling and the WSRPT algorithm, Combinatorial Optimization Springer Berlin Heidelberg, pp.416-426(2012).

[1]　Baptiste, Philippe, et al. " The complexity of mean flow time scheduling problems with release times". Journal of Scheduling , Vol. 10, No. 2

[2]　 Bellenguez-Morineau Odile, et al. " A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines", Journal of Scheduling, Vol. 18, No. 3, pp. 299-304(2014).