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

Abstract

本研究針對具非等效平行機台之多階段流程型的工廠排程問題，加入獨立且可分割整備時間及相依拆卸時間作為考量的因素；在總流程時間最小化之目標下，將工件安排至各階段的平行機台上加工，並決定其工件之加工順序。研究首先以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.