應用結合類神經網路與支援向量機之演算法縮減動態平行機台問題之最大工件完工時間

Abstract

在製造業上，考慮順序相依設置時間之動態平行機台排程問題是相當重要的，例如在晶圓針測、積體電路測試與封裝及製造薄膜液晶顯示器的配向膜塗佈…等製程中。在實務界裡，經常設定目標為最小化最大工件完工時間，使得機台產能有更佳的利用。然而，動態事件的發生，如工件來到時間的不確定性及當機等，對於排程上的影響是不可忽視的。因此，對於發展考慮順序相依設置時間之動態平行機台問題，且目標式為最小化最大工件完工時間的求解方法是一個相當值得探討的議題。本研究旨在探討上述之動態平行機台排程問題，將排程問題特徵化為數個因子：產品種類數、排程寬裕程度、設置時間比率與設置時間之範圍，再利用類神經網路與支援向量機等技術應用於現存之演算法，以求得績效較佳的排程解。同時，針對工件動態來臨之影響，提出了重排程準則與防止機台空閒之機制。透過計算結果之呈現，可以說明所提出方法績效優於一般現存之演算法。

The scheduling of jobs on parallel machines to reduce the setups of machine will be essential for the process including parallel machine with sequence-dependent setup time and being regarded as bottleneck, which includes in many manufacturing industries, such as wafer probing, IC testing, IC packing, and polyimide (PI) print in the TFT-LCD manufacturing. In the real world, it is important to minimize makespan, i.e. minimizing the maximum completion time and the balance of utilizing capacities of parallel machines. However, dynamic events such as jobs arrivals in uncertainty usually occur, from which the negative effects can not be neglected. Therefore, it is essential to develop efficient scheduling algorithms to reduce the number of setups among jobs and then the makespan of scheduling, in which a reactive mechanism such as rescheduling criteria is adopted by the algorithm to overcome the impacts from dynamic events. In this paper, we consider dynamic parallel machine problem with the sequence-dependent setup time and the objective to minimizing makespan, which includes jobs being classified into various product types and carrying with processing time, due dates, dynamic arrival, and machines required to be set up for different product types of jobs. With the consideration of the above properties, we characterize the dynamic parallel machine problem as several features and apply neural network and support vector machine to assist the considered algorithms to determine the value for parameter used in the cost function of algorithms, in which the problem features include job-type, tightness, setup time severity and setup time range. We also proposed idle preventing mechanism to keep machines working for reducing the makespan and enhancing the utilization of machines. A computation is also provided to demonstrate that our approach has remarkable performance than existing algorithm.