Column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

Zhi Long Chen, Warren Buckler Powell

Research output: Contribution to journalArticle

61 Scopus citations

Abstract

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig-Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.

Original languageEnglish (US)
Pages (from-to)220-232
Number of pages13
JournalEuropean Journal of Operational Research
Volume116
Issue number1
DOIs
StatePublished - Jul 1 1999

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem'. Together they form a unique fingerprint.

  • Cite this