以基因演算法求解工件族群批件處理機台之多目標流程式生產排程問題

Translated title of the thesis: Solving Multi-objective Scheduling Problem of Incompatible Families on Batch Processing Machines by Genetic Algorithm
  • 蕭 涵謙

Student thesis: Master's Thesis

Abstract

本研究考慮批件處理機台(Batch processing machines)之流程式生產排程問題,並考量不相容工件族群(incompatible families)之情形,目標是找出最小化最大完工時間(makespan)以及最小化總權重延遲時間(total weighted tardiness time)。本研究首先針對此問題建立數學規劃模式,由於此為一個NP-complete的問題,因此若是當工件數或機台數量增加,便很難利用數學模型來求解。故此本研究修改多目標基因演算法以求得近似最佳解,使演算法更能適用在批件處理機台,或是應用到考量不相容工件族群的情形,並在演算法中使用菁英策略結合柏拉圖前緣解的概念以處理多目標問題之情形,提供生產線上決策者進行決策;並以數組隨機產生之問題進行求解,得到本研究之演算方法再求解規模較大的問題時,可以得到較完整的柏拉圖前緣解;而後續再以本研究所建立之數學模型求解較小規模之問題的每一目標最佳解,與本研究之多目標基因演算法求解進行比較,得出本研究之演算方法在求解小型問題時同樣可以得到最佳解,而求解效率相較模形求解亦隨著問題規模上升而提高;最後以演算法計算結果分析本研究問題計算結果所發生的情形,並提供未來研究方向的建議。
Date of Award2014 Jul 9
Original languageChinese
SupervisorShiow-Yun Chang (Supervisor)

Cite this

'