Scheduling tasks on two processors with deadlines and additional resources
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.
- A linear time algorithm for restricted bin packing and scheduling problems
- A simplified NP-complete satisfiability problem
- Algorithm 520: An Automatic Revised Simplex Method for Constrained Resource Network Scheduling [H]
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Deadline scheduling of tasks with ready times and resource constraints
- scientific article; zbMATH DE number 3889254 (Why is no real title available?)
- scientific article; zbMATH DE number 3722085 (Why is no real title available?)
- scientific article; zbMATH DE number 3757695 (Why is no real title available?)
- scientific article; zbMATH DE number 3561065 (Why is no real title available?)
- scientific article; zbMATH DE number 3599820 (Why is no real title available?)
- scientific article; zbMATH DE number 3619600 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Preemptive Scheduling, Linear Programming and Network Flows
- Scheduling subject to resource constraints: Classification and complexity
- Some new results in flow shop scheduling
- The complexity of satisfiability problems
- Minimizing mean flow time with parallel processors and resource constraints
- On the complexity of a restricted list-coloring problem
- Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints.
- Restricted assignment scheduling with resource constraints
- Algorithms for minimizing maximum lateness with unit length tasks and resource constraints
- Production, maintenance and resource scheduling: a review
- Parallel machine scheduling with additional resources: notation, classification, models and solution methods
- Scheduling: agreement graph vs resource constraints
- Extra processors versus future information in optimal deadline scheduling
This page was built for publication: Scheduling tasks on two processors with deadlines and additional resources
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1084012)
