Publications

Detailed Information

Optimization Algorithms for a Car Resequencing Problem : 차량 재 정렬 문제를 위한 최적화 알고리즘

DC Field Value Language
dc.contributor.advisor이경식-
dc.contributor.author홍성원-
dc.date.accessioned2017-07-14T03:25:32Z-
dc.date.available2017-07-14T03:25:32Z-
dc.date.issued2017-02-
dc.identifier.other000000140847-
dc.identifier.urihttps://hdl.handle.net/10371/123615-
dc.description학위논문 (석사)-- 서울대학교 대학원 : 산업공학과, 2017. 2. 이경식.-
dc.description.abstractThis thesis considers a car resequencing problem (CRP) in automotive paint shops, where a set of cars conveyed from the upstream shop to one of the multiple conveyors is retrieved sequentially before painting operation. The aim of CRP is to obtain a car retrieval sequence which minimizes the sequence-dependent changeover cost in the paint shop. The changeover cost is incurred when two consecutive cars do not share the same color. In this study, we propose exact and heuristic algorithms for CRP. First, we consider a mathematical formulation of CRP and propose a branch-and-cut algorithm. Second, we present an accelerated dynamic programming algorithm by using strong combinatorial lower bounds, which outperforms existing dynamic programming algorithm. We also present several heuristic algorithms based on the proposed accelerated dynamic programming algorithm that yield good solutions quickly for large-sized instances. Computational results show that the proposed algorithms are more efficient than existing approaches and also more applicable in practice.-
dc.description.tableofcontentsChapter 1 Introduction 1
1.1 Background 1
1.2 Literature Review 4
1.3 Existing Approaches and Research Motivations 6
1.4 Organization of the Thesis 8
Chapter 2 Problem Definition and Mathematical Formulation 9
2.1 Problem Definition 9
2.2 Network Representation 11
2.3 Mathematical Formulation 12
Chapter 3 Exact Algorithms 15
3.1 Branch-and-Cut Algorithm 15
3.1.1 Cutset Inequalities 16
3.1.2 Separation Procedure 17
3.1.3 Overall Algorithm 19
3.2 Accelerated Dynamic Programming Algorithm 21
3.2.1 Dynamic Programming Algorithm 21
3.2.2 Computing Lower Bounds 24
3.2.3 Overall Algorithm 29
Chapter 4 Heuristic Algorithms 31
4.1 Fix-and-Resequencing Heuristics 31
4.2 ADP-Based Heuristics 34
Chapter 5 Computational Results 37
5.1 Test Problems 37
5.2 Test Results on NC Instances 39
5.3 Test Results on GC Instances 48
Chapter 6 Conclusion 57
Bibliography 59
국문초록 63
-
dc.formatapplication/pdf-
dc.format.extent2897385 bytes-
dc.format.mediumapplication/pdf-
dc.language.isoen-
dc.publisher서울대학교 대학원-
dc.subjectCar resequencing problem-
dc.subjectAutomotive paint shops-
dc.subjectDynamic programming-
dc.subjectBranch-and-cut algorithm-
dc.subjectHeuristic algorithm-
dc.subject.ddc670-
dc.titleOptimization Algorithms for a Car Resequencing Problem-
dc.title.alternative차량 재 정렬 문제를 위한 최적화 알고리즘-
dc.typeThesis-
dc.contributor.AlternativeAuthorSungwon Hong-
dc.description.degreeMaster-
dc.citation.pagesvii, 63-
dc.contributor.affiliation공과대학 산업공학과-
dc.date.awarded2017-02-
Appears in Collections:
Files in This Item:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share