Complexity Results for Single Machine Distance Constrained Scheduling Problems

Abstract

Scheduling problems that involve timing constraints between tasks occur often in machine shop scheduling (e.g., job shop scheduling problems) and code scheduling during software compilation for pipelined processors (e.g., multiprocessor sequencing and scheduling problems).