應用變動鄰域搜尋法求解整合生產與配送之兩階段排程問題

Abstract

在公司採用訂貨生產(make-to-order)或是直接銷售(direct-order)的營運模式下，供應鏈為避免存貨失去其時效性所造成的重大損失，通常只備有少量或者沒有備庫存來緩衝需求的不確定性，進而加強了生產與配送階段間緊密的關係。因此，本研究針對整合生產與配送之兩階段排程問題進行探討，以非等效平行機台(unrelated parallel machine)模擬產品製造階段的生產環境，而成品配送階段則以車輛途程問題(vehicle routing problem, VRP)進行模擬，且應用最早可利用機台派工法則(earliest available machine first, EAMF)及變動鄰域搜尋法(variable neighborhood search, VNS)求解問題，以目標函式值進行當前解的更新；目標函式為最小化整合兩階段之加權訂單完成時間與總配送成本，這意味著所使用之方法必須快速產生多組可行解，同時具備跳脫區域最佳解的能力來求得全域最佳解。EAMF能考量非等效平行機台之負荷，於短時間內以一排程序列(LII)產生一組生產排程，並藉由VNS對排程(LII)和途程序列(LIb)做快速且有系統的搜尋，期間以VNS特有的震動(shaking)機制期望跳脫區域最佳解。此外，易使用的VNS也改善了蟻群演算法(ant colony optimization, ACO)參數組合過於複雜，而影響求解品質的缺點。最後以測試例題驗證VNS應用於求解整合兩階段排程問題之可行性。

When make-to-order or direct-order is applied, business needs to keep low finished goods inventory level to be competitive. However, with low inventory level, business has little buffer to cope with unforeseeable demand surge, which strengthens the importance of linking production and distribution stages. This thesis considers an integrated production and distribution scheduling problem in which orders are first produced by a set of unrelated parallel machines, then directly distributed to the corresponding customers by vehicles with limited capacity, with no inventory kept at production stage. This study applied Earliest Available Machine First (EAMF) and Variable Neighborhood Search (VNS) to solve this problem. The objective is to find a joint production and distribution schedule such that the total cost considering both customer service level and total distribution cost is minimized. This implies that the proposed method must generate multiple feasible solutions quickly, along with the ability to escape local optima. The proposed method used EAMF that considers unrelated parallel machine loadings to generate a set of production schedules to be systematically optimized by VNS along with optimized routing. The proposed method designed a set of shaking mechanisms employed in VNS to escape from local optimal solution. The results of computational experiments showed that the proposed method outperformed an exist approach that applied Ant Colony Optimization (ACO) heuristics in terms of the computational time and solution quality.