考慮等候時間上限與限期完成之保養的彈性零工式排程問題

Abstract

工作生產排程和機台保養之間的權衡取捨對於解決排程問題至關重要。當暫停生產工作進行機台維護時，使得生產的排程延後，也可能使得預定好的訂單無法如期交貨。從另一方面來看，如果持續進行生產而輕忽機台的保養維護，機台可能會嚴重耗損，進而影響產品品質，也可能有無法預期的災難性損失出現，其中也包含了嚴重的交期延誤。因此，本研究針對生產排程與保養排程的聯合調度問題進行探討，聚焦在彈性零工式的生產排程並考慮一個工作可能會通過一個工作站數次的情境。在我們的問題設計上，需要被維修的機台都是已知的，在指定期限前必須完成指定時間長度的保養，但保養的開始時間點則由決策者決定。我們的問題會同時考慮每個製程步驟之間的等候時間上限。在上述情境設定下，本研究目標為最小化加權後的總延遲時間。

由於混合整數規劃模型無法在合理的時間內找到最佳解，我們提出了一種基於貪婪演算法延伸的啟發式演算法來解決我們的問題，同時我們也使用了基因演算法來提升演算法的表現。為了證明此啟發式演算法的有效性，我們在四種環境設定七種情境的實驗來檢驗演算法的表現。結果顯示，我們的演算法在工作不會經過重複製程步驟的情況下表現較佳，並且可以有效地減少計算時間。最後，我們也使用台灣面板公司提供的資料透過我們提出的演算法進行排程，結果也顯示了我們的驗算法在實務上的可用性。

A balance between production scheduling and machine maintenance is crucial. Halting production temporarily for maintenance can cause schedule delays. However, neglecting machine maintenance can result in significant wear and tear, affecting product quality and potentially leading to unforeseen catastrophic losses. Therefore, this study aims to optimize production and maintenance scheduling in a job shop and consider the scenario where a job may pass through a specific station multiple times. We assume that the due times for completing fixed-length maintenance on some machines are given, and the planner may determine when to start each maintenance. The objective is to minimize total weighted tardiness.

We propose a heuristic algorithm based on the greedy algorithm because the mixed integer programming model may fail to find the optimal solution within a reasonable time. Additionally, we use the Genetic Algorithm to enhance the performance of the algorithm. To demonstrate the effectiveness, we conduct experiments in four different environmental situations with seven scenarios to evaluate its performance. The results show that our algorithm performs better with no recirculation situation and significantly reduces computation time. Furthermore, we apply it to a real-world case of a manufacturer in Taiwan, and the experimental results confirm the applicability of the algorithm in the practical scenarios.