Bicriterion single machine scheduling with resource dependent processing times

Edwin Tai Chiu Cheng, Adam Janiak, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

72 Citations (Scopus)


A bicriterion problem of scheduling jobs on a single machine is studied. The processing time of each job is a linear decreasing function of the amount of a common discrete resource allocated to the job. A solution is specified by a sequence of the jobs and a resource allocation. The quality of a solution is measured by two criteria, F1 and F2. The first criterion is the maximal or total (weighted) resource consumption, and the second criterion is a regular scheduling criterion depending on the job completion times. Both criteria have to be minimized. General schemes for the construction of the Pareto set and the Pareto set ∈-approximation are presented. Computational complexities of problems to minimize F1 subject to F2 ≤ K and to minimize F2 subject to F1 ≤ K, where K is any number, are studied for various functions F1 and F2. Algorithms for solving these problems and for the construction of the Pareto set and the Pareto set ∈-approximation for the corresponding bicriterion problems are presented.
Original languageEnglish
Pages (from-to)617-630
Number of pages14
JournalSIAM Journal on Optimization
Issue number2
Publication statusPublished - 1 Jan 1998


  • Approximation
  • Bicriterion scheduling
  • Resource allocation
  • Single machine scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this