A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem

DOI10.1016/S0166-218X(96)00106-0MaRDI QIDQ1364482zbMATHOpenAlexFDO

Authors Vadim G. Timkovsky

Publication date 4 September 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

scheduling problempseudopolynomial-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 3970499
• Job shop scheduling with unit time operations under resource constraints and release dates
• A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
• A Polynomial Approximation Scheme for a Constrained Flow-Shop Scheduling Problem
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs

Cites work

• scientific article; zbMATH DE number 3941255 (Why is no real title available?)
• scientific article; zbMATH DE number 3970499 (Why is no real title available?)
• scientific article; zbMATH DE number 3759900 (Why is no real title available?)
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• An efficient algorithm for a job shop problem
• Computational Complexity of Discrete Optimization Problems
• Minimizing maximum lateness in a two-machine unit-time job shop
• On general routing problems
• Total completion time minimization in two-machine job shops with unit-time operations

Cited in

(21)

• A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
• An efficient algorithm for a job shop problem
• Is a unit-job shop not easier than identical parallel machines?
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• A note on ``Scheduling unit-time tasks with integer release times and deadlines
• A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job
• On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
• Scheduling lots of dependent unit-time operations on identical machines to minimize schedule length
• scientific article; zbMATH DE number 4033467 (Why is no real title available?)
• Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
• A polynomial algorithm for lot-size scheduling of two type tasks.
• scientific article; zbMATH DE number 3970499 (Why is no real title available?)
• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
• scientific article; zbMATH DE number 1731178 (Why is no real title available?)
• Job shop scheduling with unit time operations under resource constraints and release dates
• Scheduling two chains of unit jobs on one machine: a polyhedral study
• An efficient algorithm for the job-shop problem with two jobs
• scientific article; zbMATH DE number 4057269 (Why is no real title available?)
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• On scheduling cycle shops: Classification, complexity and approximation
• Polynomial-time approximation schemes for scheduling problems with time lags

This page was built for publication: A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem

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