Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms

DOI10.1016/j.disopt.2006.02.002zbMath1112.90023MaRDI QIDQ865749

Dorit S. Hochbaum, Asaf Levin

Publication date: 20 February 2007

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.02.002

zbMATH Keywords

cyclical scheduling; multiple shift scheduling problem

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

68W20: Randomized algorithms

Related Items

Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Dynamic programming based algorithms for set multicover and multiset multicover problems, On the parameterized complexity of multiple-interval graph problems, New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems, A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row, Solution approaches to large shift scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast approximation algorithm for the multicovering problem
• Matching is as easy as matrix inversion
• Matchings in colored bipartite networks
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Multiple Shift Workforce Lower Bounds
• Optimal Capacity Scheduling—I
• A Greedy Heuristic for the Set-Covering Problem
• Cyclic Scheduling via Integer Programs with Circular Ones
• A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Maximum matching of given weight in complete and complete bipartite graphs
• On the hardness of approximating minimization problems
• Minimax problems with bitonic matrices
• COMBINATORIAL APPROACHES FOR HARD PROBLEMS IN MANPOWER SCHEDULING
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Convex separable optimization is not much harder than linear optimization