Exercises in Graph Colouring For Resource Scheduling Problems Algologic Research and Solutions

algo logic
Algologic Research and Solutions

Technical Report
Exercises in graph colouring for resource scheduling

problems
May 2011
Algologic Technical Report
May 2011

problems
Contents
1 Problem statement 2
1.1 Problem #1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Problem #2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Solutions 3
2.1 Solution Problem #1 . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Solution – Problem #2 . . . . . . . . . . . . . . . . . . . . . . 4
1
problems
S. Parthasarathy
drpartha@gmail.com
Secunderabad, India
http://algolog.tripod.com/index.htm
Our Ref.: color-exer.tex

Ver.: 20110521a
Abstract
This article presents two problems in resource scheduling. It shows
how to approach these problems using graph colouring.
1 Problem statement
The following two problems are borrowed from :
http://oneweb.utc.edu/ Christopher-Mawata/petersen/lesson8.htm.
We reproduce the problems (and solutions) with permission from the orig-
nal author Prof. Christopher Mawata (svf234@mocs.utc.edu), Department
of Mathematics, University of Tennessee at Chattanooga, USA.
Details regarding the approach used are given in [1]
1.1 Problem #1
Problem 1 Suppose you want to schedule final exams and, being very con-
siderate, you want to avoid having a student do more than one exam
a day. We shall call the courses 1,2,3,4,5,6,7. In the table below a
star in entry ij means that course i and j have at least one student
in common so you can’t have them on the same day. What is the
least number of days you need to schedule all the exams?
Show how you would schedule the exams.
2
1 2 3 4 5 6 7
1 * * * * *
2 * * *
3 * * *
4 * * * *
5 * *
6 * * * *
7 * * *
The above matrix (table) is the conflict matrix [1] of the problem. A *
in position i j (row, column) indicates that there is atleast one student
who should appear in exams for subject i and subject j. Hence exams
for i and j should not be held on the same day.
1.2 Problem #2
Problem 2 Suppose you run a day care for an office building and there
are seven children A,B,C,D,E,F,G. You need to assign a locker where
each child’s parent can put the child’s food. The children come and
leave so they are not all there at the same time. You have 1 hour time
slots starting 7:00 a.m. to 12:00 noon. A star in the table means a
child is present at that time. What is the minimum number of lockers
necessary? Show how you would assign the lockers.
The contention matrix [1] of the problem is given below.
A B C D E F G
07:00 * * *
08:00 * * *
09:00 * * * *
10:00 * * * *
11:00 * * *
12:00 * *
2 Solutions
We will exploit the principle of graph colouring [1], for solving the above
problems. Our starting point will be the conflict matrices [1] given above, of
the two problems. From the conflict matrix, we prepare a conflict graph. An
3
arc between vertex i and j indicates a conflict between i and j, and corresponds
to a * at the i j position in the conflict matrix.
2.1 Solution Problem #1

The chromatic number is 4 and a possible schedule is
Day Exam 1 1, 5 2 2, 4 3 3, 6 4 7
Note: That this is not the only four colouring possible – can you find other
solutions?
2.2 Solution – Problem #2

A B C D E F G
07:00 * * *
08:00 * * *
09:00 * * * *
10:00 * * * *
11:00 * * *
12:00 * *
This is the contention matrix of the problem. It indicates the time slots at
which a given child comes to the day care centre. A star in the table means a
child is present at that time. He/she will need a locker, all to himself/herself.
We create a conflict matrix from the above contention matrix. A * in posi-

tion ij implies that there is at least one situation when child i is in conflict
with child j (for a locker), at least once ( e.g. A is in conflict with C at the
8:00 slot, 9:00 slot and 10:00 slot):
A B C D E F G
A * * * * *
B * *
C * * *
D * *
E * * *
F * * *
G * * *
It is now an easy step to transform the above conflict matrix into a conflict
graph. We assign a ”color“ to each vertex. The two terminal vertices of each
edge are in conflict (at least once), so they need two different colours.
4
We end up with the following vertex coloured graph ::
The number of colours used (aka chromatic number of the graph) indicates
the number of lockers needed to avoid conflict.
Thus the solution is that : we need four lockers:
1. Child C and child E (vertices 3 and 5) share a locker (blue colour) since
they are never at school at the same time,
2. another locker (red) is shared by the children B, D, G.
3. A gets one (green)
4. F gets one (yellow)
References
[1] S. Parthasarathy, Graph colouring...., Technical Report, Algologic, May
2010

Exercises in Graph Colouring For Resource Scheduling Problems Algologic Research and Solutions

Uploaded by

Copyright:

Available Formats

Exercises in Graph Colouring For Resource Scheduling Problems Algologic Research and Solutions

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Exercises in Graph Colouring For Resource Scheduling Problems Algologic Research and Solutions

Uploaded by

Copyright:

Available Formats

algo logic

Algologic Research and Solutions

Exercises in graph colouring for resource scheduling

Exercises in graph colouring for resource scheduling

Our Ref.: color-exer.tex

The contention matrix [1] of the problem is given below.

2.1 Solution Problem #1

2.2 Solution – Problem #2

We create a conflict matrix from the above contention matrix. A * in posi-

Thus the solution is that : we need four lockers:

2. another locker (red) is shared by the children B, D, G.

3. A gets one (green)

4. F gets one (yellow)

You might also like