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

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

Asaf Levin, Dorit S. Hochbaum

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 schedulingmultiple shift scheduling problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20)

Related Items (14)

Partial multicovering and the \(d\)-consecutive ones property ⋮ Group control for consent rules with consecutive qualifications ⋮ Solution approaches to large shift scheduling problems ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Minimizing the number of workers in a paced mixed-model assembly line ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ 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 ⋮ Minimizing shifts for personnel task scheduling problems: a three-phase algorithm ⋮ The cyclical scheduling problem ⋮ New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems ⋮ Approximability and parameterized complexity of multicover by \(c\)-intervals ⋮ The maximum clique problem in multiple interval graphs

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

This page was built for publication: Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms