Timetable Scheduling using Bipartite Graph

Abstract

In any educational institution, the two most common academic scheduling problems are course timetabling and exam timetabling. A schedule is desirable which combines resources like teachers, subjects, students, classrooms in a way to avoid conflicts satisfying various essential and preferential constraints. The timetable scheduling problem is known to be NP Complete but the corresponding optimization problem is NP Hard. This problem is solved using bipartite graph. Hence a heuristic approach is preferred to find a nearest optimal solution within reasonable running time.

Introduction

I. INTRODUCTION

In the year 1736,graph theory originated from the Konigsberg bridge problem pointed out by mathematician Euler which later led to the concept of Eulerian graph[4]. In the same decade, Gustav Kirchh off established the concept of a tree, a connected graph without cycles which was used in the calculation of currents in electrical networks or circuit and later to enumerate chemical molecules.In1840.

While constructing schedule of courses at a college or university, it is obvious that  courses taught by the same professor and courses that require same classroom must be scheduled at different time slots.Further more,a particular student or group of students may be required by a curriculum to take two different but related courses(e.g., physics and Mathematics) concurrently during a semester. In such cases too,courses need to be scheduled in away to avoid conflicts.

A. Basic Concepts of  Graph Theory

A graph G is an ordered triplet (V(G), E(G), ?) consisting of a non-empty set V of vertices or nodes, E is the set of edges and ? is the mapping from the set of edges E and the set of vertices V.

In a bipartite graph (or bigraph) (Fig. 1) the set of vertices V can be partitioned into two disjoint sets V1 and V2 such that every edge of the graph connects a vertex in V1 to one inV2, i.e.V1 andV2 are independent sets.

II. SCHEDULING PROBLEM

The general idea of a  scheduling problem is defined by allocation of  related resources among a number of time-slots satisfying various types of essential and preferential  constraints  aiming at   creating  optimized conflict-free schedule.

Some of the typical scheduling problems include-

A. Timetable Scheduling

1. CourseTimetableScheduling-coursessharingcommonresourcestobescheduledin conflict-freetime-slots.
2. ExamTimetableScheduling–examssharingcommonresourcestobescheduledin conflict-freetime-slots.
3. Aircraft Scheduling-aircrafts  need to be assigned to flights.

B. Motivation Towards Timetable Scheduling

Effective timetable is vital to the performance of any educational institute. It impacts their ability to meet changing and evolving subject demands and their combinations in a cost-effective manner satisfying various constraints. In this paper, we have focused our work into CourseTimetable Scheduling.

C. Course Timetable Scheduling

Course Timetabling is the scheduling of a set of related courses in a minimal number of time-slots such that no resource is required simultaneously by more than one event.In a typical educational institute resources,which may be required by courses simultaneously can be students, classrooms and teachers.

III. TEACHER-SUBJECT PROBLEM

A. Problem Definition

For a given ‘T’ number of teachers, ‘N’ number of subjects and available ‘P’ number of periods, a timetable should be prepared. The number of classes for each subject needed        by a particular teacher is given in Table2.This problem is mentioned earlier in some papers[25][26]but only a partial solution was provided in both.

B. Input Dataset

Number of teachers -3

Number of subjects-5

List of subjects are following

N1- Calculus

N2- Classical Mechanics

N3- Phython Programming

N4- Trigonometry

N5- MS office

Teacher-Subject Requirement Matrix

C. List of Constraints

1. Hard Constraints

a. At any one period, each subject can be taught by maximum one teacher.

b. At any one period, each teacher can teach at most one subject.

2. Soft Constraints

a. Teacher taking two classes of same subject to be scheduled in consecutive periods.

b. No more than two consecutive theory classes can be assigned to same teacher for teaching same subject.

D. Solution

This problem is solved using bipartite  graph  which  acts as the conflicts  graph. The set  of teachers  and  subjects  are the two  disjoint independent  sets . edges are drawn connecting a vertex  from  teacher  set  to a vertex  in  subject  set, indicating  that the  subject requirement  matrix  given table .

The solution to the problem is obtained  by  proper  edge  coloring  of the bipartite  graph  as shown the following figure. The chromatic number acts as the minimum number  of  periods.

Conclusion

This paper focus our works into course Time Scheduling using bipartite graph .which helps the educational institute to construct effective time table.

References

[1] Welsh, D.J.A., and Powell, M.B., 1967, “An Upper Bound for the ChromaticNumberofaGraphandit\'sApplicationtoTimetablingProblems,”TheComputerJournal. 10(1), pp. 85-86. [2] Garey, R. D.,and Johnson, S., 1979, “Computers and intractability:A GuidetotheTheoryof NP-Completeness,”Freeman. [3] Burke, E. K., Elliman, D. G., and Weare, R., 1993, “A university timetablingsystembasedongraphcoloringandconstraintmanipulation,”JournalofResearchon Computingin Education, 27(1), pp. 1-18. [4] Wood,D.C.,1968,“ASystemforComputingUniversityExaminationTimetables,”TheComputerJournal, 11, pp.41-47. [5] Bondy, S., 2002, “Final Examination Scheduling,” Communications of theACM, 22(7), pp. 494-498.

Copyright

Copyright © 2022 Buvaneswari N, Rekha S. 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.