Scheduling tasks on two processors with deadlines and additional resources (Q1084012)

The deterministic scheduling model in this paper involves a finite set of identical processors, a finite set of additional resources and a finite set of tasks to be executed, each requiring one processor and specified amounts of additional resources during a known amount of time. Each task is to be completed before its deadline. We establish the complexity status of the two major open nonpreemptive scheduling problems of this type. That is, we prove NP-hardness of two scheduling problems with two processors and unit processing times of all the tasks; the first one has one resource type available in a specified amount, the second one has an arbitrary number of resources, each available in amount of one unit. These results are complementary to a previous paper by the first author [Inform. Processing Letters 8, 60-63 (1979; Zbl 0401.90048)], where a polynomial-time algorithm was presented for an arbitrary number of processors, one resource type and zero-one resource requirements of the tasks. In addition, in the present paper new restricted versions of ONE- IN-THREE 3 SAT are also proved to be NP-hard. These heavily restricted versions promise to be useful in other NP-hardness proofs.