ALCOMFT-TR-01-106

Han Hoogeveen and Gerhard J. Woeginger
Some comments on sequencing with controllable processing times
Utrecht. Work package 3. May 2001.

Abstract: We discuss sequencing problems on a single machine with controllable job processing times. For the maximum job cost criterion, we present several polynomial time results. For the total weighted job completion time criterion, we present an NP-hardness result. Our results settle several open questions in this area.

\medskip\noindent Keywords. Scheduling, sequencing, contollable processing time, single machine, computational complexity, bicriterion optimization.

Postscript file: ALCOMFT-TR-01-106.ps.gz (102 kb).