一個二階段蟻群最佳化演算法於零工式工廠排程問題｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	詹鈞揚 Jyun-Yang Jhan
論文名稱：	一個二階段蟻群最佳化演算法於零工式工廠排程問題 A Two-stage Ant Colony Optimization to Solve the Job Shop Problem
指導教授：	羅士哲 Shih-Che Lo
口試委員:	曹譽鐘 Yu-Chung Tsao 蔡鴻旭 Hung-Hsu Tsai
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2016
畢業學年度：	104
語文別：	英文
論文頁數：	68
中文關鍵詞：	生產力4.0 、蟻群最佳化、零工式工廠、排程、智慧製造
外文關鍵詞：	Productivity 4.0, Ant Colony Optimization, Job Shop, Scheduling, Intelligent Manufacturing
相關次數：	點閱：341 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

企業在現今激烈的競爭環境下想要增加獲利，除了提高銷售量及降低生產成本外，
另一方面就是提升生產排程效率。因此，企業必須提供有效率的排程規劃來快速的因應
顧客回應需求。尤其是在工業4.0 的架構之下，建構智慧排程系統更為重要。
規劃生產排程問題，主要是希望透過有效率地資源分配來提高生產效率並降低生產
成本，縮短機台的閒置時間與總工作時間，減少企業成本與產品開發/製造時間，達成最
小成本與快速回應顧客需求之目的，讓企業在市場上具有更強勁的競爭力。
本論文研究之零工式工廠排程，彈性與複雜度大於一般的流程式工廠排程，為了規
劃零工式工廠排程，本論文提供了兩階段式的演算法，稱為改良式蟻群最佳化演算法
(iACO)，以蟻群最佳化演算法(Ant Colony Optimization Algorithm, ACO) 搭配輪盤法
(Roulette Wheel Selection, RWS)，由輪盤法選擇不同費洛蒙更新規則，蟻群演算法根據
輪盤法所選擇的費洛蒙更新規則做下一步的規劃。
我們以java 程式語言實作iACO，以Or-library 提供的82 組標竿問題，考慮機器數
量、工作數量俱不相同之零工式工廠標竿問題測試其效能，本研究所提出的 iACO 演
算法皆能找出比傳統排程方法最早交期日(EDD)，先來先做(FCFS)，最長處理時間(LPT)，
最短處理時間(SPT)，加權最短處理時間(WSPT)，關鍵性比率(CR)更加穩健且良好之解。

Recently, the way to raise benefit to any company is not only increasing sales and
decreasing cost, but improving job scheduling efficiency in the extremely competitive
environment. Therefore, it is necessary for enterprise to provide efficient scheduling plan to
achieve quick response. Especially in the era of Industry 4.0, it is more important to implement
the Intelligent Scheduling System.
Production scheduling problem, mainly, is used to distribute resource efficiently to raise
up production efficiency, to cost down, and to shorten machine idle time while reducing total
working time. Optimizing production scheduling can decrease enterprise operational cost,
production development time and manufacturing time to reach the enterprise goal which are
minimizing the total cost and quick response to customer. Thus, it will be more competitive for
enterprise in market.
This thesis is focus on the Job Shop Scheduling Problem (JSSP), which is an extension
and more complex than the Flow Shop Scheduling Problem. To solve the JSSP, this thesis
proposes a two-stage algorithm, called improved Ant Colony Optimization (iACO), based on
the Ant Colony Optimization Algorithm (ACO) and Roulette Wheel Selection (RWS). In the
iACO, the RWS would choose one from all of the pheromone rule and then schedule for the
JSSP according to rule chose in the RWS.
In this thesis, we implement the iACO by java and test its efficiency and elasticity by 82
job shop benchmark problem from the OR-library. These benchmark problems have different
number of machines and jobs ranging from 66~5010. The iACO algorithm provided in this
thesis find superior and more stable solution than those traditional scheduling methods, such
as Earliest Due Date, First Come First Served, Longest Processing Time, Shortest Processing
Time, Weighted Shortest Processing Time and Critical Ratio.

CONTENTS
摘要..................................................................................................................................... I
ABSTRACT ...................................................................................................................... II
ACKNOWLEDGMENTS ............................................................................................... III
FIGURES ......................................................................................................................... VI
TABLES ......................................................................................................................... VII
CHAPTER 1 INTRODUCTION ....................................................................................... 1
1.1 Motivation ..................................................................................................... 1
1.2 Objectives ...................................................................................................... 2
1.3 Research Structure ......................................................................................... 2
CHAPTER 2 LITERATURE REVIEW............................................................................. 4
2.1 Scheduling Problem Classify ........................................................................ 4
2.2 Scheduling Solution ....................................................................................... 8
2.3 Ant Colony Optimization (ACO) .................................................................. 8
2.3.1 The Basis of the ACO ............................................................................ 8
2.3.2 ACO in Scheduling .............................................................................. 11
CHAPTER 3 PROBLEM FORMULATION AND ANT COLONY OPTIMIZATION .. 13
3.1 Problem ........................................................................................................ 13
3.1.1 Problem Formulation ........................................................................... 13
3.2 Ant Colony Optimization ............................................................................ 13
3.2.1 Construction of the Routes................................................................... 14
3.2.2 State Transition Rule ............................................................................ 15
3.2.3 Pheromone Updating ........................................................................... 15
3.2.4 The Improved ACO.............................................................................. 16
CHAPTER 4 COMPUTATIONAL EXPERIMENTS ..................................................... 19
4.1 Preliminary Test ........................................................................................... 19
4.2 Computational Results ................................................................................. 21
4.3 Summary ...................................................................................................... 25
CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH ....................................... 26
5.1 Conclusions ................................................................................................. 26
5.2 Further Research .......................................................................................... 26
REFERENCES ................................................................................................................ 27
Appendix A. The Best improved Guantt Chart of iACO and Traditional Method. ......... 30
V
Appendix B. The Average case of Guantt Chart of iACO and Traditional Method. ....... 32
Appendix C. The Least improved Guantt Chart of iACO and Traditional Method......... 34
Appendix D. The 10*10 size Guantt Chart of iACO and Traditional Method. ............... 36
Appendix E. The 20*15 size Guantt Chart of iACO and Traditional Method. ............... 38
Appendix F. The 20*5 size Guantt Chart of iACO and Traditional Method. .................. 40
Appendix G. The 10*5 size Guantt Chart of iACO and Traditional Method. ................. 41
Appendix H. The 15*5 size Guantt Chart of iACO and Traditional Method. ................. 43
Appendix I. The 15*10 size Guantt Chart of iACO and Traditional Method. ................. 45
Appendix J. The 20*10 size Guantt Chart of iACO and Traditional Method. ................ 47
Appendix K. The 30*10 size Guantt Chart of iACO and Traditional Method. ............... 49
Appendix L. The 15*15 size Guantt Chart of iACO and Traditional Method. ............... 51
Appendix M. The 50*10 size Guantt Chart of iACO and Traditional Method. .............. 53
Appendix N. The 20*20 size Guantt Chart of iACO and Traditional Method. ............... 56

                                

Adams, J., Balas, E., and Zawack, D. (1988). “Shifting bottleneck procedure for job shop scheduling,” Management Science, 34, 391–401.
Applegate, D., and Cook, W. (1991). “Computational study of the job-shop scheduling problem,” ORSA Journal on Computing, 3, 149–156.
Anitha, J., and Karpagam, M. (2013). “Ant colony optimization using pheromone updating strategy to solve job shop scheduling,” Intelligent Systems and Control, 367–372
Bai, D., Zhang, Z.-H., and Zhang, Q. (2016). “Flexible open shop scheduling problem to minimize makespan Original Research,” Computers and Operations Research, 67, 207–215.
Beckers, R., Deneubourg, J.L., and Goss, S. (1992). “Trails and U-turns in the selection of the shortest path by the ant Lasius niger,” Journal of Theoretical Biology, 159(4), 397–415.
Bersini, H., Oury, C., and Dorigo, M. (1995). “Hybridization of genetic algorithms,” Technical Report, IRIDIA, 95–22.
Catay, B. (2006). “An ant colony optimization approach for the capacitated vehicle routing problem with simultaneous delivery and pick-up,” Proceedings of the EWGT Joint Conferences, 275–282.
Chen, R.-M., Lo, S.-T., Wu, C.-L., and Lin, T.-H. (2008). “An Effective Ant Colony Optimization-Based Algorithm for Flow Shop Scheduling,” IEEE Conference on Soft Computing in Industrial Applications, SMCia, 08.
Cheng, T.C.E., and Sin, C.C.S. (1990). “State-of-the-art review of parallel-machine scheduling research,” European Journal of Operational Research, 47, 271–292.
Dorigo, M., and Gambardella, L.M. (1997a). “Ant colonies for the travelling salesman problem,” BioSystems, 43, 73–81.
Dorigo, M., and Gambardella, L.M. (1997b). “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(1), 29–41.
Doerner, K., Gronalt, M., Hartl, R.F., Reimann, M., Strauss, C., and Stummer, M. (2002). “SavingsAnts for the vehicle routing problem,” Applications of Evolutionary Computing, 11–20.
Gonzalez, T., and Sahni, S. (1976). “Open shop scheduling to minimize finish time,” Journal of The Association Computing Machinary, 23, 665–679.
Goss, S., Aron, S., Deneubourg, J.L., and Pasteels, J.M. (1989). “Self-organized shortcuts in the argentine ant,” Naturwis-senschaften, 76, 579–581.
Gupta, J.N.D., and Stafford Jr., E.F. (2006). “Flowshop scheduling research after five decades,” European Journal of Operational Research, 169, 699–711.
Hecker, F. T., Stanke, M., Becker, T., and Hitzmann, B. (2014). “Application of a modified GA, ACO and a random search procedure to solve the production scheduling of a case study bakery,” Expert Systems with Applications, 41, 5882–5891.
Hojati, M. (2016). “Minimizing make-span in 2-stage disassembly flow-shop scheduling problem,” Computers and Industrial Engineering, 94, 1–5
Holldobler, B., and Wilson, E.O. (1990). The Ants, Springer-Verlag, Berlin.
Hwang, H., and Sun, J.U. (1997). “Production sequencing problem with reentrant work flows and sequence dependent setup times,” Computers and Industrial Engineering, 33, 773–776.
Kir, S., and Yazgan, H. R. (2016). “A sequence dependent single machine scheduling problem with fuzzy axiomatic design for the penalty costs,” Computers and Industrial Engineering, 92, 95–104.
Lai, Y.-L. (2005). Genetic Algorithm for Single-machine Scheduling to Minimize Total Tardiness with the Minimize Total Tardiness with the Minimize Number of Tardy Jobs, master’s thesis, Southern Taiwan University of Science and Technology.
Lei, D., and Guo, X. (2015). “A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents,” Expert Systems with Applications, 42, 23, 9333–9339.
Li, S., Li, G., and Zhang, S. (2005). “Minimizing makespan with release times on identical parallel batching machines,” Discrete Applied Mathematics, 148, 127–134.
Li, S.H., and Tien, P. (2008). “An ant colony optimization on open vehicle routing problem,” Systems Engineering Theory and Practice, 28(6), 81–93.
Li, X., and Gao, L. (2016). “An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem,” International Journal of Production Economics, 174, 93–110.
Lin, F.-T., Kao, C.-Y., and Hsu, C.-C. (1993). “Applying the genetic approach to simulated annealing in solving some NP-hard problems,” IEEE Transactions on Systems, Man and Cybernetics, 23(6), 1752–1767.
Lin, T.H. (2006). An ant colony system for solving the truck and trailer routing problem, master’s thesis, National Kaohsiung First University of Science and Technology.
Meng, Z., and Chen, Q. (2010). “Hybrid Genetic-Ant Colony Algorithm Based Job Scheduling Method Research of Arc Welding Robot,” Proceedings of the 2010 IEEE International Conference on Information and Automation, 20 - 23, Harbin, China.
Niu, L., Zhou, H., and Han, X. (2009). “Dynamic Integration Mechanism for Job-Shop Scheduling Model Base Using Multi-Agent,” International Conference on Information Management, Innovation Management and Industrial Engineering.
Ovacik, I.M., and Uzsoy, R. (1995). “Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times,” International Journal of Production Research, 33, 3173–3192.
Panwalkar, S.S., and Koulamas, C. (2014). “The two-machine no-wait general and proportionate open shop makespan problem,” European Journal of Operational Research, 238(2), 471–475.
Potts, C.N., and Van Wassenhove, L.N. (1982). “Decomposition algorithm for the single machine total tardiness problem,” Operation Research Letters, 1, 177–181.
Ramacher, R., and Mönch L. (2016). “An automated negotiation approach to solve single machine scheduling problems with interfering job sets,” Computers & Industrial Engineering.
Rostami, M., Pilerood, A.E., and Mazdeh, M.M. (2015). “Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment,” Computers and Industrial Engineering, 85, 206–215.
Sevastianov, S.V., and Woeginger, G.J. (1998). “Makespan minimization in open shops: A polynomial time approximation scheme,” Mathematical Programming, Series B, 82, 191–198.
Shih C.-H. (2004). Using Hybrid Genetic Algorithms with Dynamic Weights to Solve the Problem of Single Machine Scheduling on a Sequence Dependent Setup Environment, master thesis, Department of Information Management, Huafan University.
Sobeyko, O., and Mönch, L. (2016). “Heuristic approaches for scheduling jobs in largescale flexible job shops,” Computers and Operations Research, 68, 97–109.
Stutzle1, T. (2000). “Max-min ant system,” Computers and Operations Research, 16(8), 889–914.
Taillard, E. (1990). “Some efficient heuristic methods for the flow shop sequencing problem,” European Journal of Operational Research, 47, 65–74.
Teschemacher, U., and Reinhart, G. (2016) “Enhancing Constraint Propagation in ACObased Schedulers for Solving the Job Shop Scheduling Problem,” Procedia CIRP, 41, 443–447.
Thiruvady, D., Singh, G., Ernst, A. T., and Meyer, B. (2013). “Constraint-based ACO for a shared resource constrained scheduling problem,” International Journal of Production Economics, 141, 230–242.
Wang, Q., and Liu, M. (2010). “Optimization of Task Allocation And Knowledge Workers Scheduling Based on Ant Colony Algorithm,” International Symposium on Intelligence Information Processing and Trusted Computing, IPTC.
Wang, X., Jia Y.-M., and Yu T-L. (2008). “Research on dynamic scheduling operation method in supply chain based on ant colony optimization,” The IEEE International Conference on Industrial Informatics, Daejeon, Korea.
Webster, S.,and Baker, K.R. (1995). “Scheduling groups of jobs on a single machine,” Operations Research, 43, 692–703.

簡易檢索 / 詳目顯示

相關論文