- 學位論文
以拉氏鬆弛法求解多站作業等候時間限制之排程問題
Flow shop production scheduling problem with queue time constraint using Lagrangian relaxation
摘要
在許多產業中，產品的製造多採用混合流程型(Hybrid Flow Shop; HFS)生產方式，如半導體製造以及薄膜電晶體液晶顯示器(Thin Film Transistor Liquid Crystal Display; TFT-LCD)製造。作業等候時間限制是其生產過程之特性，違反作業等候時間限制將會導致在製品的重工或者報廢。在實務上，混整數規劃(Mixed-Integer Linear Programming; MILP)模型被應用於即時控制系統(Real-time control system)，根據系統的狀態即時做出生產排程之決策；然而，此類型之混整數規劃問題屬於NP困難(NP-hard)性質，其求解時間會隨著系統內的在製品數量增加而呈指數成長，進而影響生產控制之效果。本研究考慮作業等候時間限制之生產排程問題，建構一個具「可分割」特性之混整數規劃模型。使用拉氏鬆弛法(Lagrangian relaxation)以拉氏乘數(Lagrangian multiplier)將部分限制式鬆弛，使問題分割為數個子問題(Subproblem)，其中每一個子問題皆可使用動態規劃(Dynamic programming)求解，並顯著的減少求解時間。拉氏對偶問題(Lagrangian dual problem)由次梯度演算法(Subgradient algorithm)進行求解，經過迭代運算，得到拉氏乘數之最佳值。數值測試的結果顯示，此求解方法可以在合理時間內求得最佳解或是可接受之近似解。此外，模擬結果顯示，本研究所提出之即時控制系統最多可減少83.72%的報廢量以及增加4.52%的生產量。
並列摘要
The hybrid flow shop scheduling (HFS) problem has drawn much attention in the past decades. Common examples of the HFS problem can be found in many industries, which usually accompanies with a lot of queue time constraints, the violations of which can lead to scraps. In practice, the mixed-integer linear programming (MILP) based real-time production control is applied, and the admission decisions are made based on the system status. However, the NP-hard nature of the production scheduling problem implies that the complexity of the problem substantially increases as the number of lots in the system increases, and the computational time would be too long to act as a good real-time approach. In this research, the Mixed Integer Programming with LAgrangian Relaxation (MIPLAR) method is proposed. In this method, a time-indexed MILP model with a separable structure for the production scheduling problem with queue time constraints is formulated. Lagrangian relaxation techniques are used to decompose the problem into job-level subproblems, which are solved by dynamic programming with significant improvement in computation time. The subgradient method is used to solve the Lagrangian dual problem. Computational results show that the optimal solution or a near-optimal solution can be obtained by using the Lagrangian relaxation techniques within a reasonable time frame. In addition, a simulation study shows that the MIPLAR method achieves the improvement in scrap count up to 83.72% and increases throughput up to 4.52% in a 4.6-month simulated case study.