Online citations, reference lists, and bibliographies.
← Back to Search

Complexity Of Machine Scheduling Problems

P. Brucker, J. Lenstra, A. Kan
Published 1975 · Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Share
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Get Citationsy
We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.
This paper references
10.1002/NAV.3800010110
Optimal two- and three-stage production schedules with setup times included
S. Johnson (1954)
10.1002/NAV.3800030307
An extension of Johnson's results on job IDT scheduling
J. Jackson (1956)
10.1002/NAV.3800030106
Various optimizers for single‐stage production
W. Smith (1956)
10.1287/OPRE.8.6.782
SOLUTION OF THE AKERS-FRIEDMAN SCHEDULING PROBLEM
W. Szwarc (1960)
10.1007/BF01963410
Ein Beitrag zum Reihenfolgeproblem
J. Piehler (1960)
10.1287/OPRE.9.6.841
Parallel Sequencing and Assembly Line Problems
T. Hu (1961)
10.1287/OPRE.11.6.889
A Geometric Model and a Graphical Algorithm for a Sequencing Problem
W. W. Hardgrave (1963)
10.1287/MNSC.11.2.280
On Scheduling Problems with Deferral Costs
E. Lawler (1964)
10.1287/OPRE.12.5.655
Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
P. C. Gilmore (1964)
10.1007/978-0-8176-4842-8_26
Paths, Trees, and Flowers
J. Edmonds (1965)
10.1287/MNSC.15.1.102
An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
J. M. Moore (1968)
10.1287/MNSC.16.1.77
A Functional Equation and its Application to Resource Allocation and Sequencing Problems
E. Lawler (1969)
10.1137/0117070
Optimal Sequencing of Two Equivalent Processors
M. Fujii (1969)
10.1145/800157.805047
The complexity of theorem-proving procedures
S. Cook (1971)
10.1287/opre.20.3.689
Solution of the Flowshop-Scheduling Problem with No Intermediate Queues
D. Wismer (1972)
10.1137/0123021
Single-Machine Job Sequencing with Treelike Precedence Ordering and Linear Delay Penalties
W. A. Horn (1972)
10.1057/JORS.1972.52
On the Flow-Shop Sequencing Problem with No Wait in Process †
S. S. Reddi (1972)
10.1287/opre.21.3.846
Technical Note - Minimizing Average Flow Time with Parallel Machines
W. A. Horn (1973)
10.1287/MNSC.19.5.544
Optimal Sequencing of a Single Machine Subject to Precedence Constraints
E. Lawler (1973)
10.1002/NAV.3800200106
On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/Fmax) problem
P. Bratley (1973)
10.1137/0125042
Optimal linear-ordering.
D. Adolphson (1973)
Are polynomial algorithms really good
J. M. Anthonisse (1974)
10.1057/JORS.1975.151
Some Simple Applications of the Travelling Salesman Problem
J. K. Lenstra (1974)
10.1145/1811129.1811130
A terminological proposal
D. Knuth (1974)
10.1145/361011.361064
Scheduling independent tasks to reduce mean finishing time
J. Bruno (1974)
10.1111/J.1467-9574.1976.TB00264.X
Minimizing maximum lateness on one machine : Computational experience and some applications
B. Lageweg (1975)
10.1287/opre.23.2.283
Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
J. B. Sidney (1975)
10.1002/NET.1975.5.1.45
On the Computational Complexity of Combinatorial Problems
R. Karp (1975)
10.1137/0204035
Complexity Results for Multiprocessor Scheduling under Resource Constraints
M. Garey (1975)
10.1016/S0022-0000(75)80008-0
NP-Complete Scheduling Problems
J. Ullman (1975)
10.1016/0304-3975(76)90059-1
Some Simplified NP-Complete Graph Problems
M. Garey (1976)
Approximation algorithms for combinatorial problems: an annotated bibliography
M. Garey (1976)
10.1287/moor.1.2.117
The Complexity of Flowshop and Jobshop Scheduling
M. Garey (1976)
10.1145/321958.321967
Scheduling Tasks with Nonuniform Deadlines on Two Processors
M. Garey (1976)
10.1016/S0167-5060(08)70742-8
A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness
E. Lawler (1977)
10.1137/0206029
Two-Processor Scheduling with Start-Times and Deadlines
M. Garey (1977)
10.1287/MNSC.24.4.441
Job-Shop Scheduling by Implicit Enumeration
B. Lageweg (1977)



This paper is referenced by
10.1007/S10479-021-04043-X
Generating bicriteria schedules for correlated parallel machines involving tardy jobs and weighted completion time
Yang-Kuei Lin (2021)
10.1007/s10732-019-09425-w
Scheduling hybrid flow shops with time windows
F. Yang (2021)
10.1016/J.COR.2021.105308
Multi-period bin packing model and effective constructive heuristics for corridor-based logistics capacity planning
T. Crainic (2021)
10.1016/j.apm.2020.07.048
A metric approach for scheduling problems with minimizing the maximum penalty
A. Lazarev (2021)
10.1007/S10479-018-2928-6
Online production planning to maximize the number of on-time orders
N. Hall (2021)
10.1007/978-3-030-78230-6_9
Combining Constraint Programming and Temporal Decomposition Approaches - Scheduling of an Industrial Formulation Plant
Christian Klanke (2021)
10.1109/CCGrid51090.2021.00030
Data-driven scheduling in serverless computing to reduce response time
Bartlomiej Przybylski (2021)
10.1016/j.cor.2021.105238
A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times
H. Badri (2021)
10.1145/3406325.3451075
A (2 + ε)-approximation algorithm for preemptive weighted flow time on a single machine
Lars Rohwedder (2021)
Single and Parallel Machine Scheduling with Variable Release Dates
Felix Mohr (2021)
10.1088/1742-6596/1864/1/012057
Instances generation for a single machine scheduling problem
A. Lazarev (2021)
10.1007/978-3-030-77970-2_31
The Problem of Tasks Scheduling with Due Dates in a Flexible Multi-machine Production Cell
W. Bozejko (2021)
10.1007/978-3-030-77967-2_34
The Power of a Collective: Team of Agents Solving Instances of the Flow Shop and Job Shop Problems
P. Jędrzejowicz (2021)
10.1016/j.ejor.2020.12.045
Single-machine scheduling with an external resource
Dirk Briskorn (2021)
10.1088/1742-6596/1791/1/012076
On Hybrid Evolutionary Algorithms for Scheduling Problem with Tardiness Criterion
Y. V. Kovalenko (2021)
10.1088/1742-6596/1902/1/012083
Solving the problem of service requests based on the algorithm for minimizing the maximum time offset
L. Rossikhina (2021)
10.1016/j.cor.2021.105401
Genetic programming-based hyper-heuristic approach for solving dynamic job shop scheduling problem with extended technical precedence constraints
Huali Fan (2021)
10.1016/J.CIE.2021.107309
Minimization of maximum lateness in a flowshop learning effect scheduling with release dates
D. Bai (2021)
10.1016/j.cor.2021.105414
Generalized order acceptance and scheduling problem with batch delivery: Models and metaheuristics
Istenç Tarhan (2021)
10.1016/j.ejor.2020.10.052
Bi-objective parallel machine scheduling with additional resources during setups
Juan C. Yepes-Borrero (2021)
10.3390/a14050145
No-Wait Job Shop Scheduling Using a Population-Based Iterated Greedy Algorithm
Mingming Xu (2021)
10.1007/s10489-020-02027-1
A multi objective volleyball premier league algorithm for green scheduling identical parallel machines with splitting jobs
K. Salimifard (2021)
10.1007/s10951-021-00687-6
Makespan Minimization with OR-Precedence Constraints
Felix Happach (2021)
USE OF MACHINE LEARNING TECHNIQUES TO SOLVE SCHEDULING PROBLEMS
Bc. Evgeniya Brichkova (2021)
New Competitive Semi-online Scheduling Algorithms for Small Number of Identical Machines
Debasis Dwibedy (2021)
Worst-Case Analysis of an Approximation Algorithm for Single Machine Scheduling Problem
N. Grigoreva (2021)
10.1145/3468264.3473936
Intelligent container reallocation at Microsoft 365
Bo Qiao (2021)
10.1007/s10845-020-01597-8
Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem
Bentao Su (2021)
10.1007/S12065-020-00556-9
Lunar cycle inspired PSO for single machine total weighted tardiness scheduling problem
Shruti Gupta (2021)
10.1007/S40305-020-00338-1
Disruption Recovery at Airports: Ground Holding, Curfew Restrictions and an Approximation Algorithm
P. Manyem (2021)
10.1109/TITS.2020.3002271
Effective Charging Planning Based on Deep Reinforcement Learning for Electric Vehicles
Cong Zhang (2021)
10.3390/APP11052069
Parallel Algorithm with Blocks for a Single-Machine Total Weighted Tardiness Scheduling Problem
Mariusz Uchronski (2021)
See more
Semantic Scholar Logo Some data provided by SemanticScholar