跳到主要內容

臺灣博碩士論文加值系統

(35.174.62.102) 您好!臺灣時間:2021/07/25 05:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔡慶泰
研究生(外文):Ching-Tai Tsai
論文名稱:一個混合式的三階段流程型生產排程問題之研究
論文名稱(外文):A Hybrid Three-stage Flow Shop Scheduling Problem
指導教授:賴奕銓賴奕銓引用關係
學位類別:碩士
校院名稱:靜宜大學
系所名稱:企業管理研究所
學門:商業及管理學門
學類:企業管理學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:81
中文關鍵詞:總完工時間混合式流程型排程基因演算法
外文關鍵詞:Genetic AlgorithmMakespanHybrid Flow Shop Scheduling
相關次數:
  • 被引用被引用:1
  • 點閱點閱:808
  • 評分評分:
  • 下載下載:145
  • 收藏至我的研究室書目清單書目收藏:0
排程(scheduling)在生產管理的領域中,是非常重要的一門學問,其中包含了數種排程模式,而在本研究中,是針對延伸的流程型排程問題所做的研究。總完工時間(Makespan)長久以來一直是在排程領域中重要的研究指標之一,為了降低總完工時間,製造業者紛紛加入平行機台以增加效率及產能,但礙於機台價格、機台體積或其它因素,並非所有產業在其生產流程上的每一個工作站的機台都能投入大量的平行機台來加快生產。因此本研究以混合式的流程型排程來做為研究主題,我們亦提出了一種混合式的三階段流程型排程問題。然而為了有效的找出近似最佳的最小化總完工時間的解,我們採用了基因演算法(Genetic Algorithm, GA)並與派工法則(Dispatching rules)做進一步的比較,經計算結果顯示,我們可發現在這種生產製程中,基因演算法可以獲得較佳的解,尤其當訂單數量越小時效果越好。
The scheduling is a very important issue in production management field. We investigate for the hybrid flow shop scheduling problem. The makespan is always one of the important criteria in the scheduling field. In order to reduce the makespan, the manufacturer set up parallel machines to increase the production efficiency. However, due to the cost of machines, not all the industries can invest a lot of costs on setting up parallel machines to increase the production. Therefore, the objective of this research is to develop an effective heuristic algorithm to find a good schedule for the hybrid three-stage flow shop scheduling problem to reduce makespans. We adopt the Genetic Algorithm (GA) for solving the hybrid flow shop scheduling problem and compare the schedule found by the GA with traditional dispatching rules such as FCFS, SPT, LPT, EDD… etc.. In the experimental results, the genetic algorithm can obtain superior solutions for the hybrid flow shop scheduling problem. We also find that the GA is most effective for the hybrid flow shop scheduling problem when the problem size is small.
謝誌 I
ABSTRACT II
摘要 III
TABLE OF CONTENT IV
LIST OF TABLES VI
LIST OF FIGURES VII
CHAPTER 1 INTRODUCTION 1
1.1 Background 1
1.2 Motivation for the Research 2
1.3 Objective of the Research 2
1.4 Organization of the Thesis 2
CHAPTER 2 LITERATURE REVIEW 3
2.1 Scheduling 3
2.1.1 Single machine 3
2.1.2 Parallel machine 3
2.1.3 Flow shop Scheduling 3
2.1.4 Job shop Scheduling 3
2.1.5 Open shop Scheduling 4
2.2 Hybrid flow shop scheduling problem 4
2.2.1 Hybrid Multi-Stage Flow shop Problem 5
2.2.2 Hybrid Two-Stage Flow shop Problem 6
2.2.3 Hybrid Three-Stage Flow shop Problem 7
2.3 Dispatching rule 8
2.4 Genetic algorithm 10
CHAPTER 3 PROBLEM DESCRIPTION 12
3.1 The problem system 12
3.2 The performance measurements 14
3.3 Procedure of process 15
CHAPTER 4 METHODOLOGY AND EXPERIMENTAL DESIGN 17
4.1 The Genetic Algorithm 17
4.1.1 Introduction 17
4.1.2 Representation of chromosome 17
4.1.3 Initial population 18
4.1.4 Fitness function 18
4.1.5 Selection 19
4.1.6 Crossover 19
4.1.7 Mutation 21
4.2 Experimental Design 22
4.3 Data analysis 25
CHAPTER 5 RESULTS 27
5.1 Performances of the GA 27
5.2 Analysis of the experiments 29
5.2.1 Goodness of Fit Test of Makespan 29
5.2.2 The Results 31
CHAPTER 6 CONCLUSIONS 39
6.1 Conclusions 39
6.1.1 Performances of GA 39
6.1.2 Analysis of the experimental system 39
6.2 Contributions 40
6.3 Suggestions 40
REFRANCE 41
Appendix A 44
Appendix B 50
Appendix C 66
Beasley,J.E. (2009) OR-Library,
http://people.brunel.ac.uk/~mastjjb/jeb/info.htm
Goldberg, D. E. (Ed.). (1989). Genetic algorithm in search, optimization, and machine learning: Addison-Wesley.
Haouari, M., & Hidri, L. (2008). On the hybrid flowshop scheduling problem. International Journal of Production Economics, 113, 495-497.
Haouari, M., & M''Hallah, R. (1997). Heuristic algorithms for the two-stage hybrid flowshop problem. Operations Research Letters, 21, 43-53.
Haupt, R. (1989). A survey of priority rule-based scheduling. OR Spectrum, 11, 3-16.
He, L., Sun, S., & Luo, R. (2007). A hybrid two-stage flowshop scheduling problem. Asia-Pacific Journal of Operational Research, 24(1), 45-56.
Holthaus, O., & Rajendran, C. (1997). Efficient dispatching rules for scheduling in a job shop. International Journal of Production Economics, 48(87-105).
Jin, Z., Yang, Z., & Ito, T. (2006). Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics, 100, 322-334.
Jin, Z. H., Ohno, K., Ito, T., & Elmaghraby, S. E. (2002). Scheduling hybrid flowshops in printed circuit board assembly lines. POMS Series in Technology and Operations Management, 11.
Karimi, N., Zandieh, M., & Karamooz, H. R. (2010). Bi-objective group scheduling in hybrid flexible flowshop: A multi-phase approach. Expert Systems with Applications, 37, 4024-4032.
Kis, T., & Pesch, P. (2005). A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. European Journal of Operational Research, 164, 592-608.
Koulamas, C., & Kyparisis, G. J. (2007). A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines. European Journal of Operational Research, 182(945-951).
Li, S. (1997). A hybrid two-stage flowshop with part family, batch production, major and minor set-ups. European Journal of Operational Research, 102, 142-156.
Luo, H., Huang, G. Q., Zhang, Y., Dai, Q., & Chen, X. (2009). Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm. Robotics and Computer-Integrated Manufacturing, 25, 962-971.
Mahdavi, I., Mojarad, M. S., Javadi, B., & Tajdin, A. (2008). A genetic approach for solving a hybrid flow shop scheduling problem. Paper presented at the The IEEE International Conference on Industrial Engineering and Engineering Management.
Moursli, O., & Pochet, Y. (2000). A branch-and-bound algorithm for the hybrid flowshop. International Journal of Production Economics, 64, 113-125.
Neppalli, V. R., Chen, C.-L., & Gupta, J. N. D. (1996). Genetic algorithms for the two-stage bicriteria flowshop problem. European Journal of Operational Research, 95, 356-373.
Oguz, C., & Ercan, M. F. (2005). A genetic algorithm for hybrid flow-shop scheduling with multiprocessor takes. Journal of Scheduling, 8, 323-351.
Pinedo, M. L. (Ed.). (2008). Scheduling: Theory, Algorithms, and System (3 ed.): Springer-Verlag.
Portmann, M.-C., Vignier, A., Dardilhac, D., & Dezalay, D. (1998). Branch and bound crossed with GA to solve hybrid flowshops. European Journal of Operational Research, 107, 389-400.
Rajkumar, R., & Shahabudeen, P. (2009). An improved genetic algorithm for the flowshop scheduling problem. International Journal of Production Economics, 47(1), 233-249.
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers and Operations Research, 22(1), 5-13.
Riane, F., Artiba, A., & Elmaghraby, S. E. (1998). A hybrid three-stage flowshop problem: Efficient heuristics to minimize makespan. European Journal of Operational Research, 109, 321-329.
Riane, F., Artiba, A., & Elmaghraby, S. E. (2002). Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Economics, 40(17), 4353-4380.
Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169, 781-800.
Sung, C. S., & Kim, H. A. (2008). A two-stage multi-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics, 113, 1038-1048.
Tseng, L.-T., & Lin, Y.-T. (2009). A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 198, 84-92.
Wardono, B., & Fathi, Y. (2004). A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities. European Journal of Operational Research, 155, 380-401.
Wittrock, R. J. (1988). An adaptable scheduling algorithm for flexible flow lines. Operations Research, 36(3), 445-453.
Xie, X., & Tang, L. (2009). Analysis of a heuristics for scheduling two-stage hybrid flow shop. Paper presented at the International Joint Conference on Computational Sciences and Optimization.
Zhang, Y., Li, X., & Wang, Q. (2009). Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization. European Journal of Operational Research, 196, 869-876.
Zhang, Y., Zhou, Z., & Liu, J. (2010). The production scheduling problem in a multi-page invoice printing system. Computers and Operations Research, 37, 1814-1821.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊