Single machine scheduling of unit-time jobs with controllable release dates

Edwin Tai Chiu Cheng, Natalia V. Shakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)


The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n4) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an ε-approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.
Original languageEnglish
Pages (from-to)293-311
Number of pages19
JournalJournal of Global Optimization
Issue number2-3
Publication statusPublished - 1 Nov 2003


  • Controllable release dates
  • Deterministic
  • Multiple criteria
  • Scheduling
  • Single machine

ASJC Scopus subject areas

  • Applied Mathematics
  • Control and Optimization
  • Management Science and Operations Research
  • Global and Planetary Change


Dive into the research topics of 'Single machine scheduling of unit-time jobs with controllable release dates'. Together they form a unique fingerprint.

Cite this