以啟發式演算法求解可中斷式總延遲最小化開放工廠排程問題

Heuristic Algorithms for Minimizing Tardiness in Preemptive Open Shop Scheduling Problems

邱垂慶(Chui-Qing Qiu)

指導教授 ： 廖經芳

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

摘要

排程(Scheduling)問題本身屬於組合最佳化問題(Combinatorial Optimization Problem)，許多研究證實大多數排程問題都為NP-hard問題，複雜度高且不易求解。
本研究是利用建構式啟發式演算法(Constructivist Heuristics)，一次建構一個工件為前提，建立其工件之完工順序，利用最大流量問題(Maximum Flow Problem)取代線性規劃，得到下一工件的最早可完工時間，求解總延遲時間(T)與總完工時間(C)最小化之開放型工廠問題。
本研究提出三種啟發式演算法來求得近似解，並利用最佳解和下限值來評估演算法之優劣。實驗結果顯示，針對小問題三種方法之整體平均誤差百分比分別為13.37、189.8及2198，而找到最佳解之比例分別為62.31、41.06及14.22，針對大問題三種方法之整體平均誤差百分比分別為0.19、9.24及184.92；在總完工時間最小化方面，此三種方法變成同一種方法，針對小問題整體平均誤差百分比為5.3%，找到最佳解之比例為60.72，而大問題演算法整體平均誤差百分比為1.39。

關鍵字

開放工廠 ； 延遲時間 ； 建構式啟發法 ； 允許中斷

並列摘要

Most scheduling problems are NP-hard combinational optimization problems. In other words, they are usually complex and difficult to solve.
In this thesis, we examine the preemptive open shop scheduling problem. It is a well-known NP-hard problem. In this thesis, constructive heuristics which schedule one job at a time are developed. In these heuristics, a maximum flow Problem, instead of a linear programming problem, is solved to determine the earliest possible completion time for the next job to be scheduled. Two types of performance measures are investigated in this thesis: total tardiness and total completion time.
Three heuristics are developed to solve the problem under consideration. For small problems, optimal solutions from LINGO are used to evaluate the performance of the proposed heuristics. For large problems, a lower bound is used to evaluate the proposed heuristics.
Computational results show that for small problems with tardiness performance measure the average relative percentage deviation is 13.37%, 189.8% and 2198%, respective, for the three heuristics. The percentage that the heuristic finds an optimal solution is 62.31%, 41.06% and 14.22%, respective, for the three heuristics. For large problems with tardiness performance measure the average relative percentage deviation is 0.19%, 9.24% and 184.92%, respective, for the three heuristics. The first heuristic is obviously the best among these three heuristics.

For total completion time performance measure, the three heuristics are exactly the same. The average relative percentage deviation is 5.3% and 1.39%, respectively, for small and large problems.

並列關鍵字

Constructivist Heuristics ； Total Tardiness ； Open Shops ； Preemptive

參考文獻

[2]Conway, R.W., Maxwell, W.L., and Miller L.W. (1967), “The-pry of Scheduling,” Addison-Wesley, Reading, MA.

[3]K.R. BAKER, and J.W.M. BERTRAND, “A dynamic priority rule for scheduling against due dates,” Journal of Operations Management, 3, 37-42 (1982).

[5]Dorit S. Hochbaum, Ron Shamir “Minimizing the number of tardy job units under release time constraints”, Discrete Applied Mathematics, Vol. 28, pp. 45-57, (1990).

[8]Gursel A. Suer, Zbigniew Czajkiewicz “ A heuristic procedure to minimize number of tardy jobs and total tardiness in single machine scheduling”, Computers & Industrial EngineeringVolume 23, Issues 1–4, November 1992, Pages 145–148.

[9]Johnny C. Ho, Yih-Long Chang “Minimizing the number of tardy jobs for m parallel machines”, European Journal of Operational Research, Vol. 84, pp. 343-355, (1995).