POLYNOMIAL ALGORITHMS FOR RESOURCE-CONSTRAINED AND MULTIPROCESSOR TASK-SCHEDULING PROBLEMS

Resource-constrained scheduling problems with a fixed number of task t ypes are considered in which, in addition, either the processing times are bounded or the number of processors is fixed. For problems with m akespan, (weighted) mean now time, weighted number of tardy tasks, and sum of tardiness as objective functions polynomial time algorithms ar e presented. These algorithms generalize results derived by Blaiewicz ct al. (1989) for makespan problems and solve open problems listed by Hoogeveen et al. (1994). Furthermore, results for shop problems with m ultiprocessor tasks and unit processing times, in which either the num ber of jobs or the number of stages is fixed, are derived.