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

DOI10.1007/BF01719698MaRDI QIDQ1326784zbMATH OpenFDO

Authors Peter Brucker

Publication date 8 June 1994

Published in OR Spektrum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01719698

zbMATH Keywords

makespannonpreemptive job shop schedulingNP-hardpolynomially solvable casetwo machines

Mathematics Subject Classification ID

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

Recommendations

• A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
• A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing
• An efficient algorithm for the job-shop problem with two jobs
• A polynomial algorithm for multiprocessor scheduling with two job lengths.
• A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint
• On polynomial solvability of two multiprocessor scheduling problems
• A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times
• Algorithms for a two‐machine flowshop problem with jobs of two classes
• On the complexity of two machine job-shop scheduling with regular objective functions

Cites work

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

Cited in

(19)

• An efficient algorithm for the job-shop problem with two jobs
• The job shop scheduling problem: Conventional and new solution techniques
• Preemptive job-shop scheduling problems with a fixed number of jobs
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
• On the complexity of two machine job-shop scheduling with regular objective functions
• Deterministic job-shop scheduling: Past, present and future
• Shop scheduling problems with multiprocessor tasks on dedicated processors
• An efficient algorithm for a job shop problem
• Complexity of mixed shop scheduling problems: A survey
• Complexity of shop-scheduling problems with fixed number of jobs: a survey
• Low-complexity algorithms for sequencing jobs with a fixed number of job-classes
• scientific article; zbMATH DE number 4131935 (Why is no real title available?)
• scientific article; zbMATH DE number 3970499 (Why is no real title available?)
• scientific article; zbMATH DE number 894722 (Why is no real title available?)
• The Machine Duplication Problem in a Job Shop with Two Jobs
• Job Shop Scheduling With Two Jobs And Nonregular 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
• A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem

This page was built for publication: A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1326784)