A decomposition scheme for single stage scheduling problems

DOI10.1007/S10951-010-0165-1zbMATH Open1193.90093OpenAlexW2001919335MaRDI QIDQ983632FDOQ983632

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

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

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)

Cites Work

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

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
• Solution of a large-scale two-stage decision and scheduling problem using decomposition
• On the flexibility of a decision theory-based heuristic for single machine scheduling
• 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
• Title not available (Why is that?)

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)