|Title||Job Shop Scheduling Problems with Controllable Processing Times|
|Authors||Klaus Jansen, Institute for Computer
Science and Applied Mathematics Christian-Albrechts-University of Kiel
Monaldo Mastrolilli, IDSIA - Istituto Dalle Molle di Studi sull' Intelligenza Artificiale
Roberto Solis-Oba, Department of Computer Science, The University of Western Ontario, Canada
|Main Fields||1. analysis of algorithms
7. design of algorithms
|Other Main Fields||approximation algorithm|
|Abstract + Keywords||Most classical scheduling models assume
that the jobs have fixed processing times.
However, in real-life applications the processing time of a job often depends on
the amount of resources such as facilities,
manpower, funds, etc. allocated to it, and so its processing time can be
reduced when additional resources are assigned to the job. A scheduling
problem in which the processing times of the jobs can be reduced at some
expense is called a scheduling problem with controllable processing
times. In this paper we study the classic job shop scheduling problem under
the assumption that the jobs have controllable processing times. We consider
two models of controllable processing times: continuous and discrete. For
both models we present polynomial time approximation schemes when the number
of machines and the number of operations per job are fixed.
Keywords: scheduling, job shop scheduling problem, approximation algorithm, polynomial time approximation scheme.