具多重設置時間以及工作時間之彈性零工型生產排程

Abstract

隨著科技水平持續的在進步，越來越多種類的產品需求也隨之產生，加工製造業也需要因應時勢而不斷的創新發展，以加工製造業來說，彈性零工型生產排程(Flexible Job Shop Scheduling)是目前常見到的生產模式，在此生產模式下，各種不同的工件皆有其各自需要進行的加工流程，即加工所需進行的作業及作業加工的順序的不同，而彈性則指的是可進行某項作業之加工機台不會只有單一機台。除此之外，由於各工件的性質或是作業加工時的條件不同，作業彼此之間也會需要設置時間來進行機台上的調整，並且此設置時間也會因為需要進行之設置種類不同，而產生可以進行預先處理設置時間以及不可預先處理設置時間之情況，可預先處理設置時間之定義為當某工件尚處於上一階段之作業加工，但欲進行下一階段之作業加工之機台已為閒置的狀態，此時便可以預先來進行設置以及調整。再者，在實際的生產環境之中也需要考量到其生產線之上下班時間，機台到了下班時間就必須進行關機直到隔日之上班時間在重新開機。 本研究針對彈性機台零工型生產排程問題，並且將不同種類的設置時間以及上下班時間納入考量，以最小化總延遲時間為目標，使用作業之先後順序以及指派之機台關係作為決策變數，建構一混合整數線性規劃模型，並利用此數學模型進行求解。儘管如此，在進行較大規模之問題求解時，混合整數線性規劃模型無法在有限的時間求出合適的解，因此本研究將針對此問題，結合派工法則、基因演算法以及禁忌搜索法建立一混合啟發式演算法，首先透過派工法則得到一有效之初始解，再來利用此初始解配合基因演算法來尋找最佳解，最後透過禁忌搜尋法來找尋更優的解。本研究也將針對混合整數線性規劃模型、混合啟發式演算法以及其他既有之演算法所求得之結果以及求解時間進行分析以及比較，結果顯示本研究所建立之混合啟發式演算法能夠在有限之求解時間下，找到一最佳的排程結果。

With the continuous advancement of technology, a variety of product demands have come out. The manufacturing industry must have constant innovation and development. Flexible Job Shop Scheduling (FJSS) is an ordinary production type in the manufacturing industry. Under this production type, various jobs all have their own specific processing routes, which means the required operations and their sequences are different. Flexibility refers to the fact that multiple machines can perform the same operation, rather than just a single machine. Additionally, due to the property of different jobs or the conditions during processing, set-up times are required for adjustments between the operations. These set-up times can be classified into pre set-up and non-pre set-up times. Pre set-up time is defined as the time when a job is still being processed in the previous operation, while the machine which can process the next operation is idle. It can start the set-ups and adjustments before the previous operation is done. Furthermore, it is necessary to consider the working hours of the production line in the actual production environments. Machines must be shut down after working hours and restarted the next working day. This research focuses on the Flexible Job Shop Scheduling problem which takes the different types of set-up times and working hours into account. The goal is to minimize the total delay time. This research uses operation sequences and machine assignments as decision variables to construct a Mixed-Integer Linear Programming (MILP) model and solve the FJSS problem by using this mathematical model. However, for larger-scale problems, the MILP model cannot find suitable solutions within a limited time. Therefore, this study combines dispatching rules, genetic algorithms, and tabu search to propose a hybrid heuristic algorithm. First, an effective initial solution is obtained through dispatching rules, then this initial solution is used with genetic algorithms to search for the best solution. Finally, tabu search is employed to find an even better solution. This research also analyzes and compares the results and the solving times obtained from the MILP model, the hybrid heuristic algorithm, and other existing algorithms. The results indicate that the hybrid heuristic algorithm proposed in this research can find the best scheduling result within a limited solving time.