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

DOI10.1016/S0166-218X(96)00106-0zbMath0879.68011OpenAlexW2040466446MaRDI QIDQ1364482

Timkovsky, Vadim G.

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) Searching and sorting (68P10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Polynomial-time approximation schemes for scheduling problems with time lags ⋮ 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 ⋮ 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. ⋮ On scheduling cycle shops: Classification, complexity and approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing maximum lateness in a two-machine unit-time job shop
• Total completion time minimization in two-machine job shops with unit-time operations
• An efficient algorithm for a job shop problem
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• On general routing problems
• Computational Complexity of Discrete Optimization Problems