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

Jingyang Xu, Rakesh Nagi

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)757-771
Number of pages15
JournalIEEE Transactions on Automation Science and Engineering
Volume10
Issue number3
DOIs
StatePublished - Jul 1 2013
Externally publishedYes

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

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