Exact algorithms for scheduling multiple families of jobs on parallel machines

Zhi Long Chen, Warren Buckler Powell

Research output: Contribution to journalArticle

35 Scopus citations

Abstract

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
Volume50
Issue number7
DOIs
StatePublished - Oct 1 2003

All Science Journal Classification (ASJC) codes

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

Keywords

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

Fingerprint 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