Bi-criteria scheduling with machine assignment costs

Joseph Y.T. Leung, Kangbok Lee, Michael L. Pinedo

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


We consider parallel machine scheduling problems where the processing of the jobs on the machines involves two types of costs. The first type of cost is similar to one of two classical objective functions that are often considered in scheduling theory; it is either the total completion time or the makespan. The second type of cost involves an actual cost associated with the processing of a specific job on a given machine. Each job-machine combination may have a different cost. The optimization problems considered may be structured in several different ways. We consider first the two objectives hierarchically; that is, first one objective is being optimized and the class of optimal solutions is determined, and then the second objective is optimized among all schedules that are optimal with respect to the first objective. Another structure that is considered involves the minimization of a linear combination of the two objective functions. We present an overview of the computational complexities of all the problems considered in our framework.

Original languageEnglish (US)
Pages (from-to)321-329
Number of pages9
JournalInternational Journal of Production Economics
Issue number1
StatePublished - Sep 2012

All Science Journal Classification (ASJC) codes

  • Economics and Econometrics
  • General Business, Management and Accounting
  • Industrial and Manufacturing Engineering
  • Management Science and Operations Research


  • Machine cost
  • Makespan
  • Multi-objective scheduling
  • Parallel machines
  • Preemptive and nonpreemptive schedules
  • Total completion time


Dive into the research topics of 'Bi-criteria scheduling with machine assignment costs'. Together they form a unique fingerprint.

Cite this