Name
Abstract | ||
|---|---|---|
The class scheduling problem can be modeled by a graph where the vertices and edges represent the courses and the common students, respectively. The problem is to assign the courses a given number of time slots (colors), where each time slot can be used for a given number of class rooms. The Vertex Coloring (VC) algorithm is a polynomial time algorithm which produces a conflict free solution using the least number of colors [9]. However, the VC solution may not be implementable because it uses a number of time slots that exceed the available ones with unbalanced use of class rooms. We propose a heuristic approach VC* to (1) promote uniform distribution of courses over the colors and to (2) balance course load for each time slot over the available class rooms. The performance function represents the percentage of students in all courses that could not be mapped to time slots or to class rooms. A randomized simulation of registration of four departments with up to 1200 students is used to evaluate the performance of proposed heuristic. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/AICCSA.2010.5586963 | Computer Systems and Applications |
Keywords | Field | DocType |
time slot,vc solution,class scheduling problem,graph coloring,performance function,polynomial time algorithm,class room,proposed heuristic,heuristic approach,available class room,conflict free solution,scheduling problem,computational complexity,schedules,uniform distribution,color,algorithms,scheduling | Discrete mathematics,Heuristic,Mathematical optimization,Job shop scheduling,Vertex (geometry),Scheduling (computing),Computer science,Computer network,Schedule,Time complexity,Graph coloring,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-1-4244-7716-6 | 8 | 0.56 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amal Dandashi | 1 | 11 | 2.15 |
| Mayez Al-Mouhamed | 2 | 25 | 7.54 |