Single machine scheduling with discretely controllable processing times

In the field of machine scheduling problems with controllable processing times, it is often assumed that the possible processing time of a job can be continuously controlled, i.e. it can be any number in a given interval. In this paper, we introduce a discrete model in which job processing times are discretely controllable, i.e. the possible processing time of a job can only be controlled to be some specified lengths. Under this discrete model, we consider a class of single machine problems with the objective of minimizing the sum of the total processing cost and the cost measured by a standard criterion. We investigate most common criteria, e.g. makespan, maximum tardiness, total completion time, weighted number of tardy jobs, and total earliness–tardiness penalty. The computational complexity of each problem is analyzed, and pseudo-polynomial dynamic programming algorithms are proposed for hard problems.