A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs

DOI10.1007/BF01719698zbMath0807.90061MaRDI QIDQ1326784

Peter Brucker

Publication date: 8 June 1994

Published in: OR Spektrum (Search for Journal in Brave)

zbMATH Keywords

makespanNP-hardpolynomially solvable casetwo machinesnonpreemptive job shop scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Shop scheduling problems with multiprocessor tasks on dedicated processors, On the complexity of two machine job-shop scheduling with regular objective functions, An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents, Two-machine job-shop scheduling with one joint job, Complexity of mixed shop scheduling problems: A survey, Complexity of shop-scheduling problems with fixed number of jobs: a survey, Deterministic job-shop scheduling: Past, present and future, The job shop scheduling problem: Conventional and new solution techniques

Cites Work

• The complexity of shop-scheduling problems with two or three jobs