Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops

We study the problem of obtaining feasible preemptive schedules for independent jobs. It is assumed that each job has associated with it a release and due time. No job can begin before its release time. All jobs must be completed by their respective due times. It is shown that determining the existence of feasible preemptive schedules for two processor flow and job shops is NP-hard in the strong sense even when all jobs have the same due time. A linear programming formulation for the open shop problem is obtained. Also, a fast polynomial time algorithm is obtained for a restricted class of open shop problems.