以組合式班德切面求解多站作業等候時間限制之排程問題

Flow shop production scheduling problem with queue time constraints using combinatorial Benders’ cuts

李品寬(Pin-Kuan Lee)

指導教授 ： 洪一薰

國立臺灣大學/工學院/工業工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201702304

摘要

在實務的產線上，許多產品具有作業等候時間限制的特性(queue time constraint)，如半導體製造以及食品製造。混整數規劃(Mixed-Integer Linear Programming; MILP)常被使用於這類問題的求解，然而此類型的問題求解時間會隨著產品數量增加而成指數成長。本研究先利用大M法(big M method)建立一套具有等候時間限制的問題模型，並使用優先值設定(priority-order setting) 針對產品先進先出(FIFO, first in first out)特性進行簡化，同時也使模型對於產品先後順序的處理更具有彈性；接著利用組合式班德切面(CBC, combinatorial Benders’ cut) 將混整數模型拆解成兩個獨立的模型，分別為整數模型(integer part)以及連續型模型(continuously part)，並分開求解，CBC法亦可結合模型中指派問題的特性，搭配程式條件語法(if-then rule)後就能對多數大M限制式進行鬆弛，大幅減少限制式的數量，縮短求解時間。本研究亦發現在特定製程時間設定的即時控制系統上，混整數規劃模型可以利用階段性求解(phase-step solved)來達到與全域求解一樣的效果，階段性求解會使得決策變數大幅縮減，大幅減少找求解時間。最後模擬結果顯示，在本研究的即時控制系統中，結合上述方法可以較單純MILP短時間內得到更好的解，也確實能夠求解較大的問題，而長時間模擬的結果我們也比較了其他演算法，例如先進先出法(FIFO)、門檻值設定法(threshold)以及反應鏈法(reaction chains)，結果顯示CBC可以有更多的產出與較少的損壞。

關鍵字

生產排程 ； 流程式生產 ； 等候時間限制 ； 班德氏分解法

並列摘要

The queue time constraint is a common restriction in many production processes such as semiconductor production and food industry. The mixed-integer linear programming (MILP) is a common practice for the scheduling problem with queue time constraints. However, the complexity of MILP-based models increases enormously as the number of jobs increases. In our research, we formulate a model with queue time constraint by the big-M method. The first-in-first-out (FIFO) rule can be implemented by the priority-order setting in the proposed model. We solve the MILP with combinatorial Benders’ cut (CBC), where the MILP model is decomposed into two independent parts: integer and continuously parts. The decomposition technique allows us to speed up the computational time and combines the if-then rule to reduce redundant constraints with the big-M method. We also prove that the phase-step achieves the optimal solution and effectively reduces the computational time by only considering a short planning horizon. Finally, the simulation results demonstrate that the proposed method outperforms the MILP based mothed. In the long run, our mothed also outperforms other approaches such as FIFO, threshold, and reaction chains in terms of the number of scrap jobs and throughputs.

並列關鍵字

scheduling ； flow shop ； queue time constraint ； combinatorial Benders’ cut.

參考文獻

Lee, Y. Y., Chen, C. T., & Wu, C. (2005). Reaction chain of process queue time quality control. Semiconductor Manufacturing, 2005. ISSM 2005, IEEE International Symposium on, 47-50. IEEE.

Akkerman, R., Van Donk, D. P., & Gaalman, G. (2007). Influence of capacity-and time-constrained intermediate storage in two-stage food production systems. International Journal of Production Research, 45(13), 2955-2973.

Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.

Bernier, V., & Frein, Y. (2004). Local scheduling problems submitted to global FIFO processing constraints. International Journal of Production Research, 42(8), 1483-1503.

Canto, S. P. (2008). Application of Benders’ decomposition to power plant preventive maintenance scheduling. European Journal of Operational Research, 184(2), 759-777.