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 theLRproblem 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.
Original language | English (US) |
---|---|
Pages (from-to) | 757-771 |
Number of pages | 15 |
Journal | IEEE Transactions on Automation Science and Engineering |
Volume | 10 |
Issue number | 3 |
DOIs | |
State | Published - Jul 1 2013 |
Externally published | Yes |
Keywords
- Assembly scheduling
- Lagrangian relaxation (LR)
- Makespan
- Parallel machine scheduling
- Randomized algorithm
- Subgradient search
ASJC Scopus subject areas
- Control and Systems Engineering
- Electrical and Electronic Engineering