研究生: |
林孝柔 Hsiao-Jou Lin |
---|---|
論文名稱: |
混合式基因演算法於多目標彈性零工式工廠排程問題之研究 Flexible Job Shop Scheduling using a Multiobjective Memetic Algorithm |
指導教授: |
蔣宗哲
Chiang, Tsung-Che |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2011 |
畢業學年度: | 99 |
語文別: | 中文 |
論文頁數: | 49 |
中文關鍵詞: | 多目標 、柏拉圖最佳化 、彈性零工式工廠排程問題 、混合式基因演算法 、禁忌搜尋法 、變動鄰域尋優演算法 |
英文關鍵詞: | multiobjective, Pareto optimal, flexible job shop scheduling problem, memetic algorithm, tabu search, variable neighborhood descent |
論文種類: | 學術論文 |
相關次數: | 點閱:376 下載:46 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
生產排程主要是透過有效地資源分配來提高生產效率、降低生產成本,為了能達到既定的目標 (滿足交貨時間或縮短機台閒置時間),生產排程至今仍是多目標最佳化領域中常見的研究題目。大部分的排程問題都是屬於組合最佳化問題並且難以求出最佳解,零工式工廠生產排程問題就是屬於此問題之一,多目標彈性零工式工廠排程問題 (Multi-objective Flexible Job-shop Scheduling Problem) 旨在如何分配適當的機台給每一零件的製程使用 (路由問題)以及如何將這些已選定機台的製程排序 (排程問題) 以最小化完工時間 (makespan)、最大機台工作量 (maximal machine workload)、總機台工作量 (total workload) 。
本論文提供基因演算法 (Genetic Algorithm, GA) 搭配禁忌搜尋法 (Tabu Search, TS) 去解多目標彈性零工式工廠生產排程問題,有別於文獻中合併函式 (aggregation function) 適應值 (fitness) 的算法,我們利用柏拉圖法 (Pareto) 計算適應值以求得柏拉圖最佳解 (Pareto front)。其中在禁忌搜尋法中加入變動鄰域尋優演算法 (Variable Neighborhood Descent, VND),從開始時間到完工時間的最長路徑 (critical path) 找到關鍵製程 (critical operations),利用交換與插入關鍵製程改變最長路徑來縮短最小完工時間。
實驗問題包含Kacem data與BR data共十五個測試問題。本研究在Kacem data皆能透過一次的實驗就能找到過去所有文獻中提出的最佳解,而BR data則有五個測試問題可以更新文獻中的最佳解。
[1] Cheng, R., Gen, M., & Tsujimura, Y. (1996) A Tutorial Survey of Job-shop Scheduling Problems Using Genetic Algorithms--I. Representation. Computers and Industrial Engineering , 30(4), 983 – 997.
[2] Cheng, R., Gen, M., & Tsujimura, Y. (1999) A Tutorial Survey of Job-shop Scheduling Problems Using Genetic Algorithms, Part II: Hybrid Genetic Search Strategies. Computers and Industrial Engineering, 36(2), 343 – 364.
[3] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002, April) A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182 – 197.
[4] Zitzler, E., Laumanns, M., & Thiele, L. (2001) SPEA2-Imprving the Strength Pareto Evolutionary Algorithm. Computer Engineering and Networks Laboratory (TIK), Report 103.
[5] Zhang, Q., & Li, H. (2007) MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transation on Evolutionary Computation, 11 (6), 712 – 731.
[6] Nowicki, E. & Smutnicki C. (1996) A Fast Taboo Search Algorithm for the Jobs-shop Problem. Management Science, 42, 797 –813.
[7] Mastrolilli, M., & Gambardella, L.M. (2000) Effective Neighborhood Functions for the Flexible Job Shop Problem. Journal of Scheduling, 3(1), 3 – 20.
[8] Bozejko, W., Uchronski, M., & Wodecki, M. (2010) Parallel Hybrid Metaheuristics for the Flexible Job Shop Problem. Computers and Industrial Engineering, 59, 323 –333.
[9] Pezzella, F., Morganti, G., & Ciaschetti, G. (2008) A Genetic Algorithm for the Flexible Job-shop Scheduling Problem. Computers and Operations Research, 35(10), 3202 – 3212.
[10] Kacem, I., Hammadi, S., & Borne, P. (2002) Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-shop Scheduling Problems. IEEE Transactions on System, Man, and Cybernetics – Part C, 32(1), 1 – 13.
[11] Yazdani, M., Amiri, M., & Zandieh, M. (2010) Flexible Job-shop Scheduling with Parallel Variable Neighborhood Search Algorithm. Expert Systems with Applications, 37(1), 678 – 687.
[12] Bagheri, A., Zandieh, M., Mahdavi, I., & Yazdani, M. (2010) An Artificial Immune Algorithm for the Flexible Job-shop Scheduling Problem. Future Generation Computer Systems, 26, 533 –541.
[13] Zribi, N., Kacem, I., A. Kamel, E., & Borne, P. (2007) Assignment and Scheduling in Flexible Job-shops by Hierarchical Optimization. IEEE, 37(4), 652 – 661.
[14] Xia, W., Wu, Z. (2005) An Effective Hybrid Optimization Approach for Multi-objective Flexible Job-shop Scheduling Problem. Computer and Industrial Engineering, 48(1), 409 – 425.
[15] Gao, J., Gen, M., Sun, L., & Zhao, X. (2007) A Hybrid of Genetic Algorithm and Bottleneck Shifting for Multiobjective Flexible Job Shop Scheduling Problems. Computers and Industrial Engineering, 53, 149 –162.
[16] Gao, J., Sun, L., & Gen, M. (2008) A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems. Computers and Operations Research, 35(9), 2892 – 2907.
[17] Zhang, G., Shao, X., Li, P., & Gao, L. (2009) An Effective Hybrid Particle Swarm Optimization Algorithm for Multi-objective Flexible Job-shop Scheduling Problem. Computers and Industrial Engineering, 56(4), 1309 – 1318.
[18] Xing, L., Chen, Y., & Yang, K. (2009) Multi-objective Flexible Job Shop Schedule: Design and Evaluation by Simulation Modeling. Applied Soft Computing, 9(1), 362 – 376.
[19] Xing, L., Chen, Y., Wang, P., Zhao, Q., & Xiong, J. (2010) A Knowledge-based Ant Colony Optimization for Flexible Job Shop Scheduling Problems. Applied Soft Computing, 10(3), 888 – 896.
[20] Li, J.Q., Pan, Q.K., & Liang, Y.C. (2010) An Effective Hybrid Tabu Search Algorithm for Multiobjective Flexible Job-shop Scheduling Problems. Computers & Industrial Engineering 59, 647 – 662.
[21] Xing, L., Chen, Y., & Yang, K. (2009) An Efficient Search Method for Multi-objective Flexible Job Shop Scheduling Problems. Journal of Intelligent Manufacturing, 20, 283 – 293.
[22] Moslehi, G., Mahnam, M. (2011) A Pareto Approach to Multi-objective Flexible Job-shop Scheduling Problem using Particle Swarm Optimization and Local Search. International Journal of Production Economics 129, 14 – 22.
[23] Mostaghim, S., Teich, J. (2003) Strategies for Finding Local Guides in Multi-objective Particle Swarm Optimization. In: Proceedings of the IEEE Swarm Intelligence Symposium, pp.26 – 33.
[24] Giffler, B., Thomspon, G.L. (1960) Algorithms for Solving Production-scheduling Problems. Operations Research, 8, 487 –503.
[25] Lee, K.M., Yamakawa, T., & Lee, K.M. (1998) A Genetic Algorithm for General Machine Scheduling Problems. In: Proceedings of International Conference on Knowledge-based Intelligent Electronic Systems, pp. 60 – 66.
[26] Brandimarte, P. (1993) Routing and Scheduling in a Flexible Job Shop by Tabu Search. Annals of Operations Research 41, 157 – 183.