Is a unit-job shop not easier than identical parallel machines?

DOI10.1016/S0166-218X(98)00032-8zbMath0908.90173MaRDI QIDQ1392555

Vadim G. Timkosvky

Publication date: 28 July 1998

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

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

zbMATH Keywords

NP-hardnessmaximum completion timeidentical parallel machinestotal tardinesstotal completion timemaximum latenesspolynomial-time reductionunit-time operations

Mathematics Subject Classification ID

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

Related Items (8)

Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ Using mixed graph coloring to minimize total completion time in job shop scheduling ⋮ On minimizing the weighted number of late jobs in unit execution time open-shops. ⋮ 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 ⋮ On preemption redundancy in scheduling unit processing time jobs on two parallel machines ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ On scheduling cycle shops: Classification, complexity and approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing mean flow time with release time constraint
• A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
• Some no-wait shops scheduling problems: Complexity aspect
• The complexity of shop-scheduling problems with two or three jobs
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Total completion time minimization in two-machine job shops with unit-time operations
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
• Scheduling chain-structured tasks to minimize makespan and mean flow time
• An efficient algorithm for a job shop problem
• Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
• Scheduling with Deadlines and Loss Functions
• Minimizing Total Tardiness on One Machine is NP-Hard
• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Preemptive Scheduling with Release Times, Deadlines, and Due Times
• `` Strong NP-Completeness Results
• Computational Complexity of Discrete Optimization Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling independent tasks to reduce mean finishing time
• Optimal Preemptive Scheduling on Two-Processor Systems
• Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems

This page was built for publication: Is a unit-job shop not easier than identical parallel machines?