不完全作業下考慮交期之兩階段混合流程式排程問題

Translated title of the thesis: Two-stage Hybrid Flow Shop Scheduling with Missing Operations and Due Date
  • 吳 宗霖

Student thesis: Master's Thesis

Abstract

在排程的領域,以最佳解方法解決小規模的問題並不是難題,但隨著環境的複雜度上升,問題也相對越來越難求得最佳解,使用派工法則等啟發式演算法,在可接受的時間內求得近似最佳解已是學者們致力多年的目標。本研究探討的系統為兩階段之混合流程式生產,因需求不同使得某些工件在第一階段作業時間為零之情形,稱之為不完全作業模式(missing operations),若以過往方式產生作業排班,將導致第二階段機台空閒之情形過長,為了改善此類情形,將這些工件直接移至第二階段進行加工,產生非排列式(non-permutation)工作序列,便可得到更好之績效。然而過去文獻中鮮少討論此類情形,其中以交期指標做為目標之研究更為稀少,因此本研究提出三個以交期指標做為目標之啟發式演算法,使此生產系統能快速回應客戶需求,本研究提出之演算法1藉由以多種派工法則產生第一階段排序,計算工件在第二階段釋放時間後,再以其他派工法則產生一組解,從不同組合中選擇最小的總延遲時間排程;演算法2亦以四種排列組合方式產生初始解,並以遞迴方式持續向下搜尋是否有較低的延遲工件數,最後回傳找到的最佳序列;演算法3則是由演算法2的步驟中,利用多個儲存空間記取所有符合最低延遲工件數的排序,從中選擇總延遲時間最低的序列,此三種演算法皆利用有效率地步驟求得近似解。 本研究先以小問題測試本研究提出之啟發式演算法有效性,再以多種參數組合之實驗,探討不同生產環境下演算法之適用性。最後根據分析結果發現,隨著不完全作業比率以及工件數的增加,本研究提出之演算法1與演算法2改善排列式排程狀況也隨之明顯。並在不同資料實驗設計的環境下,分析與交期相關之派工法則,發現當工件數較少時使用SPT派工法則;而工件數提升時使用EDD派工法則,更能快速地找到品質較佳的可行解。
Date of Award2015 Sep 3
Original languageChinese
SupervisorShiow-Yun Chang (Supervisor)

Cite this

不完全作業下考慮交期之兩階段混合流程式排程問題
宗霖, 吳. (Author). 2015 Sep 3

Student thesis: Master's Thesis