整備與拆卸時間考量之開放型排程問題之求解模式建立

Solution Models Construction for Open Shop Scheduling Problem with Setup, Processing, and Removal Times Separated

駱景堯(Chin-Yao Low) ； 葉進儀(Jinn-Yi Yeh) ； 駱芳梧(Fang-Wu Low)

《工業工程學刊》 20卷6期 (2003/11) Pp. 565-574

摘要

排程為有效配置所有可利用之有限資源以滿足特定績效衡量準則之一種技術。而生產排程主要之議題則是在各種生產條件之限制下，決定所有須處理之工件在特定生產設備上之處理順序。本研究所探討開放型工廠排程之特色在於系統中之工件在機器設備上並無固定之處理順序，而過去之研究基於簡化問題之考量大都將整備與拆卸時間忽略或合併於處理時間內。然而，實務上之考量為求排程結果之可行性與精確性，整備時間與拆卸時間為不可忽略之因素；再者，交期之考量亦常為企業評估排程結果優劣之指標之一，因此本研究針對考量整備與拆卸時間之開放型工廠排程問題，在滿足總工件延遲時間最小化之目標下，首先以整數規劃建立該問題之最佳解模式；而後基於求解效率之考量，本研究亦建構一啓發式求解程序，並結合模擬退火法程序進行求解之改善。最後在兼顧求解效能與效率之雙重考量下，研究中亦針對影響演算結構之參數進行實驗設計與分析，並針對各種不同之製程環境提出穩健之參數組合，以供後續研究之參考。

關鍵字

開放型工廠排程 ； 整備時間 ； 拆卸時間 ； 總延遲時間 ； 模擬退火法

並列摘要

In this research, we look the setup, processing, and removal times as separatable, then take the sequence-independent setup and dependent removal times into account when deal with an open shop scheduling problem with the objective to minimize the total job tardiness. The addressed problem is first described as a 0-1 integer programming model, and following, a simulated annealing based heuristic is proposed to get an near optimal schedule in a reasonable computation time. During the research, the parameters used in the heuristics that affect the solution quality and efficiency are analyzed and designed; then for the constructed heuristic, a good parameter setting is suggested. The experimental results are reported, and provided for the references for the further research.

並列關鍵字

setup ； removal ； open shop scheduling ； total job tardiness ； simulated annealing

參考文獻

Achugbue, J. O.,Chin, Francis Y. L.(1982).Scheduling the open shop to minimize mean flow time.SIAM Journal on Computing.11(4)

Brucker, P.,Johann, H.,Bernd, J.,Birgit, W.(1997).A branch ＆ bound algorithm for the open shop problem.Discrete Applied Mathematics.76

Du, Jianzhong,Leung, Joseph Y. T.(1993).Minimizing mean flow time in two-machine open shops and flow shops.Journal of Algorithms.14(1)

Gonzalez, T.,Sahni, S.(1976).Open shop scheduling to minimize finish time.Journal of the Association for Computing Machinery.23(4)

Kyparisis, G. J.,Koulamas, C.(2000).Open shop scheduling with makespan and total completion time criteria.Computers ＆ Operations Research.27(1)