具可分割工件與成批加工之混合型流線式生產暨等候時間限制之排程規劃

Abstract

現實的生產環境大多屬於混合型流線式生產排程 (Hybrid Flow Shop；HFS) ，因此本研究以多目標混合型流程式排程作為研究主題，其結合平行機台 (Parallel machine) 及流線型排程 (Flow shop) 兩者之特點，生產環境包括一個以上之加工階段 (Stages) ，每一階段都有一個或數個功能相同的機器執行加工，而工件 (job) 只需在每個階段中的任一台機器進行加工即可，其常為一個具高複雜度的組合問題。 在現實生活中混合型流線式生產排程問題常結合其他生產環境的限制與特性，例如：等候時間限制，其廣泛存在半導體晶圓廠、光電業、食品加工業和鋼鐵製造業的製造程序中，其指在限制的時間內在製品必須完成特殊製程的加工，若當等候時間超出時間限制時，在製品必須重新加工或報廢，嚴重影響工件品質和生產成本。此外還有可分割工件特性，由於不同的設備參數設定與製程設計，產品會有各自的可用機台的清單，根據此清單之限制，產品可拆解成數個部分同時在不同的機台上進行加工，而以上限制不僅增加此排程問題的複雜度，並提高求解的困難度。 本研究主要探討半導體及電子製造產業中常見的具可分割工件、成批加工與等候時間限制的混合型流線式生產排程問題，並將此問題建構為一混合整數規劃模型，目標為在最小化違反等候時間限制之數量下減少總完工時間 (total completion) 以期各個工件皆能在不違反等候時間限制的前提下以最少的時間完成製程。本研究以IBM ILOG CPLEX Optimization Studio V12.5.1驗證並求解數學模型，但由於數學規劃模型無法在有效的時限下求解較大規模的問題，因此進一步提出一套啟發式演算法，在短時間內求得合理的排程解。 本研究透過情境分析，將演算法與先進先出派工法進行各種情境的求解表現之比較，結果顯示所提出的演算法皆可有效求解不同情境的問題，可在不違反等候時間限制下減少所有工件的完工時間。

In this study, we consider a job-splitting and batching hybrid multi-stage flowshop with queue time constraint. A hybrid flowshop is composed of a series of production stages with several identical parallel machines at each stage. Jobs are processed through all stages in the same production flow. In many real world applications, there are often queue time limitations among process stages. Any violation of the process queue time constraint affects yield quality and also incurs significant scrap costs. Furthermore, Lot streaming combined job splitting with operations overlapping is one of the effective techniques used to implement the time-based strategy in today’s era of global competition. Besides, Batching in a manufacturing system is very common policy in most industries. The main reasons for batching are avoidance of set ups and/or facilitation of material handling. As a consequence, we purpose a hybrid flowshop scheduling problem which combines with job splitting, batching and queue time constraint in order to solve a complex combinatorial problem encountered in many real world applications. The objective is to minimize the total completion time of all of jobs under minimizing the number of jobs violating the queue time constraint. We formulate this problem as a mixed integer linear programming model (MILP) . Computational tests have shown that the total elapsed time resulting from the purposed formulation which solves the large-scale problem is costly. Therefore, we present a solution approach, a kind of heuristic, based on the characteristic of the problem. Numerical results show that this solution approach generates higher quality solutions in moderate computational time.