具時窗限制之多階多廠序列生產工程鏈的訂單分配問題暨其遺傳演算求解法

Abstract

本研究提出一個具實務性的工程鏈營運問題，名為「具時窗限制之多階多廠序列生產工程鏈的訂單分配問題」。除完整定義此問題及數學模型外，並提出「階層內工廠競爭模式」和「階層內工廠合作模式」二種求解目標。問題的限制條件包括訂單在各階層的最晚完工時窗(含最終交期)、訂單內產品跨階運輸數量守恆、工廠的時間產能、及產品運輸時間限制。本文研擬遺傳演算求解法，在問題模型架構下規劃「訂單暨階層開展式」的實數型染色體編碼法。並搭配提出一「訂單暨階層區隔式」的染色體交配法，及五種實數交配演算法。同時，也提出一「訂單暨階層區隔式」的染色體突變法執行突變運算。本研究也規劃一套「階層式染色體解碼法」有效地展出最終訂單分配結果。求解結果會顯示訂單在工程鏈各階層中各個廠各時段間分配的產品數量以及訂單在工程鏈生產網絡中所選擇的生產途徑。在競爭或合作的模式下與訂單的分配策略下組成「競爭拆單模式」、「競爭不拆單模式」、及「合作拆單模式」。為驗証所提方法的適用性，本研究並以C#程式語言在.NET Framework的平台開發「遺傳演算為基的時窗限制多階多廠序列生產工程鏈的訂單分配系統」。為研究問題的實務性提出「工廠生產和運輸成本差異」及「工程鏈階層數」兩個屬性區分應用問題的類型。範例測試結果顯示不同的實數交配演算法會影響本問題各模式的求解結果。所提示的遺傳演化模式會以儘早完工方式分配訂單，結果符合工程鏈的實務運作。範例測試時，在各模式下求解不同類型的問題，求解結果皆符合求解目標及範例問題的特性。此外也探討顧客和企業在工程鏈營運情境下，應該採用的訂單分配模式。本研究研擬的遺傳演算求解模型可以有效地求解此多階多廠序列生產工程鏈的訂單分配問題以支援工程鏈的營運和決策。

This paper presents a time window constrained order allocation problem for a multi-plant and multi-layer serial engineering chain. A mathematical model for the problem was rigorously defined and two allocation strategies, cooperation and competition, with different goals were proposed and studied. Constraints on this problem include order completion times for each engineering layer, cross-layered product flow balance, transportation time, and production capacity. To comply with the layered structure of the engineering chain, an order-layer based GA encoding scheme was proposed, accompanying with order-layer divided crossover and mutation operations and a layer-nested decoding method, which deploys the final order allocation plan. The allocation plan reveals the numbers of products of different orders distributed to each time slot of all of the factories in each layer. Based on the two allocation strategies, three computation modes were proposed: order splitting under competition, order splitting under cooperation, and order competition. A prototype system implementing the proposed GA method was developed to test sample data. Benchmarks were designed based on layer scales and production and transportation cost variations. Numerical tests with various production scenarios showed that the proposed method can be used effectively to solve the presented problem, which will eventually facilitate engineering chain management.