The University Course Selection Problem: Efficient Models and Experimental Analysis
Résumé
The university course selection problem (UCSP) deals with 1nding an optimal choice of courses from a set of alternatives to attain a prescribed goal. It is assumed that a timetable is already given. If the planning is done for a term, the problem is simple and can be solved by complete enumeration using a computer. For multi-year planning, complete enumeration is impractical. The problem is made more complicated when inter-campus travel is also involved.
In this paper, we formulate UCSP as a maximum weight independent set problem with specially structured additional constraints. Data for the experiments are collected from the SFU student information system. Experimental results using a general purpose integer programming solver are given. Our model could easily solve the problem, producing an optimal solution in very reasonable running time.
Références
Ans’otegui, C., Bonet, M.L., Levy, J. and Many‘a, F. (2007). ‘The logic behind weighted CSP’, In Proceedings of the 20th International Joint Conference on ArtiïnAcial Intelligence IJCAI-07, pp.32–37.
Bistarelli, S., Montanari, U. and Rossi, F. (1997). ‘Semiring-based constraint solving and optimization’, Journal of ACM, Vol.44(2), no.3,pp.201-236
Carter, M.W. (2001). ‘A comprehensive course timetabling and student scheduling system at the University of Waterloo’, LNCS, Vol.2079, pp.64–84.
Carter, M.W. (1986). ‘A Survey of Practical Applications of Examination Timetabling Algorithms’,INFORMS, Vol.34,No.2, pp.193–202.
Carter, M.W. and Laporte, G. (1998). ‘Recent developments in practical course timetabling’,Practice and Theory of Automated Timetabling II,Springer-Verlag LNCS 1408,pp.3–19.
Chang, M.S. and Wang, F.H. (1992).‘EZcient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs’,Information Processing Letters,43, pp.293–295.
Chipara, O., Lu, C. and Stankovic, J. (2006) ‘Dynamic Con2ict-free Query Scheduling for Wireless Sensor Networks’, in Proceedings of the 14th IEEE International Conference on Network Protocols.
Dinkel, J.J., Dinkel, J.M. and Venkataramanan, M. A.(1989). ‘An EZcient Decision Support System for Academic Course Scheduling’, INFORMS, Vol.37, pp853–864.
Ferland, J.A. and Fleurent, C. (1994). ‘A Decision Support System for Course Scheduling’, INFORMS, Vol.24, No.2, pp.105–115.
Freuder, E.C. and Wallace, R.J. (1992). ‘Partial constraint satisfaction’, Arti1cial Intelligence, Vol.58, pp.21–70.
Hori, Y., Nakayama, T., Imai, Y. (2010). ‘Constructing Student Personal Course Scheduling Problem with Spreading Activation on a Course Network’, Proceedings of the International Multi Conference of Engineers and Computer Scientists, Vol.I.
Ismayilova, N.A., Ozdemir, M.S., Gasimov, R.N. (2007)‘A Multiobjective Faculty-Course-Time Slot Assignment Problem With preferences’, Math. Comput. Modelling 46, pp1017–1029.
Nozawa, T., Ida, M. (2005). ‘Construction of Curriculum Analyzing System Based on Document Clustering of Syllabus Data(Education)’, ransactions of Information Processing Society of Japan, Vol.46, No.1, pp.289–300.
Oboth, C., Batta, R. and Karwan, M. (2013). ‘Dynamic con2ict-free routing of automated guided vehicles’, International Journal of Production Research, Vol.37:9,pp.2003–2030.
Schaerf, A. (1995). ‘A survey of automated timetabling’, Technical Report CS-R9567, CWI, Amsterdam,NL.
Stallaert, J. (1997). ‘Automated Timetabling Improves Course Scheduling at UCLA’, INFORMS, Vol.27, pp.67–81.
Werghi, N. and Kamoun, F. (2010). ‘A decision-tree-based system for student academic advising and planning in information systems programmes’,Int. J. Business Information Systems,Vol.5, No.1.
Wu, K. and Havens, W.S. (2005). ‘Modeling an Academic Curriculum Plan as a Mixed-initiative Constraint Satisfaction Problem’,Canadian Conference on AI,Vol.3501, pp.79–90.
Téléchargements
Publié-e
Rubrique
Licence
The images, figures, and tables in the Simon Fraser University Operations Research Undergraduate Journal are not necessary those of the Simon Fraser Student Society, Operations Research Union, or the Department of Mathematics at Simon Fraser University or their respective Directors and Executives. The copyright of all contributions remains with their authors. By submitting to Analytics Now, authors acknowledge that submissions reflect original work, and that proper credit has been given to outside sources.
All material herein is Copyright 2012 by the respective authors. Permission to reprint or reproduce the material contained herein is prohibited without express written permission from the author and publisher with the exception of dissemination for non-profit, educational, academic, or informative purposes.
