有優先順序關係的兩台流線型機組之排程

Abstract

流線型機組排程問題自1954 年由D.S. Johnson 提出後，便受到許多研究學者的注目。本研究在此基礎下加入了支援性優先順序關係的限制條件，把所有需操作事務分為兩類：支援型項目與主要工作。此模型是來自於泡沫塑料（泡棉）化工公司的實際製程。在機組機器數量為兩台的情況下，設定第一台機器執行發泡程序，可產生多種不同類型的泡棉原料（支援型的小工作群組），第二台機器處理產品製造加工（主要工作）。當主要工作的所有支援項目在第一台機器上都執行完成後始被釋放，此工作才可以於第二台機器上被執行。所有工作於機器上的處理時間與相互關係為已知，在找出一個排程使得總完工時間能最小的目標。由於傳統流線型兩台機組求最小總完工時間的排程問題已經證明為NP-hard，現設定了支援性優先順序的限制使題目更為複雜，因此本問題亦是NP-hard。本論文將推導最佳解之下界值，並設計可行的刪除法則以提升分支與界定法之解題效率。為了可以在短時間獲致可用之排程，因此我們也設計了迭代區域搜尋法求取近似解。實驗結果顯示，分支演算法可求得在40 個工作與10 個支援項目時的最佳解，迭代區域搜尋法則明顯有不錯地效率求得200 個工作下的近似解，其誤差率小於0.109。

Since the introduction of the flowshop scheduling problem by Johnson in 1954, scheduling in flowshops has drawn much research attention. This thesis considers scheduling in flowshops with supportive precedence relations. The model originates from a real production context of a chemical factory that produces foam products. We reconstruct traditional two-machine model to divide all operations into two categories: supportive items and major jobs. Supportive items and regular jobs are to be processed by the stage-one machine and the stage-two machine, respectively. In the model, many different compositions of foam can be mixed in the foam blowing stage (on machine one), and products are processed in the manufacturing stage (on machine two). Each job on machine two cannot start until its supportive perations on machine one are all finished and machine two is not occupied. The objective is to minimize the total job completion time. The studied problem is strongly NP-hard. In this thesis, we propose a branch and bound algorithm equipped with a lower bound and two dominance rules. We also design a heuristic and a meta-heuristic (ILS) to derive approximate solutions. The branch and bound algorithm can solve instances with up to 40 jobs and 10 items. From the statistics of computational experiments, it seems very efficient and effective for large-scale problems with up to 200 by the ILS approach. And the average deviation is less than 0.109% from optimal values in small-scale problems.