Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
DOI10.1016/J.DISOPT.2006.02.002zbMATH Open1112.90023OpenAlexW2028181262MaRDI QIDQ865749FDOQ865749
Authors: 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
Recommendations
Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- Title not available (Why is that?)
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- A fast approximation algorithm for the multicovering problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Maximum matching of given weight in complete and complete bipartite graphs
- A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- On the hardness of approximating minimization problems
- Matching is as easy as matrix inversion
- Cyclic Scheduling via Integer Programs with Circular Ones
- COMBINATORIAL APPROACHES FOR HARD PROBLEMS IN MANPOWER SCHEDULING
- Optimal Capacity Scheduling—I
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- Title not available (Why is that?)
- Convex separable optimization is not much harder than linear optimization
- Matchings in colored bipartite networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Multiple Shift Workforce Lower Bounds
- Minimax problems with bitonic matrices
Cited In (22)
- On the computational complexity of (maximum) shift class scheduling
- An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times
- On Graham's bound for cyclic scheduling
- Partial multicovering and the \(d\)-consecutive ones property
- A faster algorithm for finding minimum Tucker submatrices
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- The complexity of multidimensional periodic scheduling
- Minimizing the number of workers in a paced mixed-model assembly line
- A polynomial-time algorithm for finding a minimal conflicting set containing a given row
- Approximability and parameterized complexity of multicover by \(c\)-intervals
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- The cyclical scheduling problem
- The cyclical scheduling problem
- Cyclic Scheduling of Multimodal Concurrently Flowing Processes
- On the parameterized complexity of multiple-interval graph problems
- Title not available (Why is that?)
- Minimizing shifts for personnel task scheduling problems: a three-phase algorithm
- The maximum clique problem in multiple interval graphs
- Group control for consent rules with consecutive qualifications
- New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
- Contact center scheduling with strict resource requirements
- Solution approaches to large shift scheduling problems
This page was built for publication: Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q865749)
