In the field of machine scheduling problems with controllable processi
ng times, it is often assumed that the possible processing time of a j
ob can be continuously controlled, i.e. it can be any number in a give
n interval. In this paper, we introduce a discrete model in which job
processing times are discretely controllable, i.e. the possible proces
sing time of a job can only be controlled to be some specified lengths
. Under this discrete model, we consider a class of single machine pro
blems with the objective of minimizing the sum of the total processing
cost and the cost measured by a standard criterion. We investigate mo
st common criteria, e.g. makespan, maximum tardiness, total completion
time, weighted number of tardy jobs, and total earliness-tardiness pe
nalty. The computational complexity of each problem is analyzed, and p
seudo-polynomial dynamic programming algorithms are proposed for hard
problems. (C) 1997 Elsevier Science B.V.