模擬退火法於考量整備與拆卸時間之具非等效平行機台多階段流程型排程問題研究

An Approach of Simulated Annealing in Multistage Flow Shop Scheduling with Unrelated Parallel Machines

葉玉玲(Yuk-Ling Yip) ； 駱景堯(Chin-Yao Low) ； 洪正鴻(Cheng-Horn Horng)

《管理與系統》 12卷1期 (2005/01) Pp. 93-116

摘要

本研究針對具非等效平行機台之多階段流程型的工廠排程問題，加入獨立且可分割整備時間及相依拆卸時間作為考量的因素；在總流程時間最小化之目標下，將工件安排至各階段的平行機台上加工，並決定其工件之加工順序。研究首先以0-1整數規劃建構出探討問題之最佳解模式，但有鑒於數學模式求解耗時且僅適用於小規模問題之求解，故針對較大規模問題，發展出一以模擬退火法為基礎之啓發式演算法，用以求解於中、大規模問題，以期可以在容許時間下搜尋到最佳解或一近似最佳解。研究中除對於影響演算法之參數進行分析與設定，以求演算法之穩定性；並對起始解對於演算法之最終求解結果之影響進行分析與比較，期能以此結果提供後續研究之參考。

關鍵字

非等效平行機台 ； 多階段流程型 ； 整備時間 ； 相依拆卸時間 ； 模擬退火法

並列摘要

In this research, an unrelated parallel machine flow shop scheduling problem of minimizing mean flow time is considered. In the past few years, in order to simplify the scheduling problem, most of research assumes setup and removal times are even negligible or part of the processing time. 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. To solve the addressed problem two different solving models are developed. First, a 0-1 integer programming model is constructed; however, the mathematical model is too time consuming to solve the medium or large size problem, thus, 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.

並列關鍵字

unrelated parallel machine ； flow shop ； setup ； removal ； simulated annealing

參考文獻

駱景堯、葉進儀、駱芳梧(2003)。整備與拆卸時間考量之開放型排程問題之求解模式建立。工業工程學刊。20(6)，565-574。

Adamopoullos, G. I.,Pappis, C. P.(1998).Scheduling Under a Common Due-Date on Parallel Unrelated Machines.European Journal of Operational Research.105,494-501.

Alidaee, B.,Rosa, D.(1997).Scheduling Parallel Machines to Minimize Total Weighted and Unweighted Tardiness.Computers and Operations Research.24(8),775-788.

Allahverdi, A.(2000).Minimizing Mean Flowtime in a Two-Machine Fowshop with Sequence-Independent Setup Times.Computers and Operations Research.27,111-127.

Allahverdi, A.,Aldowaisan, T.(2000).No-Wait and Separate Setup Three-Machine Flowshop with Total Completion Time Criterion.International Transactions in Operational Research.7,245-264.