Scheduling Opposing Forests

SIAM Journal on Algebraic and Discrete MethodsPublished 1 March 1983

M. R. Garey, David S. Johnson, Robert E. Tarjan, Mihalis Yannakakis

Citations81

TL;DR

It is shown that a polynomial time algorithm for a wider class of precedence constraints is unlikely, and it is proved that the problem to be NP-complete for precedence constraints that are the disjoint union of an in-forest and an out-forest (the “opposing forests” of the title).

Abstract

A basic problem of deterministic scheduling theory is that of scheduling n unit-length tasks on m identical processors subject to precedence constraints so as to meet a given overall deadline. T. C. Hu's classic "level algorithm" can be used to solve this problem in linear time if the precedence constraints have the form of an in-forest or an out-forest. We show that a polynomial time algorithm for a wider class of precedence constraints is unlikely, by proving the problem to be NP-complete for precedence constraints that are the disjoint union of an in-forest and an out-forest (the "opposing forests" of our title). However, for any fixed value of m we show that this problem can be solved in polynomial time for such precedence constraints. For the special case of $m = 3$ we provide a linear time algorithm.

Keywords

Computer ScienceEngineering

Journal of Computer and System SciencesNP-complete scheduling problems

1,429 Citations1975Jeffrey D. Ullman

It is shown that the problem of finding an optimal schedule for a set of jobs is NP-complete even in the following two restricted cases, tantamount to showing that the scheduling problems mentioned are intractable.

Operations ResearchParallel Sequencing and Assembly Line Problems

895 Citations1961T. C. Hu

This paper deals with a new sequencing problem in which n jobs with ordering restrictions have to be done by men of equal ability, and how to arrange a schedule that requires the minimum number of men to complete all jobs within a prescribed time T.

Journal of the ACM`` Strong '' NP-Completeness Results

652 Citations1978M. R. Garey, David Johnson

This paper provides a standard framework for stating and proving "strong" NP-completeness results of this sort, survey some of the strong results proved to date, and indicate some unphcauons of these results for both opumlzatlon and approximaUon algontluns.

View PDF

Acta InformaticaOptimal scheduling for two-processor systems

610 Citations1972E. G. Coffman, Ronald Graham

It is proved that the algorithm gives optimal solutions and its application to preemptive scheduling disciplines is discussed.

SIAM Journal on ComputingTwo-Processor Scheduling with Start-Times and Deadlines

234 Citations1977M. R. Garey, David S. Johnson

An O(n^3) algorithm is presented that constructs such a schedule whenever one exists and may be used in a binary search mode to find the shortest such schedule or to find a schedule that minimizes maximum “tardiness”.

SIAM Journal on ComputingScheduling Interval-Ordered Tasks

227 Citations1979Christos H. Papadimitriou, Mihalis Yannakakis

It is shown that unit execution time jobs subject to a precedence constraint whose complement is chordal can be scheduled in linear time on m processors.

SIAM Journal on Applied MathematicsOptimal Sequencing of Two Equivalent Processors

186 Citations1969M. Fujii, Tadao Kasami +1 more

This paper presents an efficient algorithm for a class of sequencing problems in which n tasks with an arbitrary precedence relation have to be processed by two processors of equal ability, and each task requires one unit of time.

Mathematics of Operations ResearchSequencing with Series-Parallel Precedence Constraints

167 Citations1979Clyde Monma, Jeffrey B. Sidney

A natural subclass of problems for which a total preference ordering of the jobs exists for all subsequences of jobs is considered, and an efficient general algorithm is found for these sequencing problems with series-parallel precedence constraints.

Journal of the ACMScheduling Tasks with Nonuniform Deadlines on Two Processors

150 Citations1976M. R. Garey, David S. Johnson

It is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.

View PDF

Mathematics of Operations ResearchScheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness

107 Citations1977Peter Brucker, M. R. Garey +1 more

This work considers an extension of this special case model to include the possibility of individual task deadlines, in which case the goal is to minimize maximum lateness and shows that it makes a considerable difference whether the precedence is of “in-tree” or “out- tree” form.