應用混合式染色體表達法於具順序相依家族整備時間之流線型製造單元排程

A Mixed-Mode Chromosome Representation for Scheduling a Flowshop Manufacturing Cell with Sequence Dependent Family Setup Times

戴邦豪(Pang-Hao Tai)

指導教授 ： 巫木誠

國立交通大學/管理學院/工業工程與管理系所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00303

摘要

本研究主要在探討具順序相依家族整備時間(Sequence Dependet Family Setup Times)之流線型製造單元(Manufacturing Cell System)生產排程問題。在傳統染色體表達法的基礎下，應用呂佳玟(2009)提出的染色體解碼概念，來提昇求解的效率，並且發展四種類型的基因演算法來求解製造單元排程問題，此四種演算法分別為GA-T（Traditional Genetic Algorithm）、GA-N（New Genetic Algorithm）、GA-TN以及GA-NT，其中GA-TN和GA-NT（Mixde-mode Genetic Algorithm）為使用混合式染色體表達法之基因演算法。本研究使用Lin et al. (2009)之實驗情境在最小化最大完工時間(makespan； )與最小化總延遲時間(total tardiness； )的績效指標下，將四種基因演算法進行比較；實驗結果顯示，GA-TN在各種指標下均比其餘三種演算法有良好之表現。本研究不僅改良了有別於傳統染色體的的表達法，並且在相同的進化機制下，透過染色體設計方式不同，進而改善排程求解的品質與求解效率。

關鍵字

順序相依家族整備時間 ； 基因演算法 ； 染色體表達法 ； 單元製造系統

並列摘要

This research is concerned with the scheduling of a flowshop manufacturing cell with sequence-dependent family setup times. A new chromosome representation scheme is proposed. Based on the new and a prior chromosome representation schemes, we develop four types of genetic algorithms (GAs) to solve the scheduling problem. These four GAs, respectively called GA-T, GA-N, GA-TN, GA-NT, are essentially based on the same solution evolutionary mechanism but different in using various chromosome representation schemes. Extensive experiment results indicate that the GA-TN outperform the other three ones in terms of solution quality. This finding shed light on a new track for improving genetic algorithms—developing new chromosome representation scheme, even with the same solution evolutionary mechanisms, might lead to better solution effectiveness

並列關鍵字

flowshop manufacturing cell ； genetic algorithm ； chromosome representation ； sequence-dependent family setups

參考文獻

呂佳玟，「應用基因演算法與家族式派工於傳輸整合步進機在小批量情境下之排程問題」，交通大學，碩士論文，民國98年。

Cheng TCE, Gupta NDJ and Wang G (2000). A review of flowshop scheduling research with setup times. Production and operations management 9: 262-282.

Cheng TCE & Wang Guoqing. (1998). Batching and scheduling to minimize the makespan in the two-machine flowshop. IIE Transactions 30: 447-453.

Das Sidhartha R & Canel Cem (2005). An algorithm for scheduling batches of parts in a multi-cell flexible manufacturing system. Int. J. Production Economics 97: 247-262.

Franca PM, Gupta JND, Mendes AS, Moscato P , Veltink KJ (2005). Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Computers & Industrial Engineering 48: 491-506.