A decomposition scheme for single stage scheduling problems

DOI10.1007/s10951-010-0165-1zbMath1193.90093OpenAlexW2001919335MaRDI QIDQ983632

Stefan Bock, Michael L. Pinedo

Publication date: 24 July 2010

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-010-0165-1

zbMATH Keywords

single stage schedulingspeeding up scheduling algorithmsuniversal decomposition scheme

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines ⋮ On the flexibility of a decision theory-based heuristic for single machine scheduling ⋮ A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
• Scheduling jobs with equal processing times and time windows on identical parallel machines
• A note on scheduling equal-length jobs to maximize throughput
• The complexity of mean flow time scheduling problems with release times
• Rolling horizon procedures for the single machine deterministic total completion time scheduling problem with release dates
• Preemptive scheduling of equal-length jobs to maximize weighted throughput.
• Scheduling equal-length jobs on identical parallel machines
• Balancing assembly lines effectively -- a computational comparison
• Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
• Minimizing Total Tardiness on One Machine is NP-Hard
• Planning and Scheduling in Manufacturing and Services
• Finding Total Unimodularity in Optimization Problems Solved by Linear Programs
• Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm
• Scheduling