Solving parallel machine scheduling problems by column generation

Zhi Long Chen, Warren Buckler Powell

Research output: Contribution to journalArticle

131 Scopus citations

Abstract

We consider a class of problems of scheduling n jobs on m identical, uniform, or unrelated parallel machines with an objective of minimizing an additive criterion. We propose a decomposition approach for solving these problems exactly. The decomposition approach first formulates these problems as an integer program, and then reformulates the integer program, using Dantzig-Wolfe decomposition, as a set partitioning problem. Based on this set partitioning formulation, branch-and-bound exact solution algorithms can be designed for these problems. In such a branch-and-bound tree, each node is the linear relaxation problem of a set partitioning problem. This linear relaxation problem is solved by a column generation approach where each column represents a schedule on one machine and is generated by solving a single machine subproblem. Branching is conducted on variables in the original integer programming formulation instead of variables in the set partitioning formulation such that single machine subproblems are more tractable. We apply this decomposition approach to two particular problems: the total weighted completion time problem and the weighted number of tardy jobs problem. The computational results indicate that the decomposition approach is promising and capable of solving large problems.

Original languageEnglish (US)
Pages (from-to)78-92
Number of pages15
JournalINFORMS Journal on Computing
Volume11
Issue number1
DOIs
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Branch and bound
  • Column generation
  • Dantzig-Wolfe decomposition
  • Parallel machine scheduling
  • Set partitioning

Fingerprint Dive into the research topics of 'Solving parallel machine scheduling problems by column generation'. Together they form a unique fingerprint.

  • Cite this