SINGLE-MACHINE SCHEDULING WITH DISCRETELY CONTROLLABLE PROCESSING TIMES

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.