Solving assembly scheduling problems with tree-structure precedence constraints: A Lagrangian relaxation approach

Jingyang Xu; Rakesh Nagi

doi:10.1109/TASE.2013.2259816

Solving assembly scheduling problems with tree-structure precedence constraints: A Lagrangian relaxation approach

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1109/TASE.2013.2259816
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

Access to Document

10.1109/TASE.2013.2259816

Fingerprint Dive into the research topics of 'Solving assembly scheduling problems with tree-structure precedence constraints: A Lagrangian relaxation approach'. Together they form a unique fingerprint.

Cite this

@article{9a27d2e9da2e4953b8d5c0c44e15ac11,

title = "Solving assembly scheduling problems with tree-structure precedence constraints: A Lagrangian relaxation approach",

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.",

keywords = "Assembly scheduling, Lagrangian relaxation (LR), Makespan, Parallel machine scheduling, Randomized algorithm, Subgradient search",

author = "Jingyang Xu and Rakesh Nagi",

year = "2013",

month = jul,

day = "1",

doi = "10.1109/TASE.2013.2259816",

language = "English (US)",

volume = "10",

pages = "757--771",

journal = "IEEE Transactions on Automation Science and Engineering",

issn = "1545-5955",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Solving assembly scheduling problems with tree-structure precedence constraints

T2 - A Lagrangian relaxation approach

AU - Xu, Jingyang

AU - Nagi, Rakesh

PY - 2013/7/1

Y1 - 2013/7/1

N2 - 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.

AB - 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.

KW - Assembly scheduling

KW - Lagrangian relaxation (LR)

KW - Makespan

KW - Parallel machine scheduling

KW - Randomized algorithm

KW - Subgradient search

UR - http://www.scopus.com/inward/record.url?scp=84892576600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84892576600&partnerID=8YFLogxK

U2 - 10.1109/TASE.2013.2259816

DO - 10.1109/TASE.2013.2259816

M3 - Article

AN - SCOPUS:84892576600

VL - 10

SP - 757

EP - 771

JO - IEEE Transactions on Automation Science and Engineering

JF - IEEE Transactions on Automation Science and Engineering

SN - 1545-5955

IS - 3

ER -