應用基因演算法求解供應鏈中生產排程與物流配送兩階段總成本最小化問題

Abstract

生產排程(product manufacturing)與物流配送(finished good delivery)為供應鏈中的兩個階段作業。目前已有相當多的中、外文獻分別探討此兩階段之最佳化問題。本研究則是將此兩階段視為單一系統，並使用非等效平行機台的生產排程模式(unrelated parallel machine scheduling problem)及車輛途程問題(vehicle routing problem，VRP)來探討其整體之最小成本。由於此兩階段所用之非等效平行機台及車輛途程問題已被證明為非多項式複雜度演算法可解(non-deterministic polynomial-time hard，NP-hard)問題，其求解時間會隨著訂單數的大小而呈指數增加，因此很難在合理的時間內找出整合此兩階段之最佳解。而巨集式啟發式演算法(meta-heuristic)是一種快速且實用的尋優求解方法，其中基因演算法(genetic algorithm，GA)較能符合各種不同型態的最佳化問題。有鑑於此，本研究運用基因演算法以有效地找出整合供應鏈中生產排程與物流配送兩階段總成本最小化的最適解，並使用國際題庫及電腦模擬資料探討在不同情況下本研究所發展之基因演算法在求解此兩階段最佳化問題之可行性及穩定度。結果顯示本研究所提出之方法非常適合求解此兩階段最佳化之問題。

Product manufacturing and finished good delivery are two stages in a supply chain. This study considers these two stages as one system and aims to find a system-wide solution to minimize the total cost of the integrated two-stage problem. Unrelated parallel machine scheduling problem (UPMSP) and vehicle routing problem (VRP) are used to represent each stage of the integrated problem. Since both UPMSP and VRP are NP-hard, the studied problem is also NP-hard. Therefore, it is unlikely to find an optimal solution within reasonable time to this two-stage problem. Meta heuristics are then considered to find the near-optimal solution in this study. Genetic algorithm is utilized to efficiently solve the two-stage problem with an objective of minimizing the total cost incurred at both stages. Finally, simulated data along with problem instance are used to examine the effectiveness and stability of the proposed method. The results show that the proposed approach performs well for this problem.