AN ADAPTIVE SIMULATED ANNEALING METHOD FOR ASSEMBLY LINE BALANCING AND A CASE STUDY A THESIS SUBMITTED TO GRADUATE SCHOOL OF NATURAL AND APPLIED SCIENCES OF MIDDLE EAST TECHNICAL UNIVERSITY BY HÜSEYİN GÜDEN IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN INDUSTRIAL ENGINEERING AUGUST 2006 Approval of the Graduate School of Natural and Applied Sciences Prof. Dr. Canan ÖZGEN Director I certify that this thesis satisfies all the requirements as a thesis for the degree of Master of Science. Prof. Dr. Çağlar GÜVEN Head of the Department This is to certify that we have read this thesis and that in our opinion it is fully adequate, in scope and quality, as a thesis for degree of Master of Science. Asst. Prof. Dr. Sedef MERAL Supervisor Examining Committee Members: Assoc. Prof. Dr. Levent KANDİLLER (METU, IE) Asst. Prof. Dr. Sedef MERAL (METU, IE) Prof. Dr. Hadi GÖKÇEN (Gazi U., IE) Onur ÖZKÖK (Baskent U., IE) Asst. Prof. Dr. Bayram Ali SU (Atılım U., IE) I hereby declare that all information in this document has been obtained and presented in accordance with academic rules and ethical conduct. I also declare that, as required by these rules and conduct, I have fully cited and referenced all material and results that are not original to this work. Name, Last name : Hüseyin, GÜDEN Signature : iii ABSTRACT AN ADAPTIVE SIMULATED ANNEALING METHOD FOR ASSEMBLY LINE BALANCING AND A CASE STUDY Güden, Hüseyin M.Sc., Department of Industrial Engineering Supervisor: Asst. Prof. Dr. Sedef Meral August 2006, 195 pages Assembly line balancing problem is one of the most studied NP-Hard problems. NP-Hardness leads us to search for a good solution instead of the optimal solution especially for the big-size problems. Meta-heuristic algorithms are the search methods which are developed to find good solutions to the big-size and combinatorial problems. In this study, it is aimed at solving the multi-objective multi-model assembly line balancing problem of a company. A meta-heuristic algorithm is developed to solve the deterministic assembly line balancing problems. The algorithm developed is tested using the test problems in the literature and the the real life problem of the company as well. The results are analyzed and found to be promising and a solution is proposed for the firm. Keywords: Assembly Line Balancing, Multi-Model Line, Multi- Objective, Meta-Heuristics, Adaptive Simulated Annealing iv ÖZ MONTAJ HATTI DENGELEMESİ İÇİN BİR UYARLANABİLİR TAVLAMA BENZETİMİ YÖNTEMİ VE BİR ÖRNEK ÇALIŞMA Güden, Hüseyin Yüksek Lisans, Endüstri Mühendisliği Bölümü Tez Yöneticisi: Y. Doç. Dr. Sedef Meral Ağustos 2006, 195 sayfa Montaj hattı dengeleme problemi en çok çalışılan NP-Zor problemlerden biridir. NP-Zorluk, özellikle büyük boyutlu problemlerde, en iyi çözüm yerine iyi bir çözümü araştırmamıza neden olur. Modern-sezgisel algoritmalar büyük boyutlu ve kombinatoryal problemlere iyi çözümler bulmak amacıyla geliştirilmiş yöntemlerdir. Bu çalışmada, bir şirketin çok-amaçlı çok- modelli montaj hattı dengeleme problemini çözmek amaçlanmıştır. Bir modern-sezgisel algoritma geliştirilmiş ve deterministik montaj hattı dengeleme problemlerini çözmek üzere sunulmuştur. Geliştirilen algoritma literatürdeki test problemleri ve şirketteki gerçek hayat problemi kullanılarak test edilmiştir. Sonuçlar analiz edilmiş ve umut verici bulunmuşlardır ve firma için bir çözüm önerilmiştir. Anahtar Kelimeler: Montaj Hattı Dengeleme, Çok-Modelli Hat, Çok- Amaç, Modern-Sezgiseller, Uyarlanabilir Tavlama Benzetimi v To my family vi ACKNOWLEDGMENTS I express my great gratitude to Asst. Prof. Dr. Sedef MERAL because of her guidance and contributions throughout the study. I am indebted to İlker İPEKÇİ, my friend, for his invaluable help. I also want to thank to Asst. Prof. Dr. Haldun SÜRAL for his suggestions. Thanks to Yiğit Koray GENÇ, my friend, for his contributions. vii TABLE OF CONTENTS PLAGIARISM ................................................................................................ iii ABSTRACT .....................................................................................................iv ÖZ ..................................................................................................................... v DEDICATION ................................................................................................ vi ACKNOWLEDGMENTS .............................................................................vii TABLE OF CONTENTS ..............................................................................viii LIST OF TABLES ..........................................................................................xi LIST OF FIGURES .......................................................................................xv CHAPTER 1. INTRODUCTION ........................................................................................1 2. ASSEMBLY LINE BALANCING AND THE RELEVANT LITERATURE ............................................................................................ 6 2.1 Assembly Lines ................................................................................... 6 2.2 Assembly Line Balancing Problem ................................................... 9 2.2.1 Single-Model Deterministic ALBP ...........................................10 2.2.1.1 Single-Model Deterministic Type-I ALBP .......................12 2.2.1.1.1 Optimal Seeking Methods .........................................12 2.2.1.1.2 Heuristic Solution Approaches .................................19 2.2.1.2 Single-Model Deterministic Type-II ALBP .....................20 2.2.2 Mixed-Model ALBP ..................................................................21 2.2.3 Multi-Model ALBP ....................................................................26 2.2.4 Meta-Heuristic Approaches ......................................................28 3. THE CASE STUDY ...................................................................................34 3.1 The Company in the Study .............................................................34 3.2 Current Balancing Method and Development of the Proposed Method ............................................................................................34 3.3 Determining the Problem ................................................................37 viii 3.3.1 Tasks ...........................................................................................37 3.3.2 Task Times .................................................................................38 3.3.3 Precedence Relationships Diagram ..........................................39 3.3.4 Zoning Restrictions ....................................................................42 3.4 Integer Programming Studies ..........................................................45 4. THE PROPOSED APPROACH ...............................................................49 4.1 Simulated Annealing (SA) ................................................................49 4.2 Adaptive Simulated Annealing (ASA) .............................................51 4.3 Construction of the Solutions ...........................................................54 4.4 Representation of the Solutions ........................................................55 4.5 Types of Moves ..................................................................................56 4.6 Objectives of ALBP and Evaluation of Solutions ...........................57 4.6.1 Minimization of the Number of Stations .................................57 4.6.2 Minimization of Cycle Time .....................................................58 4.6.3 Maximization of Irregularity between Station Times ............59 4.6.4 Maximization of Smoothness between Station Times ............61 4.6.5 Maximization of Common Tasks that Assigned to the Same Stations between Consecutive Models .....................................62 4.7 Sequencing Problem ..........................................................................63 4.8 The Proposed Methodology...............................................................63 4.8.1 Representation of the Solutions ................................................64 4.8.2 The Move Procedure .................................................................67 4.8.3 The Adaptive Cooling Schedule ...............................................68 4.8.4 Construction of the Initial Solution .........................................70 4.8.5 Evaluating the Solutions ...........................................................70 4.8.5.1 Evaluating the Line Balances ............................................70 4.8.5.2 Evaluating the Sequences ..................................................73 4.8.6 The Overall Methodology .........................................................74 5. EXPERIMENTAL ANALYSIS ............................................................... 77 5.1 Design of the Experiment ..................................................................77 5.2 Single and Mixed-Model Assembly Line Balancing Problems ….79 ix 5.2.1 Test Problems .............................................................................79 5.2.1.1 The First ASA Part ............................................................79 5.2.1.2 The Second ASA Part ........................................................80 5.2.2 The Case Problem ......................................................................81 5.3 Multi-Model Assembly Line Balancing Problems ..........................85 5.4 Current Line Balance and Suggested Line Balances .....................88 5.5 Run Times of the Experiments .........................................................88 6. CONCLUSION AND FURTHER RESEARCH ISSUES .......................90 REFERENCES ...............................................................................................96 APPENDICES A. SKETCH OF THE ASSEMBLY LINE OF THE FIRM .....................105 B. TASK LIST ..............................................................................................106 C. PRECEDENCE RELATIONSHIPS ......................................................116 D. PSEUDOCODE OF THE ALGORITHM .............................................128 E. RESULTS OF THE EXPERIMENTAL RUNS ...................................131 F. CURRENT AND SUGGESTED ASSIGNMENTS ..............................188 x
Description: