On the geometry, preemptions and complexity of multiprocessor and shop scheduling

DOI10.1007/s10479-007-0266-1zbMath1151.90433OpenAlexW1979626969MaRDI QIDQ940887

Nodari Vakhania, Evgeny V. Shchepin

Publication date: 3 September 2008

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-007-0266-1

zbMATH Keywords

algorithmmultiprocessor schedulingtime complexitypreemptionshop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (9)

Parametric analysis of the quality of single preemption schedules on three uniform parallel machines ⋮ Schedules with a single preemption on uniform parallel machines ⋮ On the complexity of scheduling unrelated parallel machines with limited preemptions ⋮ On the complexity of constructing multiprocessor little-preemptive schedules ⋮ Research on permutation flow shop scheduling problems with general position-dependent learning effects ⋮ Some results of the worst-case analysis for flow shop scheduling with a learning effect ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ A note on the proof of the complexity of the little-preemptive open-shop problem ⋮ Preemptive and non-preemptive scheduling on two unrelated parallel machines

Cites Work

• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• The complexity of cyclic shop scheduling problems
• Little-preemptive scheduling on unrelated processors
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Scheduling with Deadlines and Loss Functions
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• Open Shop Scheduling to Minimize Finish Time
• Preemptive Scheduling of Uniform Processor Systems
• Flowshop and Jobshop Schedules: Complexity and Approximation
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming

This page was built for publication: On the geometry, preemptions and complexity of multiprocessor and shop scheduling