A decomposition scheme for single stage scheduling problems

DOI10.1007/S10951-010-0165-1MaRDI QIDQ983632zbMATH OpenOpenAlexFDO

Authors 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) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Decomposition in single-machine scheduling
• Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm
• A new decomposition approach for the single machine total tardiness scheduling problem
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Dominance and Decomposition Heuristics for Single Machine Scheduling

Cites work

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

Cited in

(7)

• A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines
• 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
• Solution of a large-scale two-stage decision and scheduling problem using decomposition
• Décomposition temporelle et caractérisation de solutions admissibles pour le problème d'ordonnancement à une machine
• Dual decomposition of a single-machine scheduling problem
• scientific article; zbMATH DE number 433057 (Why is no real title available?)

This page was built for publication: A decomposition scheme for single stage scheduling problems

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