DocumentCode :
71093
Title :
Solving assembly scheduling problems with tree-structure precedence constraints: A Lagrangian relaxation approach
Author :
Jingyang Xu ; Nagi, Rakesh
Author_Institution :
Dept. of Ind. & Syst. Eng., Univ. at Buffalo (SUNY), Buffalo, NY, USA
Volume :
10
Issue :
3
fYear :
2013
fDate :
Jul-13
Firstpage :
757
Lastpage :
771
Abstract :
In this paper, we consider an assembly scheduling problem (ASP) with tree-structured precedence constraints. In our problem, there are a number of work centers. Each work center contains a number of machines of the same functionality. The job to be processed via this system is a job with tree-structure precedence constraints. Each operation in the job has a designated work center. We propose a mixed integer linear programming formulation and solve the problem with a Lagrangian relaxation (LR) approach. We solve the subproblems of the LR problem via a heuristic method and generate feasible solutions via a randomized list scheduling algorithm. Near-optimal results are obtained and the computational time is within a few seconds for problems with size up to 20 machines and 300 operations.
Keywords :
assembling; bills of materials; integer programming; job shop scheduling; linear programming; trees (mathematics); ASP; LR approach; Lagrangian relaxation approach; assembly scheduling problem; bill-of-material; heuristic method; job shop scheduling problem; mixed integer linear programming formulation; randomized list scheduling algorithm; shared manufacturing facility; tree-structure precedence constraint; work center; Assembly scheduling; Lagrangian relaxation (LR); makespan; parallel machine scheduling; randomized algorithm; subgradient search;
fLanguage :
English
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1545-5955
Type :
jour
DOI :
10.1109/TASE.2013.2259816
Filename :
6517989
Link To Document :
بازگشت