Routing equal-size messages on a slotted ring

DOI10.1007/s10951-011-0259-4zbMath1280.68073OpenAlexW2122049872MaRDI QIDQ2434298

Dariusz Dereniowski, Wiesław X. Kubiak

Publication date: 5 February 2014

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-011-0259-4

zbMATH Keywords

routingjust-in-time schedulingoptical networkslotted ringmulti-slot scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
• Proportional optimization and fairness
• A linear-time algorithm for a special case of disjoint set union
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Precoloring extension. I: Interval graphs
• Balancing loads on Sonet rings with integer demand splitting
• On the ring loading problem with demand splitting.
• Scheduling preemptable tasks on parallel processors with limited availability
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• On two coloring problems in mixed graphs
• Just-in-time scheduling. Models and algorithms for computer and manufacturing systems
• Scheduling Problems and Mixed Graph Colorings
• The Complexity of Coloring Circular Arcs and Chords
• Graph Classes: A Survey
• The Ring Loading Problem
• Linear time algorithms for the ring loading problem with demand splitting
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem