具時窗限制的併批暨排程優化問題及其遺傳演算法

Abstract

本研究探討具時窗限制的併批暨排程優化問題及其遺傳演算求解法。本研究完整定義問題的數學模式，採用最大化機台產能利用率為求解目標，限制條件為加工型別限制、加工先後順序限制、批次容量限制、及時窗限制。本研究依據問題模式開發遺傳演算求解法，採用「工件排程處理順位編碼法」及「加工作業排程處理順位編碼法」兩種編碼法。據此再提出「忽略時窗限制的解碼�排程演算程序」及「考慮時窗限制的解碼�排程演算程序」兩種解碼方法，前者視時窗限制為軟式限制，後者視時窗限制為硬式限制。兩種編碼和兩種解碼方法組成三種遺傳演算模式：「工件排程處理順位編碼忽略時窗限制求解模式」、「加工作業排程處理順位編碼忽略時窗限制求解模式」、及「工件排程處理順位編碼考慮時窗限制求解模式」。為驗證所提方法的適用性，本研究並以C#程式語言在.NET Framework的平台開發「遺傳演算為基的時窗限制併批暨排程系統」。本研究同時提出「時窗限制鬆緊」、「加工時間差異」、及「問題規模」三個屬性指標嘗試對所提問題進行分類，並制定標竿問題命名法則。為進行實例測試本研究依據所制定的分類法則創建多個不同類型的測試範例。範例測試結果顯示不同遺傳演算模式求解不同類型的問題有不同的效率，且所提的遺傳演算適存函式針對本研究問題能考量多層面的目標且求得有效率的排程解。

This research presents the definition and model of the Time Window Constrained Batching Scheduling Problem. The object of this model is to maximize machine utilization. The problem is subjected to four kinds of constraints. GA-based optimization methods are developed to solve this problem, which includes: two encoding methods and two decoding and scheduling procedures. These two decoding and scheduling procedures are “Time Window Constraints Ignored Decoding and Scheduling Procedure” and “Time Window Constraints Considered Decoding and Scheduling Procedure”. The former treats time window constraints as soft constraints and the later treats time window constraints as hard constraints. These encoding methods and decoding and scheduling procedures form three modes of GA-based optimization methods. Based on these proposed methods, a system named GA-based Time Window Constrained Batching Scheduling System (GA-TWCBSS) is developed. This paper defined three properties to classify the research problem and set up the naming rule. According to these properties, several classes of examples are created as test problems. Computation results show that different GA-based optimization methods solve different classes of examples in different performance. In addition, the proposed fitness function can cover multi objectives simultaneously by using the proposed GA-based optimization methods.