Araştırma Makalesi
PDF Zotero Mendeley EndNote BibTex Kaynak Göster

EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING

Yıl 2017, Cilt 3, Sayı 7, 51 - 59, 30.04.2017
https://doi.org/10.18768/ijaedu.309802

Öz

Graphs are discrete structures composed of vertices and edges connecting these vertices. Graphs are used in almost all disciplines as abstract models for the representation and study of a wide range of relations and processes in physical, biological, social and information systems. Many practical problems in a variety of areas like computer and communication networks, social networks, transportation networks, cellular networks, linguistics, chemistry, physics, biology can be represented and studied by graphs.

Real-world entities - like molecules, persons, groups, roles, species, computing and communication devices, terms - correspond to vertices. Relations among such entities - like preference, domination, independence, interference, proximity, constraints - imply the existence of edges between corresponding vertices. Thus, focusing on the abstract graph model instead of studying each particular instance as a different real-world problem reveals common underlying properties, deficiencies and principles. In this way, efficient approaches to real-world problems emerge from the theoretical study of their abstractions.

In this work, we use graph coloring to propose efficient solutions to scheduling problems arising in higher education. The objective of the graph coloring problem is to assign colors to graph vertices so that adjacent vertices, i.e., vertices connected by an edge, receive different colors. We consider as the objective of scheduling problems in higher education, like lecture and exam scheduling, to assign time/day slots to teaching or examination activities so that the maximum number of students can attend them with the fewest possible conflicts.

Our main motivation has been the crucial issue of efficient course and exam schedules often arising in departments of the University of Patras, Greece. Students usually have to attend lectures or exams scheduled in overlapping or simultaneous time slots. However, course and exam schedules are created based on heuristic approaches which may work well on average but certainly leave several room for improvement.

What if a graph-theoretic approach were used? Courses correspond to vertices of a graph and there is an edge between two vertices if and only if an appropriately selected minimum population of students attends corresponding courses (lectures/exams). Then, a coloring of such an underlying graph suggests an appropriate schedule for teaching/examination activities.

Using a simple coloring algorithm and the MATLAB programming environment, we have designed and developed a scheduling application which receives as input courses and constraints and outputs an efficient lecture/examination schedule. Experimental evaluation suggests that our application works well in practice. Ongoing work focuses on the use of a more involved coloring algorithm for addressing more complex course scheduling instances while minimizing required time resources.

Kaynakça

  • Appel, K. and Haken, W. (1977). The Solution of the Four-Color Map Problem. Scientific American, vol. 237, no. 4, pp. 108-121. Appel, K. and Haken, W. (1989). Every Planar Map is Four-Colorable. American Mathematical Society, vol. 98. Bondy J. A. and Murty U. S. R (1982). Graph theory with applications. Elsevier Science Publishing Co., Inc. ISBN: 0-444-19451-7 Brooks, R. L. (1941). On Coloring the Nodes of a Network. Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 37, Issue 2, pp. 194-197. Chaitin, G. J. (1982). Register allocation & spilling via graph colouring. In Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, pp. 98–105. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2001). Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7. Feige U., Kilian J. (1998). Zero knowledge and the chromatic number. Journal of Computer and System Sciences, vol. 57, pp. 187–199. Garey, M. R., Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. Håstad J. (1999). Clique is hard to approximate within n1−e . Acta Mathematica, vol. 182, pp. 105–142. Karp R. M. (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations, pp. 85–103. Kempe, A. B. (1879). On the Geographical Problem of Four Colors. American Journal of Mathematics, vol. 2, no. 3, pp. 193-200. Khanna S. and Kumaran K. (1998). On Wireless Spectrum Estimation and Generalized Graph Coloring. In Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 1998), IEEE, pp. 1449 - 1461. Khot S. (2001). Improved inapproximability results for MaxClique, Chromatic Number and Approximate Graph Coloring. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), IEEE, pp. 600–609. Lewis, R. (2015). A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers. Lovász, L. (1975). Three Short Proofs in Graph Theory. Journal of Combinatorial Theory, Series B, vol. 19, no. 3, pp. 111-113. Marx, D. (2004). Graph colouring problems and their applications in scheduling. Periodica Polytechnica, Electrical Engineering, 48 (1–2), pp. 11-16. Moler, C. (2004). The Origins of MATLAB. Mathworks. Narayanan L. and Shende S. (2001). Static Frequency Assignment in Cellular Networks. Algorithmica, vol. 29, issue 3, pp 396–409. Pardalos P. M., Mavridou T., Xue J. (1998). The Graph Coloring Problem: A Bibliographic Survey. Handbook of Combinatorial Optimization, Kluwer Academic Publishers, vol. 2, pp. 331-395. Roberts, F. S. (1978). Graph theory and its applications to the problems of society, CBMS-NSF Monograph 29, SIAM Publications. Xu J. (2003). Theory and application of graphs. Springer Science and Business Media, LLC. ISBN 9778-1-4613-4670-8 Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, vol. 3, pp. 103–128.

Yıl 2017, Cilt 3, Sayı 7, 51 - 59, 30.04.2017
https://doi.org/10.18768/ijaedu.309802

Öz

Kaynakça

  • Appel, K. and Haken, W. (1977). The Solution of the Four-Color Map Problem. Scientific American, vol. 237, no. 4, pp. 108-121. Appel, K. and Haken, W. (1989). Every Planar Map is Four-Colorable. American Mathematical Society, vol. 98. Bondy J. A. and Murty U. S. R (1982). Graph theory with applications. Elsevier Science Publishing Co., Inc. ISBN: 0-444-19451-7 Brooks, R. L. (1941). On Coloring the Nodes of a Network. Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 37, Issue 2, pp. 194-197. Chaitin, G. J. (1982). Register allocation & spilling via graph colouring. In Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, pp. 98–105. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2001). Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7. Feige U., Kilian J. (1998). Zero knowledge and the chromatic number. Journal of Computer and System Sciences, vol. 57, pp. 187–199. Garey, M. R., Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. Håstad J. (1999). Clique is hard to approximate within n1−e . Acta Mathematica, vol. 182, pp. 105–142. Karp R. M. (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations, pp. 85–103. Kempe, A. B. (1879). On the Geographical Problem of Four Colors. American Journal of Mathematics, vol. 2, no. 3, pp. 193-200. Khanna S. and Kumaran K. (1998). On Wireless Spectrum Estimation and Generalized Graph Coloring. In Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 1998), IEEE, pp. 1449 - 1461. Khot S. (2001). Improved inapproximability results for MaxClique, Chromatic Number and Approximate Graph Coloring. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), IEEE, pp. 600–609. Lewis, R. (2015). A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers. Lovász, L. (1975). Three Short Proofs in Graph Theory. Journal of Combinatorial Theory, Series B, vol. 19, no. 3, pp. 111-113. Marx, D. (2004). Graph colouring problems and their applications in scheduling. Periodica Polytechnica, Electrical Engineering, 48 (1–2), pp. 11-16. Moler, C. (2004). The Origins of MATLAB. Mathworks. Narayanan L. and Shende S. (2001). Static Frequency Assignment in Cellular Networks. Algorithmica, vol. 29, issue 3, pp 396–409. Pardalos P. M., Mavridou T., Xue J. (1998). The Graph Coloring Problem: A Bibliographic Survey. Handbook of Combinatorial Optimization, Kluwer Academic Publishers, vol. 2, pp. 331-395. Roberts, F. S. (1978). Graph theory and its applications to the problems of society, CBMS-NSF Monograph 29, SIAM Publications. Xu J. (2003). Theory and application of graphs. Springer Science and Business Media, LLC. ISBN 9778-1-4613-4670-8 Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, vol. 3, pp. 103–128.

Ayrıntılar

Konular Sosyal
Bölüm Makaleler
Yazarlar

Evi Papaioannou Bu kişi benim
Greece


Stavros Athanassopoulos Bu kişi benim
Greece


Christos Kaklamanis
Greece

Yayımlanma Tarihi 30 Nisan 2017
Başvuru Tarihi 30 Nisan 2017
Kabul Tarihi 31 Mart 2017
Yayınlandığı Sayı Yıl 2017, Cilt 3, Sayı 7

Kaynak Göster

EndNote %0 International E-Journal of Advances in Education EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING %A Evi Papaioannou , Stavros Athanassopoulos , Christos Kaklamanis %T EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING %D 2017 %J IJAEDU- International E-Journal of Advances in Education %P 2411-1821-2411-1821 %V 3 %N 7 %R doi: 10.18768/ijaedu.309802 %U 10.18768/ijaedu.309802

                                                           Published and Sponsored by OCERINT International © 2015

                                                                              Contact: ijaedujournal@hotmail.com