流線型多階段生產排程與保養排程聯合調度問題探討

Abstract

排程問題中我們常常需要針對工作生產排程以及機台保養進行權衡取捨。在實際生產過程中，若是暫停生產工作並對機台進行維護，則生產排程會被延誤，可能會迫使工作無法如期完成。但若一直不對機台進行保養維護，則生產可能會由於機台們的機況差，導致生產所需時間延長，使得工作完成時間依然超過交期。因此，決定機台何時該生產、何時該維護才能最大化效益是一個值得討論的重要問題。 本研究針對流線型多階段生產排程與保養排程的聯合調度問題進行探討。在我們的問題中，於不考慮保養排程的狀況下，每台機器必須以同樣的順序處理所有工作，而機器在維護後工作生產所需時間將減少，本研究主要目標為最小化加權後的總延遲時間。我們證明此問題是一個 NP-hard 問題，並且發現混合整數規劃模型無法在實務上可接受的時間內找到最佳解。因此，我們提出了一種啟發式演算法來解決我們的問題。該演算法可分為三個部分，分別為初始化工作列表、工作交換以及保養安排，而此演算法是基於禁忌搜索演算法和貪婪演算法進行延伸。為了證明此啟發式演算法的有效性以及穩健性，我們生成了十三種情境，並使用我們的啟發式演算法與十五種不同的演算方法進行比較。結果顯示，我們的演算法可以有效地減少計算時間並求得近似解，且在訂單大多不緊急的情境中表現更好。

There is always a trade-off between production and maintenance. In practice, production has to be suspended for maintenance. This will cause the production schedule to pause and make some jobs not to be completed by the due times. However, continuous production without maintenance may lead to long processing times due to poor machine conditions, which may also result in tardiness. Therefore, the determination of the production and maintenance timing is an important issue worthy of discussion. In this study, we consider a joint production scheduling and preventive maintenance problem in a permutation flow shop environment. The job processing sequence must be the same on each machine, and the job production times will be reduced after machine maintenance. The objective is to minimize the total weighted tardiness. Because the problem is NP-hard, it is too time-consuming to obtain an optimal solution. Therefore, we propose a heuristic algorithm to solve our problem. This algorithm can be divided into three parts, which are job listing, job swapping, and maintenance scheduling, and is based on a combination of Tabu search and greedy search. To demonstrate the effectiveness and robustness of our algorithm, we generate thirteen scenarios and compare our heuristic algorithm with fifteen different methods. The results show that our algorithm can efficiently reduce the calculation time while obtaining good feasible solutions. Our algorithm performs especially good in the non-urgent scenario.