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

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

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

非等效平行機台 ； 多階段流程型 ； 整備時間 ； 相依拆卸時間 ； 模擬退火法 ； unrelated parallel machine ； flow shop ； setup ； removal ； simulated annealing

管理與系統

12卷1期（2005 / 01 / 01）

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.

1. 駱景堯、葉進儀、駱芳梧(2003)。整備與拆卸時間考量之開放型排程問題之求解模式建立。工業工程學刊，20(6)，565-574。
   連結：
2. 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.
3. Alidaee, B.,Rosa, D.(1997).Scheduling Parallel Machines to Minimize Total Weighted and Unweighted Tardiness.Computers and Operations Research,24(8),775-788.
4. Allahverdi, A.(2000).Minimizing Mean Flowtime in a Two-Machine Fowshop with Sequence-Independent Setup Times.Computers and Operations Research,27,111-127.
5. 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.
6. Azizoglu, M.,Kirca, O.(1998).Tardiness Minimization on Parallel Machines.International Journal of Production Economics,55,163-168.
7. Balakrishnan, N.,Kanet, J. J.(1999).Early/Tardy Scheduling with Sequence Dependent Setups on Uniform Parallel Machines.Computers and Operations Research,26,127-141.
8. Brah, S. A.,Loo, L. L.(1999).Heuristics for Scheduling in a Flow Shop with Multiple Processors.European Journal of Operational Research,113,113-122.
9. Dessouky, M. M.,Dessouky, M. I.(1998).Flow Shop Scheduling with Identical Jobs and Uniform Parallel Machines.European Journal of Operational Research,109,620-631.
10. Franca, P. M.,Gendreau, M.,Laporte, G.(1996).A Tabu Search Heuristic for the Multiprocessor Scheduling Problem with Sequence Sependent Setup Times.International Journal of Production Economics,43,79-89.
11. Kim, D-W.,Kim, K-H.,Jang, W-S.(2002).Unrelated Parallel Machine Scheduling with Setup Times Using Simulated Annealing.Robotics and Computer Integrated Manufacturing,18,223-231.
12. Koulamas, C.,Kyparisis, G. J.(2000).Scheduling on Uniform Parallel Machines to Minimize Maximum Lateness.Operations Research Letters,26,175-179.
13. Proust, C.,Gupta, J. N. D.,Deschamps, V.(1991).Flowshop Scheduling with Set-up, Processing and Removal Times Separated.International Journal of Production Research,29,479-493.
14. Santos, D. L.,Hunsucker, J. L.,Deal, D. E.(1995).Global Lower Bounds for Flow Shop with Multiple Processors.European Journal of Operational Research,80,112-120.
15. Santos, D. L.,Hunsucker, J. L,Deal, D. E.(1996).An Evaluation of Sequencing Heuristics in Flow Shops with Multiple Processors.Computers Industrial Engineering,30(4),681-692.
16. Sule, D.R.(1982).Sequencing n Jobs on Two Machines Separated.Naval Research Logistics Quarterly,29,517-519.
17. Suresh, V.,Chaudhuri, D.(1996).Bicriteria Scheduling Problem for Unrelated Parallel Machines.Computers and Operations Research,30(1),77-82.
18. Yoshida, T.,Hitomi, K.(1979).Optimal Two-Stage Production Scheduling with Setup Times Separated.AIIE Transactions,11,261-263.
19. 田國興(1999)。中原大學工業工程研究所。
20. 張百棧(2002)。基因演算法於非等效平行機台排程應用。工業工程學刊，19(2)，79-95。
21. 張毓仁(2000)。中原大學工業工程研究所。
22. 楊文華(1996)。國立台灣工業技術學院管理技術研究所。

1. Wang, Shu-Hui,Lin, Hong-Mau,Lin, Cecilia,Hou, Tung-Hsu,Chen, Chung-Kuang(2010).A Study of Operating Room Scheduling That Integrates Multiple Quantitative and Qualitative Objectives.The Journalof Nursing Research,18(1),62-74.