簡易檢索 / 詳目顯示

回結果列表
研究生： 廖錚圻
Cheng-Chi Liao
論文名稱： 應用蟻群最佳化求解敏捷製造排程問題
An Ant Colony Optimization Algorithm for Scheduling in Agile Manufacturing
指導教授： 廖慶榮
Ching-Jong Liao
口試委員: 鄭元杰
Yuan-Jye Tseng
羅士哲
Shih-Che Lo
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2006
畢業學年度： 94
語文別： 英文
論文頁數： 38
中文關鍵詞： 排程 、敏捷製造 、螞蟻演算法 、最大完工時間 、分支界限演算法
外文關鍵詞： Ant Colony Opti
相關次數： 點閱：380  下載：7 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  •  上一筆

    • 利用低成本在短時間內生產客製化產品是達到敏捷製造 (Agile Manufacturing) 的其中一種目標。為了達成這種目標，組裝驅動差異化策略已在許多敏捷製造的相關文獻被提及到。在本篇論文中，我們將描述一個應用組裝驅動差異化策略的生產製造系統。此系統包含加工及組裝兩個階段，在加工階段包含了一部加工機器，而在組裝階段則包含了多部組裝工作站。我們提出利用螞蟻演算法 (Ant Colony Optimization; ACO) 求解最大完工時間最小化的排程問題。所提出的螞蟻算法將融入由本篇所發展的派工法則作為新的貪婪法則，並利用變動鄰域搜尋法作為局部搜尋，使螞蟻演算法增進更多的效能和效益。為了驗證演算法的績效，此篇論文也提出分支界限演算法以得到問題的最佳解。由實驗結果得知，在此問題下，螞蟻演算法優於目前已知的其他演算法，不但改善了其績效而且也節省了求解的時間。

    Producing customized products in a short time at low cost is one of the goals of agile manufacturing. To achieve this goal, an assembly-driven differentiation strategy has been proposed in the agile manufacturing literature. In this thesis, we address a manufacturing system that applies the assembly-driven differentiation strategy. The system consists of machining and assembly stages, where there is a single machine at the machining stage and multiple identical assembly stations at the assembly stage. An ant colony optimization (ACO) algorithm is developed for solving the scheduling problem of determining the sequence of parts to be produced in the system so as to minimize the maximum completion time (or makespan). The ACO algorithm uses a new dispatching rule as the heuristic desirability and variable neighborhood search as the local search to make it more efficient and effective. To evaluate the performance of heuristic algorithms, a branch-and-bound procedure is proposed for deriving the optimal solution to the problem. Computational results show that the proposed ACO algorithm is superior to the existing algorithm, not only improving the performance but also decreasing the computation time.

    CONTENTS CHINESE ABSTRACT .i ENGLISH ABSTRACT ii ACKNOWLEDGEMENTS ...iii CONTENTS .iv LIST OF FIGURES .vi LIST OF TABLES ………..vii Chapter 1. INTRODUCTION 1 1.1. Overview 1 1.2. Problem statement 2 1.3. Research process and thesis organization 5 Chapter 2. LITERATURE REVIEW 7 2.1. Agile manufacturing 7 2.2. Scheduling machining/assembly shop in agile manufacturing 8 2.3. Background and review of ACO 10 Chapter 3. PROPOSED ALGORITHMS 12 3.1. The proposed dispatching rule 12 3.2. The proposed ACO algorithm 15 3.2.1. Variable neighborhood search 15 3.2.2. The ACO algorithm 16 3.3. The branch-and-bound procedure 19 Chapter 4. COMPUTATION RESULTS 21 4.1. Test problems and performance measure 21 4.2. Parameters setting 22 4.3. Results and discussions 26 Chapter 5. CONCLUSIONS AND FUTURE RESEARCH 29 REFERENCES 31 APPENDIX. THE PROPOSED ACO ALGORITHM 38 LIST OF FIGURES Figure Page 1. Example of (a) a product and its simple digraph and (b) a product and its complex digraph 3 2. The machining and assembly environment of the problem 4 3. The flow chart of the research 6 4. Assembly sequence of the product in Example 1 13 5. Gantt chart of schedule obtained from the new dispatching rule 14 6. Gantt chart of schedule obtained from the heuristic of He and Babayan (2002) 14 7. The framework of local search 17 8. The test of parameter 23 9. The test of parameter 23 10. The test of parameter 24 11. The test of parameter 24 12. The test of parameter 25 13. The test of parameter 25 LIST OF TABLES Table Page 1. Classification of agile manufacturing literature 8 2. Research on machining/assembly shops 10 3. ACO application in combinatorial optimization problems 11 4. Machining and assembly times for Example 1 13 5. The computed values of and for Example 1 14 6. The levels of factors for the experiments 21 7. The test of times for VNS 26 8. Comparative evaluation of the new dispatching rule with the heuristic of He and Babayan (2002) 27 9. Comparative evaluation of algorithms with and without the use of VNS 28 10. Comparative evaluation of ACO with HASA of Gaafar and Masoud (2005) 28

    Avanthay, C., Hertz, A., and Zufferey, N., A variable neighborhood search for graph coloring. European Journal of Operational Research, 2003, 151, 379-388.
    Bautista, J. and Pereira, J., Ant algorithms for a time and space constrained assembly line balancing problem. European Journal of Operational Research, In Press (Available online at: www.sciencedirect.com accessed 6 February 2006).
    Blum, C. and Sample, M., An ant colony optimization algorithm for shop scheduling problems. Journal of Mathematical Modelling algorithms, 2004, 3, 285-308.
    Bullnheimer, B., Hartl, R. F., and Strauss, C., An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 1999, 89, 319-28.
    Corry, P. and Kozan, E., Ant colony optimization for machine layout problems. Computational Optimization and Applications, 2004, 28, 287-310.
    Den Besten, M., Stützle, T., and Dorigo, M., Ant colony optimization for the total weighted tardiness problem. Proceeding PPSN VI, 6th International Conference Parallel Problem Solving from Nature, 2000, pp. 611-20.
    Doctor, S. R., Cavalier, T. M., and Egbelu, P. J., Scheduling for machining and assembly in a job shop environment. International Journal of Production Research, 1993, 31, 1275-1297.
    Don-Taylor, G., Design for global manufacturing and assembly. Progress in Material Handling Research, Ann Arbor, MI, 1996, pp. 9-13.
    Dorigo, M. and Gambardella, L. M., Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1, 53-66.
    Dorigo, M., Maniezzo, V., and Colorni A., Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on System, Man and Cybermetics, 1996, 26, 29-41.
    Drummond, L. M. A., Vianna, L. S., Silva, M. B., and Ochi, L. S., Distribution parallel metaheuristics based on GRASP and VNS for solving the traveling purchaser problem. Proceedings of the 9th International Conference on Parallel and Distributed System, 2002, pp. 257-263.
    Feng, S. C. and Zhang, C. C., A modular architecture for rapid development of CAPP system for agile manufacturing. IIE Transactions, 1998, 30, 893-903.
    Gaafar, L. K. and Masoud, S. A., Genetic algorithms and simulated annealing for scheduling in agile manufacturing. International Journal of Production Research, 2005, 43, 3069-3085.
    Gagné, C., Gravel, M., and Price, W. L., Solving real car sequencing problems with ant colony optimization. European Journal of Operational Research, In Press (Available online at: www.sciencedirect.com accessed 6 June 2005).
    Gagné, C., Price, W. L., and Gravel, M., Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. Journal of the Operational Research Society, 2002, 53, 895-906.
    Gajpal, Y. and Rajendran, C., An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops. International Journal of Production Economics, 2006, 101, 259-272.
    Gambardella, L. M., Taillard É. D., and Dorigo, M., Ant colonies for the quadratic assignment problem. Journal of Operational Research Society, 1999, 50, 167-76.
    Gambardella, L. M., Taillard, É. D., and Agazzi, G., A multiple ant colony system for vehicle routing problems with time windows. New Ideas in Optimization, edited by Corne, D., Dorigo, M., and Glover, F., pp. 63-76, 1999 (McGraw-Hill: United Kingdom).
    Glover, F. and Kochenberger, G. A., Handbook of Metaheuristics, 2003 (Kluwer Academic Publisher: Boston).
    Gunasekaran, A., Agile manufacturing enablers and an implementation framework. International Journal of Production Research, 1998, 36, 1223-1247.
    Hansen, P. and Mladenović, N., Variable neighborhood search for the p-Median. Location Science, 1997, 5, 207-226.
    He, D., Babayan, A., and Kusiak, A., Scheduling manufacturing system in an agile environment. Robotics and Computer Integrated Manufacturing, 2001, 17, 2461-2481.
    He, D. and Babayan, A., Scheduling manufacturing system for delayed product differentiation in agile manufacturing. International Journal of Production Research, 2002, 40, 2461-2481.
    He, D. W. and Kusiak, A., The delayed product differentiation strategy in agile manufacturing. IERC Proceedings 1995, 4th Annual Industrial Engineering Research Conference. Norcross, GA, USA, 1995, pp. 701-708.
    He, D. W. and Kusiak, A., Production planning and scheduling in virtual manufacturing. IERC Proceedings 1996, 6th Annual Industrial Engineering Research Conference. 1996, pp. 491-496.
    He, D. and Kusiak, A., Designing an assembly line for modular products. Computers and Industrial Engineering, 1998, 34, 37-52.
    He, D. W., Kusiak, A., and Tseng T. L., Delayed product differentiation: a design and manufacturing perspective. Computer-Aided Design, 1998, 30, 105-113.
    Holthaus, O. and Rajendran, C., A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs. Journal of the Operation Research Society, 2005, 56, 947-953.
    Kusiak, A., Aggregate scheduling of a flexible machining and assembly system. IEEE Transactions on Robotics and Automation, 1989, 5, 451-459.
    Lee, C. Y., Cheng, T. C. E., and Lin, B. M. T., Minimizing the makespan in the 3-machine assembly type flowshop scheduling. Management Science, 1993, 39, 616-625.
    Lee, G. H., Reconfigurability consideration design of components and manufacturing systems. International Journal of Advanced Manufacturing Technology, 1997, 13, 376-386.
    Lee, G. H., Designs of components and manufacturing systems for agile manufacturing. International Journal of Production Research, 1998, 36, 1023-1044.
    Liao, C. J. and Juan, H. C., An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers and Operations Research. In Press (Available online at: www.sciencedirect.com accessed 30 August 2005).
    Lin, B. M. T., Cheng, T. C. E., and Chou, A. S. C., Scheduling in an assembly-type production chain with batch transfer. Omega, In Press (Available on line at: www.sciecedirect.com accessed 28 June 2005).
    Mason-Jones, R. and Towill, D. R., Total cycle time compression and the agile supply chain. International Journal of Production Economics, 1999, 62, 61-73.
    Meller, R. D. and Mungwattana, A., Multi-shuttle automated storage/retrieval systems. IIE Transactions, 1997, 29, 925-938.
    Merkle, D., Middendorf, M., and Schmeck, H., Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 2002, 6, 333-46
    Minis, I., Herrmann, J. W., Lam, G., and Lin, E., A generative approach for concurrent manufacturability evaluation and subcontractor selection. Journal of Manufacturing Systems, 1999, 18, 383-395.
    Mladenović, N. and Hansen, P., Variable neighborhood search. Computers and Operations Research, 1997, 24, 1097-1100.
    Montreuil, B., Venkatadri, U., and Rardin, R. L., Fractal layout organization for job shop environments. International Journal of Production Research, 1999, 37, 501-521.
    Naylor, J. B., Naim, M. M., and Berry, D., Leagility: Integrating the lean and agile manufacture paradigms in the total supply chain. International Journal of Production Research, 1999, 62, 107-118.
    Olsen, K. A. and Saetre, P., Managing product variability by virtual products. International Journal of Production Research, 1997, 35, 2093-2107.
    Perry, M., Sohal, A. S., and Rumpf, P., Quick response supply chain alliance in the Australian textiles, clothing and footwear industry. International Journal of Production Economics, 1999, 62, 119-132.
    Plonka, F. E., Developing a lean production and agile work force. International Journal of Human Factors in Manufacturing, 1999, 7, 11-20.
    Quinn, R. D., Causey, G. C., Merat, F. L., Sargent, D. M., Barendt, N. A., Newman, W. S., Velasco, V. B., Podgurski, A., Jo, J.-Y., Sterling, L. S., and Kim, Y., An agile manufacturing workcell design. IIE Transactions, 1997, 29, 901-909.
    Rajendran, C. and Ziegler, H., Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Computers and Industrial Engineering. 2005, 48, 789-797.
    Ribeiro, C. C. and Souza, M. C., Variable neighborhood search for the degree-constrained minimum spanning tree problem. Discrete Applied Mathematics, 2002, 118, 43-54.
    Sanchez, L. M. and Nagi, R., A review of agile manufacturing systems. International Journal of Production Research, 2001, 39, 3561-3600.
    Sarmiento, A. M. and Nagi, R., A review of integrated analysis of production-distribution systems. IIE Transactions Special Issue on Manufacturing Logistics, 1999, 11, 1061-1074.
    Silva, C. A., Runkler, T. A., Sousa, J. M., and Palm, R., Ant colonies as logistic process optimizers. Ant algorithms-proceedings of ANTS 2002-Third international workshop. Lecture Notes in Computer Science, 2463, edited by Dorigo, M., Di Caro, G., and Samples, M., pp.76-87, 2002 (Springer: Berlin).
    Song, L. and Nagi, R., Design and implementation of a virtual information system for agile manufacturing. IIE Transactions, 1997, 20, 839-857.
    Strader, T. J., Lin, F.-R., and Shaw, M. J., Information infrastructure for electronic virtual organization management. Design Support Systems, 1998, 23, 75-94.
    Stützle, T. and Hoos, H. H., The MAX-MIN ant system and local search for the traveling salesman problem. IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference, edited by Baeck, T., Michalewicz, Z., and Yao, X., 1997.
    Stützle, T. and Hoos, H. H., The MAX-MIN ant system and local search for combinatorial optimization problems. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, edited by Martello, S. S., Osman, I. H., and Roucairol, C., 1998.
    Stützle, T. and Hoos, H. H., Max-min ant system. Future Generation Computer System, 2000, 16, 889-914.
    Sun, X., Morizawa, K., and Nagasawa, H., Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling. European Journal of Operational Research, 2003, 146, 498-516.
    Syam, S. S., Model for the capacitated p-facility location problem in global environments. Computers and Operations Research, 1997, 24, 1005-1016.
    T’kindt, V., Monmarché, N., Tercinet, F., and Laügt, D., An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research, 2002, 42, 250-57
    Tu, Y., Production planning and control in virtual one of kind production company. Computers and Industrial Engineering. 1997, 34, 271-283.
    Venkatadri, U., Rardin, R. L., and Montreuil, B., A design methodology for fractal layout organization. IIE Transactions, 1997, 29, 911-924.
    Warnecke, R. J., Automatic assembly-state of the art. Proceedings of the 3rd International Conference of Assembly Automation, Boeblingen, Germany, pp. 1-14.
    Ying, G. C. and Liao, C. J., Ant colony system for permutation flow-shop sequencing. Computers and Operations Research, 2004, 31, 791-801.
    Yokoyama, M., Hybrid flow-shop scheduling with assembly operation. International Journal of Production Economics, 2001, 73, 103-116.
    Yokoyama, M., Scheduling for two-stage production system with setup and assembly operations. Computers and Operations Research, 2004, 31, 2063-2078.
    Yokoyama, M. and Santos, D. L., Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 2005, 161, 754-770.
    Yusuf, Y. Y., Sarhadi, M., and Gunasekaran, A., Agile manufacturing: The drivers, concepts and attributes. International Journal of Production Economics, 1999, 62, 33-43.
    Zhou, Q. and Besant, C. B., Information management in production planning for a virtual enterprise. International Journal of Production Research, 1999, 37, 207-218.

    QR CODE