Graph Colouring, Class Scheduling and Application in Modern Computer Science

Abstract

Course timetabling and exam timetabling are two most common academic scheduling problems in any of the educational institution. A desirable schedule combines resources in a way which satisfies essential and preferential constrains. In this paper, we focus on college course timetabling including hard and soft constraints. Our Objective is to inculcate graph colouring approach to obtain a conflict free course graph.

Introduction

I. INTRODUCTION

In 1736 Graph theory which was pointed out by Euler with Konigsberg bridge problem led to Eulerian graph concept  later Gustav Kirchoff  developed the concept of a tree which had a eminent application in electrical networks. A.I. Mohiue came up with the idea of complete graph and bipartite graph in the year 1840. In 1852

Thomas Gutherie paned way to the four –colour problem. the graph colouring deals with planar graph with graph colouring approach which was later solved by kennel appel and Wolfgarg laken Heawood extended it to five –colour theorem in the year 1890.George David Birkhoff studied colouring problems  in algebraic graph theory in the year 1912. The Graph colouring has a vast application which include map colouring scheduling problems, network design, Sudoku, Bipartite graph detection etc. Varied complex problem which involves optimization in particulars, Conflict resolution optimal partitioning of mutually exclusive events can be accomplished by mearus of graph coloring

II. LITERATURE REVIEW

The course scheduling problem was applied to graph colouring in the year 1967, Welsh and Powell (10) in 1967 illustrated the relationship between timetabling and graph colouring .woods graph algorithm (2) was developed in the year 1969. Dulton and Bingham in 1981 introduced heuristic graph colouring algorithm carted (3) in 1986 survey examination timetabling survey. The Mehtas work on conflict –free graph had a significant contribution to complex timetabling applications in 1991 scheron and McGeoch (4) tested various approach for graph colouring with simulated annealing technique.

Kiare and Yelena (5) find approximate solution for a university course timetabling problem using heuristic algorithm.

Burke elliman and Weare (6) introduced graph colouring approach for university timetable system. In1995 Bresina introduced graph colouring method aiming at optimizing solutions. In 2008 koala graph colouring library was developed base on C++. Automata – based approximation algorithms were proposed for solving the minimum helix colouring problem in 2009. A Akbulut  and yilmaaz in 2013 (7) proposed scheduling system based on RFID technology.

III. SCHEDULING PROBLEM

The conceptual idea of scheduling problem is defined by allocating resources that are related among a number of time-slots which satisfied various types of essential and preferential constraints aiming at creating an optimized and conflict free schedule. 

A. Timetable Scheduling

1. The Course Timetable Scheduling: Courses which share common resource will be scheduled in conflict –free –time slots.
2. Timetable Scheduling: Exam sharing common recourses is to be scheduled in conflict free time slots
3. Aircraft Scheduling: Aircraft needs to be assigned to flights 
4. Job shop Scheduling: Is a scheduling for the set of jobs along with their processing time and set of machines a schedule mapping machines ad jobs satisfying the feasibility constraints and optimization objectives.

IV. CONSTRAINTS

In any scheduling problem we have to consider the constraints related to obtain an optimal solution. The many a number of contraction on creating a schedule we accept and reject the output based on our satisfaction .Constraints can be classified as hard and soft constraints.

???????A. Hard Constraints

The essential constrains which cannot be rejected and must be satisfied to have a schedule is called hard constraints any schedule which do not satisfy these hard constraints are rejected.

Few examples are

1. Number of courses cannot exceed the given limit
2. No two or more covers can allotted in the same students.
3. No teacher can handle two courses at same time

???????B. Soft Constraints

The preferential conditions which are optional for scheduling. It is highly complicated to incorporate all the soft constraint in the schedule we accept the schedule even at the occurrence of not satisfying few soft constraints.

???????C. Temporal Constraints &  Spatial Constraints

Constraints can also be classified based on its relation between time and space. The constraints that are related to time are called time related constraints.

1. A theory class and practical class cannot be scheduled at same time.
2. The space related constraints are called spatial constraints.

Example:  No two subject Classes can be allotted in a same room.

Both temporal and spatial constraints are mainly hard type constraints which enhances the effectiveness of a schedule.

V. IDENTIFYING THE SCHEDULING PROBLEM

The objective of scheduling problem is to find the most efficient way to schedule a set of jobs on machines. The three main goals are

???????A. Optimization Issue 

Optimization is meant to maximize profit and minimize cost , for examples scheduling machine time for easiest completion time.

???????B. Equity

Equity is making things fair for all participants for instance scheduling football game by making an exact no of home and away game

.???????C. Conflict Resolution

Conflict resolution focuses on presenting conflicts such as scheduling college final examination for the end team.

VI. METHOD TO SOLVE SCHEDULING PROBLEMS

In Graph colouring provides solutions for many scheduling problems for instance a set of jobs need to be appointed for specific time slots there are many sorts of scheduling it but most of the times, the jobs can conflict i.e as they share same resources they cannot be allocated to same resources they cannot be allocated to same time slots. In graph colouring the designated colours in the graph restrains vertices of the graph is coloured in a manner such that no two adjacent vertices have same colour below is the explanation of graph colouring algorithm

The following the steps to be followed while colouring the vertices

1. Check all the adjacent vertices if they are coloured we add it to a list of used colours.
2. Choose the colour which is not in the list of used colours and assign for the vertex.
3. Go to the next uncoloured vertex with empty list.

We check the entire vertex and select the select the colour which is not the same as its vertices.

 It is important that we start with a right vertex in order to use minimum number of colours.

Welsh-Powell algorithm which ensures the min number of colours in a graph is stated above.

a. Select the first vertex named having most incoming edges and colour it

b. Look at the other vertices colour it if

• If they are not neighbours.
• They are uncoloured.
• The vertex to which it is adjacent is not coloured with the same colour.
• Repeat until colouring all the vertices.

VII. SENSITIVITY ANALYSIS

Nirmala College for Women provides Nine Inter-disciplinary skills for their students to pursue in their final year of the graduation. The students may select up to 2 courses simultaneously. The classes will be held in the college premises. The challenge here is to schedule the classes as per the availability of the halls and including the pairs of courses that have one or more students in common.

The courses that are provided are

TABLE I
List Of Available Courses

The table shows with an x which pairs of courses have one or more students in common only two air-conditioned lecture hall are available for use at any one time

Let us solve the above problem using graph colouring concept. The table with x marks shows pairs of courses having one or more students in common.

1. Hard Constraints

a. Only two halls are allotted for the classes in general

b. At any one time slot, it is permissible to avail 3 halls.

2. Soft Constraints

a. Both the halls should be occupied

History –H            Economics – E     English Literature – EL

Math –M               Chemistry – C       Botany - B

Zoology- Z            Geography – G     B.Com – B.C

We have a constraint that only 2 halls are available. But during time slot (a) , 3 hall are required therefore we simply more BC to Time Slot d .

Now, the altered slots is as above

• Time slot a – H, EL
• Time Slot b – C, Z, M
• Time Slot c – B, G
• Time Slot d - E, BC

Therefore four slots are allotted for the classes as per the above preference.

The complexity of a scheduling problem is as proportional to the number of constraints involved. A better schedule is one which satisfies hard constraints and maximizes the satisfaction of soft constraints. 

VIII. APPLICATION OF GRAPH COLOURING IN MODERN COMPUTER SCIENCE

Graph colouring is used in various fields of research in computer science such as Data mining, Guarding art gallery, Physical layout segmentation, Map colouring and GSM mobile phone networks, Pre-colouring extension, List colouring, Minimum sum colouring, Round Robin Sport Scheduling,  Aircraft scheduling,  Bio-processor task,  Fequency assignment. 

Conclusion

In summary, graph theory is an important branch of mathematics. For planning difficulties, we examined goals and solutions to planning problems. Certain steps must be followed for best results, one example being the graph coloring algorithm. Overall, fairness, conflict resolution, and optimization are the main goals of scheduling problems.

References

[1] Welsh, D.J.A., and Powell, M.B., 1967, “An Upper Bound for the Chromatic Number of a Graph and it\'s Application to Timetabling Problems,” The Computer Journal. 10(1), pp. 85-86. [2] Wood, D. C., 1968, “A System for Computing University Examination Timetables,” The Computer Journal, 11, pp.41-47. [3] Carter, M. W., Laporte, G., and Lee, S. Y., 1996, “Examination timetabling: Algorithmic strategies and applications,” Journal of the Operational Research Society 47(3), pp. 373–383. [4] Johnson, D. S., Aragon, C. R., McGeoch, L. A., and Schevon, C., 1991, “Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning,” Operations Research, 39(3), pp. 378–406. [5] Kiaer, L., and Yellen, J., 1992, “Weighted Graphs and University Timetabling,” Computers and Operations Research, 19(1), pp. 59-67. [6] Burke, E.K., Elliman, D.G., and Weare, R.F., 1994, “A University Timetabling System Based on Graph Colouring and Constraint Manipulation,” Journal of Research on Computing in Education, 27( 1), pp. 1-18. [7] Akbulut, A., and Y?lmaz, G., 2013, “University Exam Scheduling System Using Graph Coloring Algorithm and RFID Technology,” International Journal of Innovation, Management and Technology, 4(1), pp. 66-72.

Copyright

Copyright © 2023 Pharsana Parveen M, Julia Rose Mary. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.