Scheduling two irregular polygons

DOI10.1016/0166-218X(88)90056-XMaRDI QIDQ1104847zbMATH OpenOpenAlexFDO

Authors Peter Brucker, Wolfgang Meyer

Publication date 1988

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(88)90056-x

zbMATH Keywords

cyclic arrivals of trainsminimizing maximum distancescheduling two irregularly occuring events

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Review text

The paper deals with the problem of scheduling two irregularly occuring events in such a way that the maximum (minimum) distance between two different events is minimized (maximized). Such a problem is important in constructing schedules for cyclic arrivals of trains, buses etc. It can be modelled by constructing two irregular polygons on some line and moving them in order to minimize (maximize) a distance between adjacent vertices. In the paper, two O(m\(\cdot n\cdot \log m)\) algorithms for the two above variants, are given (m, n being numbers of vertices of the two polygons).

Recommendations

• scientific article; zbMATH DE number 858990
• A railway scheduling problem
• Cyclic schedules for r irregularity occurring events
• Scheduling periodic events
• Polygon scheduling

Cites work

• Approximation of a set of points by points of a grid
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Optimal schedules for periodically recurring events

Cited in

(11)

• Computing the minimum Hausdorff distance between two point sets on a line under translation
• Optimal schedules for periodically recurring events
• Scheduling with safety distances
• Polygon scheduling
• Cyclic schedules for r irregularity occurring events
• Pattern scheduling
• A Meeting Scheduling Problem Respecting Time and Space
• A railway scheduling problem
• Location of polygon vertices on circles and its application in transport studies
• scientific article; zbMATH DE number 858990 (Why is no real title available?)
• Scheduling periodic events

This page was built for publication: Scheduling two irregular polygons

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