Page 127 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes first constructed, with changes then being made to the schedule via the application of
neighbourhood operators that preserve this validity. Until now, such approaches have
tended to focus on a specific formulation of round-robin scheduling problem, known as
the Travelling Tournament Problem, originally proposed by Easton.
In this work we have chosen to look at the problem of round-robin scheduling in more
general terms. Specifically, we choose to view it as a type of graph colouring problem.
Graph colouring is a classical combinatorial optimisation problem for which much research
has been conducted, both from the perspective of solving graph colouring problems [2, 6,
7, 9] and in exploring the spaces of feasible and/or optimally coloured graphs [9,11,13]. By
using such principles, in this work we analyse the ability of a number of well-known
graph colouring algorithms for solving round-robin scheduling problems of different
sizes. We also show how the graph colouring model can be extended in order to cope with
additional hard (i.e. mandatory) constraints that can often be imposed in practical situations.
Finally, we also examine a number of neighbourhood operators, originating from the
graph colouring literature that can then be utilised in order to explore the space of feasible
round-robin schedules.
In the final part of this work we consider a complex real world scheduling problem that
was given to us by the Welsh Rugby Union, based at the Millennium Stadium in Cardiff,
Wales. This problem involves producing a double round-robin tournament using 2(n – 1)
rounds and features a number of additional hard constraints to do with stadium sharing,
stadium availability, and pre-assignment issues. In addition, soft constraints involving
the spread of related matches throughout the tournament are also imposed. We propose
two separate algorithms for tackling this problem, both that make use of our proposed
algorithmic operators, and we demonstrate their ability to produce solutions that are
superior to those currently used by the league, in short periods of time.
Questions:

1. Describe the main problem of rugby scheduling.
2. How does the Welsh Rugby Union resolve the existing problem?

Source: http://www.mistaconference.org/2009/abstracts/718-719-131-A.pdf

12.4 Summary

 Most real-time scheduling algorithms of practical interest assign fixed priority to individual
jobs.

 In a dynamic system, job ready for execution are placed in one common priority queue
and dispatched to processors for execution as the processors become available.
 A priority driven scheduler is an on-line scheduler.

 There is no pre-computation of schedules of tasks.
 The rate monotonic algorithm assigns priorities to tasks based on their periods.
 A scheduling algorithm can feasibly schedule any set of periodic tasks on a processor if the
total utilization of the tasks is equal to or less than the schedulable utilization of that
algorithm.

122 LOVELY PROFESSIONAL UNIVERSITY