Conditional Scheduling with Varying Deadlines

We examine a conditional scheduling model in which the deadlines of jobs are allowed to vary. We explore variants of the basic model and locate the dividing line between NP-hard and polynomial-time problems. Suppose that an engineer needs to design one of two devices, either A or B. Each device will require nine months of work. The due date of both A and B is in one year, but only one device will need to be completed. However, which device will need to be built will not be known until six months from now. Building both devices is clearly impossible, since the total amount of time required is 18 months. Instead, the engineer’s next six months should be divided between A and B, with the remaining six months devoted exclusively to one or the other, depending on the decision six months from now about which device to complete. In this example, the scheduling strategy is easy enough to determine. In more complicated examples, it may be less clear how to devise a strategy. What if the devices to be made are many, require unequal amounts of time, and have unequal due dates? What if the decisions about which device to make occur at different times? What if some devices require other devices to be already completed? This report presents generalizations and variants of the engineer’s problem, and locates the dividing line between polynomial-time and computationally infeasibl