Routing equal-size messages on a slotted ring

DOI10.1007/s10951-011-0259-4zbMath1280.68073MaRDI 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

routing; just-in-time scheduling; optical network; slotted ring; multi-slot scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

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