Cyclic schedules for r irregularity occurring events

DOI10.1016/0377-0427(90)90026-VMaRDI QIDQ2639766zbMATH OpenFDO

Authors Peter Brucker, Rainer E. Burkard, Johann L. Hurink

Publication date 1990

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-0427(90)90026-V

zbMATH Keywords

cyclic schedulingNP-hardpolynomial algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The problem to be considered is one of scheduling r cyclic task events that are activated according to some fixed periodic pattern. Three criteria are analyzed: minimizing the maximum distance between two events, maximizing the minimum distance and minimizing the sum of squared distances. For all three problems polynomial algorithms are given, if r is fixed. For general r, however, the problems are NP-hard.

Recommendations

• Scheduling periodic events
• Scheduling two irregular polygons
• Optimal schedules for periodically recurring events
• scientific article; zbMATH DE number 4147849
• A study of the cyclic scheduling problem on parallel processors

Cites work

• A characterization of the minimum cycle mean in a digraph
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3694971 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• Optimal schedules for periodically recurring events
• Scheduling two irregular polygons

Cited in

(12)

• Disjoint congruence classes and a timetabling application
• Scheduling two irregular polygons
• Computing the minimum Hausdorff distance between two point sets on a line under translation
• On the stabilization of resource usage for cyclical sequencing problems
• Discrete optimization in public rail transport
• Optimal schedules for periodically recurring events
• Scheduling with safety distances
• A genetic algorithm approach to periodic railway synchronization
• Polygon scheduling
• Periodic network optimization with different arc frequencies
• Pattern scheduling
• Scheduling periodic events

This page was built for publication: Cyclic schedules for r irregularity occurring events

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639766)