Parallel-machine Scheduling with Precedence Constraints and Controllable Job-processing Times

摘要

A parallel-machine scheduling problem with tree-formed precedence constraints is studied, where job-processing times can be compressed by allocating extra resource to the jobs. A tabu-search algorithm is developed in this paper, which searches for the near optimal solutions based on the structural characteristics of the problem. Experiment shows the algorithm is capable for providing satisfactory schedules for media and large-sized problems within acceptable computing time.