Scheduling tasks on two processors with deadlines and additional resources
type: Item
instance of: scholarly article
title: Scheduling tasks on two processors with deadlines and additional resources
zbMATH Open document ID: 0605.90073
DOI: 10.1016/0377-2217(86)90138-4
author: B. George
published in: European Journal of Operational Research
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3978806
zbMATH Keywords: deadlines
zbMATH Keywords: resource constraints
zbMATH Keywords: finite set of identical processors
zbMATH Keywords: additional resources
zbMATH Keywords: two major open nonpreemptive scheduling
zbMATH Keywords: NP- hardness
Wikidata QID: Q57387928
MaRDI profile type: Publication
full work available at URL: 0377-2217(86)90138-4
OpenAlex ID: W2018082550
cites work: Deadline scheduling of tasks with ready times and resource constraints
cites work: Q4182233
cites work: A linear time algorithm for restricted bin packing and scheduling problems
cites work: Scheduling subject to resource constraints: Classification and complexity
cites work: Q4131987
cites work: Q4166568
cites work: Complexity Results for Multiprocessor Scheduling under Resource Constraints
cites work: Q4198056
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Q3940839
cites work: Q3221735
cites work: Some new results in flow shop scheduling
cites work: The complexity of satisfiability problems
cites work: Q3911382
cites work: A simplified NP-complete satisfiability problem
cites work: Algorithm 520: An Automatic Revised Simplex Method for Constrained Resource Network Scheduling [H]
cites work: Preemptive Scheduling, Linear Programming and Network Flows
description: scientific article; zbMATH DE number 3978806