彈性零工生產與搬運排程問題及啟發式求解法

Abstract

本研究首先定義彈性零工生產與搬運排程問題，再提出具遺傳演算優化的求解法，有效降低排程系統中產品的最大完工時間。已知各產品的加工作業順序、不同候選機台和加工時間、及搬運設備搬運時間，模擬實務工廠生產。目標是規劃一套最佳的加工作業順序及選定加工機台和搬運設備，最小化產品的最大完工時間。然而計算產品完工時間必須由加工作業、機台加工及搬運設備的細節排程中求得，因此提出一精確的排程演算程序模擬生產系統中的排程。本研究除了提出貪婪式的經驗求解法外，也使用遺傳演算法求解問題，並在遺傳演算法初始解中嘗試加入適當比例的貪婪解，以提升求解效率。為了驗證演算機制的效能，以(Liang et al., 2012)文獻做測試範例並另自創大型複雜標竿問題進行驗證。結果顯示本研究提出的遺傳優化演算法能顯著地減少產品的最大完工時間，也較貪婪式經驗求解法求得更佳的解。此外，因實務上有不同機台布置及不同加工特性產品，本研究也測試在不同情境下的搬運設備分析，提供使用者一項做決策的工具。

This paper defines Flexible Job and Material Delivery Scheduling Problem and uses genetic algorithm to construct a solving method, effectively reduce the maximal completion time of products in the system. Before simulating a schedule, the production process sequence of each product, the different candidate machines and processing time, and the handling time of handling equipment are known. The goal is to minimize product maximal completion time by planning an optimal set of processing operations, selected machines and handling equipment. However, the calculation of product maximal completion time can be evaluated only when detailed schedules of processing operations, machines and handling equipment are available. This work derives a concise simulation algorithm to generate a schedule in the production system. Our research proposes not only greedy heuristic method but also genetic algorithm to solve this problem. This study also attempts to add an appropriate proportion of greedy solution in the initial solution of the genetic algorithm to improve the efficiency of the solution. In order to verify the effectiveness of each methods, the academic literature (Liang et al., 2012) and another large-scale complex standard problem was verified. After applying this problem to test several benchmarks, the results shows that our research can significantly reduce the maximal completion time of products and obtain a great solution. The results also has a better performance than greedy heuristic method. In addition, there are different machine layout and different processing characteristics of product in practice. Our research tests the analysis of handling equipment in different situations and provides users with a decision-making tool.