臺灣博碩士論文加值系統

在傳統的流程型工廠排程問題中，每個工作站均只有一台機器，若其中一個或多個工作站有二台以上的平行機器，就成為混合式流程型工廠排程問題（Hybrid flow shop scheduling problem; HFSP）。
針對混合式流程型工廠排程問題，本研究以最大完工時間最小化為目標，建構一啟發式演算法（HHF），並藉由二個標準題庫來測試其求解績效。將測試結果與其他著名的啟發式演算法之計算結果比較，證實本研究所提出之HHF演算法對於HFSP具有較佳的求解績效。

We study the problem of sequencing n-job on a m-stage hybrid flow shop(HFS), each stage with multiple identical machines and all job have multiprocessor tasks in each stage. This research focuses on the development of a new heuristic for minimizing the makespan in HFS problem.
To verify the developed new heuristic, computational experiments are conducted on two well-known benchmark problem sets. The proposed new heuristic is compared with other heuristic from the literature.Results demonstrated that the new heuristic is a more effective heuristic for the problem.

誌謝 i
中文摘要 ii
英文摘要 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章、導論 1
1.1研究動機與目的 1
1.2研究問題與限制條件 3
1.2.1研究問題 3
1.2.2假設與限制條件 3
1.3研究流程 4
1.4 論文架構 6
第二章、文獻探討 7
2.1混合式流程型排程問題 7
2.1.1兩階段HFSP 7
2.1.2三階段HFSP 11
2.1.3 k階段HFSP 13
2.2混合式流程型排程之啟發式演算法 14
2.3流程型排程之啓發式演算法 17
第三章、研究方法 22
3.1新啟發式演算法架構 22
3.1.1 HHF第一階段 24
3.1.2 HHF第二階段 26
3.2新啟發式演算法求解流程 29
3.3測試題庫及下界 33
第四章、結果分析 36
4.1啟發式演算法與HHF演算法結果的比較（OR Library） 36
4.2啟發式演算法與HHF演算法結果的比較（Oğuz） 41
4.3 統計分析 46
第五章、結論與建議 47
5.1 結論 47
5.2未來研究方向與建議 48
參考文獻 50
附錄 符號彙編 53

[1]M. J. Acero-Dominguez, C. D. Paternina-Arboleda, Scheduling jobs on a k-stage flexible flow shop using a TOC-Based(BOTTLENECK)procedure, Proceedings of the 2004 Systems and Information Engineering Design Symposium,2004.
[2]E. H. Aghezzaf, A. Artiba, Aggregate planning in hybrid flowshops, International Journal of Production Research 36 (1998) 2463-2477.
[3]C. Andres, J. M. Albarracin, G. Tormo, E. Vicens, J. P. Garcia-Sabater, Group technology in a hybrid flowshop environment:A case study, European Journal of Operational Research 167 (2004) 272-281.
[4]M. Azizoğlu, E. Cakmak, S. Kondakci, A flexible flowshop problem with total flow time minimization, European Journal of Operational Research 132 (2001) 528-538.
[5]A. Babayan, D. He, Solving the n-job 3-stage flexible flowshop scheduling problem using an agent-based approach, International Journal of Production Research 42 (2004) 777-799.
[6]M. Braglia, A. Petroni, Data envelopment analysis for dispatching rule selection, Production Planning & Control 10 (1999) 454-461.
[7]S. A. Brah, J. L. Hunsucker, Branch and bound algorithm for the flow shop with multiple processors, European Journal of Operational Research 51 (1991) 88-99.
[8]J. Carlier, Scheduling jobs with release dates and tails on identical machines to minimize the makespan, European Journal of Operational Research 29 (1987) 298-306.
[9]A. G.. P. Guinet , M. M. Solomon, Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time, International Journal of Production Research 34 (1996) 1643-1654.
[10]J. N. D. Gupta, Two-stage hybrid flowshop scheduling problem, Operational Research Society 39 (1988) 359-364.
[11]J. N. D. Gupta, E. A. Tunc, Schedules for a two-stage hybrid flowshop with parallel machines at the second stage, International Journal of Production Research 29 (1991) 1489-1502.
[12]J. N. D. Gupta, E. A. Tunc, Schedules a two-stage hybrid flowshop with separable setup and removal times, European Journal of Operational Research 77 (1994) 415-428.
[13]J. N. D. Gupta, A flowshop scheduling problem with two operations per job, International Journal of Production Research 35 (1997) 2309-2325.
[14]J. N. D. Gupta, A. M. A. Hariri, C. N. Potts, Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Annals of Operations Research 69 (1997) 171-191.
[15]J. N. D. Gupta and E. A. Tunc, Minimizing tardy jobs in a two-stage hybrid flowshop, International Journal of Production Research 36 (1998) 2397-2417.
[16]T. P. Hong, C. L. Wang, S. L. Wang, Solving flexible flow-shop problems by combining LPT and Gupta Scheduling Algorithms, Hybrid Methods in Engineering 3 (2001) 130-142.
[17]J. A. Hoogeveen, J. K. Lenstra, B. Veltman, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European Journal of Operational Research 89 (1996) 172-175.
[18]M. S. Jayamohan, C. Rajendran, A comparative analysis of two different approaches to scheduling in flexible flow shops, Production Planning & Control 11 (2000) 572-580.
[19]S. N. Kadipasaoglu, W. Xiang , B. M. Khumawala, A comparison of sequencing rules in static and dynamic hybrid flow systems, International Journal of Production Research 35 (1997) 1359-1384.
[20]S. N. Kadipasaoglu, W. Xiang , B. M. Khumawala, A note on scheduling hybrid flow systems, International Journal of Production Research 35 (1997) 1491-1494.
[21]C. Koulamas, A new constructive heuristic for the flowshop scheduling problem, European Journal of Operational Research 57 (1998) 111-122.
[22]M. Kreutz, D. Hanke, S. Gehlen, Solving extended hybrid-flow-shop problems using active schedule generation and genetic algorithms, Supported by the BMBF under Grant No.01IB802A9(LEONET).
[23]C. Y. Lee, G. L. Vairaktarakis, Minimizing makespan in hybrid flowshops, Operations Research Letters 16 (1994) 149-158.
[24]G. C. Lee, Y. D. Kim, S. W. Choi, Bottleneck-focused scheduling for a hybrid flowshop, International Journal of Production Research 42 (2004) 165-181.
[25]S. Li, A hybrid two-stage flowshop with part family, batch production, major and minor set-up, European Journal of Operational Research 102 (1997) 142-156.
[26]H. T. Lin, C. J. Liao, A case study in a tow-stage hybrid flow shop with setup time and dedicated machines, International Journal of Production Research 86 (2003) 133-143.
[27]R. Linn, W. Zhang, Hybrid flow shop scheduling: A Survey, Computers & Industrial Engineering 37 (1999) 57-61.
[28]S. L. Narasimhan, P. M. Mangiameli, A comparison of sequencing rules for a two-stage hybrid flow shop, Decision Sciences 18 (1987) 205-214
[29]M, Nawaz, E. Emory Enscore Jr Inyong Ham, A heuristic algorithm for the m-Machine, n-Job flow-shop sequencing problem, OMEGA 11 (1983) 91-95.
[30]C. Oğuz, Y. Zinder, V. H. Do, A. Janiak, M. Lichtenstein, Hybrid flow-shop scheduling problems with multiprocessor task systems, European Journal of Operational Research 152 (2004) 115-131.
[31]C. Oğuz, M. F. Ercan, T. C. E. Cheng, Y. F. Fung, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop, European Journal of Operational Research 149 (2003) 390-403.
[32]C. Oğuz, A. Janiak, M. Lichtenstein, Metaheuristic algorithms for hybrid flow-shop scheduling problem with multiprocessor tasks, MIC’2001-4th Metaheuristics International Conference, 2001.
[33]M. C. Portmann, A. Vignier, D. Dardilhac, D. Dezalay, Branch and bound crossed with GA to solve hybrid flowshops, European Journal of Operational Research 107 (1998) 389-400.
[34]C. Rajendran, D. Chaudhuri, A multi-stage parallel-processor flowshop problem with minimum flowtime, European Journal of Operational Research 57 (1992) 111-122.
[35]F. Riane, A. Artiba, S. E. Elmaghraby, A hybrid three-stage flowshop problem: Efficient heuristics to minimize makespan, European Journal of Operational Research 109 (1998) 321-329.
[36]F. S. Serifoğlu, G. Ulusoy, Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach, Journal of the Operational Research Society 55 (2004) 504-512.
[37]H. Soewandi, S. E. Elmaghraby, Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan, IIE Transactions 35 (2003) 467-477.
[38]H. Soewandi, S. E. Elmaghraby, Sequencing three-stage flexible flowshops with identical machines to minimize makespan, IIE Transactions 33 (2001) 985-993.
[39]C. Sriskandarajah, S. P. Sethi, Scheduling Algorithms for flexible flowshops:Worst and average case performance, European Journal of Operational Research 43 (1989) 143-169.
[40]H. W. Thornton, J. L. Hunsucker, A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage, European Journal of Operational Research 152 (2004) 96-114.
[41]P. Watanakich, R, Kanjanapanyakom, A heuristic approach for a two-stage hybrid flow shop with machine setup time, Proceedings of Symposium in Production and Quality Engineering, 2002.
[42]廖顯明（2005），「蟻群系統在混合式流程型工廠排程問題之應用」，私立華梵大學工業工程與經營資訊學系碩士論文。