Scheduling with controllable release dates and processing times: Total completion time minimization

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov, Natalia V. Shakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)

Abstract

The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n2) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times.
Original languageEnglish
Pages (from-to)769-781
Number of pages13
JournalEuropean Journal of Operational Research
Volume175
Issue number2
DOIs
Publication statusPublished - 1 Dec 2006

Keywords

  • Controllable processing times
  • Controllable release dates
  • Due-date scheduling
  • Parallel machines
  • Scheduling
  • Single machine
  • Total completion time

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this