A direct barter model for course add/drop process

• Published in: Discrete Applied Mathematics 2011-04, Vol.159 (8), p.812-825
• Main Authors: HAYDAR OZER, Ali, ÖZTURAN, Can
• Format: Article
• Language: English
• Subjects: Add drop; Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Barter network; Bartering; Calculus of variations and optimal control; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Computer systems performance. Reliability; Course scheduling; Exact sciences and technology; Mathematical analysis; Mathematical models; Mathematics; Minimum cost; Network flow; Networks; Optimization; Policies; Scheduling; Sciences and techniques of general use; Software; Student registration; Students; Theoretical computing; Timetabling; Weighting
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2011.01.004

Even though course timetabling and student scheduling problems have been studied extensively, not much has been done for the optimization of student add/drop requests after the initial registration period. Add/drop registrations are usually processed with a first come first served policy. This, however, can introduce inefficiencies and dead-locks resulting in add/drop requests that are not satisfied even though they can, in fact, be satisfied. We model the course add/drop process as a direct bartering problem in which add/drop requests appear as bids. We formulate the resulting problem as an integer linear program. We show that our problem can be solved polynomially as a minimum cost flow network problem. In our model, we also introduce a two-level weighting system that enables students to express priorities among their requests. We demonstrate improvement in the satisfaction of students over the currently used model and also the fast performance of our algorithms on various test cases based on real-life registration data of our university.