用混合型基因和聲搜尋演算法於有自動倉儲設備之迴流式混合流程型生產排程問題

Abstract

隨著工業產品的多樣化，工件於加工過程中常須要迴流至前一階段選多個機台之一做下個階段加工的頻率增加，致使此類迴流式混合流程型生產的環境越為複雜，因此若能妥善安排此環境下生產排程將可大幅提升生產效率。過去相關研究大多考慮機台前緩衝區可擺放的再製品容量是無限的，即使設定緩衝區容量是有限的，仍會產生大量再製品存放的複雜問題。實務上，先進的自動搬運系統會使用自動倉儲(stocker)來暫時擺放再製品，然而過去未曾有流程排程問題之研究將自動倉儲納入。因此本研究在迴流式混合流程型生產環境下加入過去研究從未被考慮的自動倉儲以解決大量再製品存放的問題。為使此問題更符合實際的工廠環境，問題設定上考慮從自動倉儲搬運再製品到每個工作站的傳送時間，目標設定上考慮最大完工時間和平均完工時間雙目標最佳化。此問題涵蓋過去相關問題亦是NP-hard，因此適合採用萬用啟發式演算法求解。因此，本研究首先建立此問題之數學模型，並提出啟發式演算法。和聲搜尋演算法(Harmony Search Algorithm; HSA)對解的各參數較基因演算法(Genetic Algorithm; GA)能獨立優化，已證實較GA有較佳的效能。因此，本研究將提出HSA與GA之混和演算法求解，並針對兩者提出更進一步的改良方法。實驗結果顯示，在不同工單數量之排程問題下，本研究之混和演算法比GA和HSA原型有更好的結果。此外，結果亦顯示同時考慮緩衝區與自動倉儲的生產環境比僅考慮緩衝區或僅考慮自動倉儲的生產環境較為有利的於排程的安排。

The diversification of industrial products has increased the involvement of reentrant processes in the manufacturing industry. Thus, a job can be routed so that it returns multiple times to one of multiple machines at the preceding workflow stage to continue the manufacturing process. Therefore, reentrant manufacturing processes have become increasingly complex and can be utilized to substantially improve manufacturing efficiency when managed properly. However, most previous studies have assumed that the capacity of inventory buffers for works-in-process (WIPs) is unlimited. Even with a limited capacity, it is complex to store many WIPs properly. In practice, this problem can be solved using an advanced automated material handling system with stockers for temporary WIP storage. However, no study on flow shop scheduling has considered the impact of stockers on scheduling efficiency. Consequently, this study investigated the application of stockers in solving the problem of insufficient WIP storage in a reentrant hybrid flow shop scheduling environment. For the solution to be practicable, this study considered the time for transferring a WIP from a stocker to each station. With the objective of optimizing the makespan and mean flowtime of a schedule, this problem is NP-hard because it generalizes the previous problem, and hence it is suitable for being solved by metaheuristic algorithms. Consequently, this study developed a mathematical model and proposed a metaheuristic algorithm for the scheduling problem. Compared with genetic algorithms (GAs), harmony search algorithms (HSAs) are more effective for optimizing each solution parameter independently. Therefore, this study developed a hybrid HSA–GA (HHSGA) for the problem, in which improvements of both GA and HSA were devised. Experimental comparison on scheduling problems with different numbers of jobs showed that the solutions generated by the HHSGA were better than those generated by conventional GA and HSA. Moreover, the results indicated that the condition using inventory buffers and a stocker was more than with inventory buffers only or with a stocker only beneficial.