差異化生產流程之完工時間最小化

Abstract

S.M. Johnson 於1954 年率先提出流線型機組排程模式，由於其實務性應用 與完整的理論架構，吸引了許多研究學者對此模式進行深入之研究。本研究所探 討之差異化生產流程即屬於傳統流線型機組之延伸模型。此模型是將工作分成多 種類型，且每個工作都各有兩階段的作業需要處理。在第一階段中，所有的工作 都必須在同台機器上完成；而第二階段中，每個工作則需根據其所屬不同的類 型，進入不同的機器上操作。茲以汽車生產線為例，在第一階段中無論其車款類 型為何，每部車所需之零件都需要經由某台共同機器將他們組裝起來。在將汽車 組裝好後，第二階段則是要依照該車顏色塗裝之需求而進入負責該顏色塗裝的機 器以進行上色工作。此問題模型因其在第一階段共用同台機器，在第二階段則因 工作所屬類型之不同而在作業機器選擇上有所差異，故稱之為差異化生產流程。 此問題已經過證明為NP-hard，故本研究試圖發展演算法，其採用分支定界之策 略並根據問題之特性發展出下界及支配法則，期望其能更有效率的來求取最佳 解。本研究的實驗以三台第二階段機器與五台第二階段機器為模型所設計，並根 據實驗結果發現此演算法大幅提升了求解效率，確實帶來非常良好的效果。

Since Johnson’s first study on the flowshop scheduling setting in 1954, considerable research works have been done on this subject due to its practical as well as theoretical significance. In this thesis, we consider the differentiation flowshop model, which is extended from the traditional flowshop scheduling problem. In this model, we divide the jobs into various categories, each of which consists of two stages of operations. At the first stage, all jobs should be processed on the same machine. At the second stage, each individual product proceeds to a dedicated machine according to its type. Take the car production line as an example. We perform the assembly operations on a common machine regardless of the car types at the first stage. At the successive stage, the painting process is required to perform on different machines based on its specific color. Owing to the characteristics of the model, which has a common machine shared by all types of jobs at stage one and different types of dedicated machines at stage two, we call it the “differentiation” flowshop. This problem has been proven to be a NP-hard problem; therefore in this thesis, we develop a branch-and-bound algorithm with a lower bound and a dominance rule in order to derive the optimal solution in a more efficient way. Computational experiments are conducted for the models with three dedicated machines and five dedicated machines, respectively. The statistics demonstrate that the proposed algorithm can substantially improve the efficiency of finding optimal solutions to a certain range.