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

DOI10.1016/J.DISOPT.2006.02.002MaRDI QIDQ865749zbMATHOpenAlexFDO

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

zbMATH Keywords

cyclical schedulingmultiple shift scheduling problem

Mathematics Subject Classification ID

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)

Recommendations

• The cyclical scheduling problem
• The cyclical scheduling problem
• Optimizing over Consecutive 1's and Circular 1's Constraints
• On the complexity of manpower shift scheduling
• scientific article; zbMATH DE number 1555983

Cites work

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

Cited in

(22)

• Solution approaches to large shift scheduling problems
• Dynamic programming based algorithms for set multicover and multiset multicover problems
• An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times
• On Graham's bound for cyclic scheduling
• The cyclical scheduling problem
• The cyclical scheduling problem
• The complexity of multidimensional periodic scheduling
• Cyclic Scheduling of Multimodal Concurrently Flowing Processes
• Approximability and parameterized complexity of multicover by \(c\)-intervals
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Partial multicovering and the \(d\)-consecutive ones property
• Minimizing shifts for personnel task scheduling problems: a three-phase algorithm
• On the computational complexity of (maximum) shift class scheduling
• The maximum clique problem in multiple interval graphs
• Group control for consent rules with consecutive qualifications
• Contact center scheduling with strict resource requirements
• On the parameterized complexity of multiple-interval graph problems
• A faster algorithm for finding minimum Tucker submatrices
• 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
• scientific article; zbMATH DE number 850294 (Why is no real title available?)
• New pseudopolynomial complexity bounds for the bounded and other integer knapsack related 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)