Exact algorithms for scheduling multiple families of jobs on parallel machines

Zhi Long Chen, Warren Buckler Powell

Research output: Contribution to journalArticlepeer-review

42 Scopus citations


In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time.

Original languageEnglish (US)
Pages (from-to)823-840
Number of pages18
JournalNaval Research Logistics
Issue number7
StatePublished - Oct 2003

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


  • Branch and bound
  • Column generation
  • Parallel machine scheduling
  • Set partitioning type formulation
  • Setup times


Dive into the research topics of 'Exact algorithms for scheduling multiple families of jobs on parallel machines'. Together they form a unique fingerprint.

Cite this