Browse

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

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
홍성원
Advisor
이경식
Major
공과대학 산업공학과
Issue Date
2017-02
Publisher
서울대학교 대학원
Keywords
Car resequencing problemAutomotive paint shopsDynamic programmingBranch-and-cut algorithmHeuristic algorithm
Description
학위논문 (석사)-- 서울대학교 대학원 : 산업공학과, 2017. 2. 이경식.
Abstract
This 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.
Language
English
URI
http://hdl.handle.net/10371/123615
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Theses (Master's Degree_산업공학과)
  • mendeley

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

Browse