Scheduling

Implementing A Class Scheduling Problem at The College Of Business And Economics Of Bahir Dar University, Ethopia – Biniyam Asmare Kasa

The paper addresses a class scheduling integer programming optimization problem. Initially the schedule was made manually, this was both time consuming and inefficient. It required a number of revisions before the actual schedule was out.  With rapidly increasing number of students this became more difficult. The curriculum had been changed to a modular system, i.e. the starting and the ending week of courses may vary across programs and courses, compared to the pre-modular curriculum wherein all the courses were full semester (Biniyam Asmare Kasa 2015). There is no more a notion of “representative week” (a weekly schedule followed for the entire term), due to the introduction of the modular curriculum with different starting and end dates, the new solution has to address the class conflicts that might occur (Biniyam Asmare Kassa 2015). A sequential problem solving algorithm is implemented to address this problem.

The sequential approach includes dividing the problems into stages and achieving part of the objectives, and then moving onto the other stage of the sub-problem using the optimal solution from the previous stage (Biniyam Asmare Kassa 2015). This approach tries to solve the problem faced by CoBE, a department inside the Bahir Dar University(BDU).  The final objective was to come up with a timetable. The first stage of the problem involves assigning instructor to each of the courses which forms the instructor assignment problem. Using the results obtained from the first stage, section-instructor combination(class), these classes are then assigned to the rooms available at CoBE. After the instructor class and the rooms have been assigned, stage three results in assigning to each of these classes specific required number of hours. The stages are different linear integer programming problems each with constraints related to instructors- their preferences, teaching load; classes- minimizing rooms, considering the disability students, proximity to classes and for hours – desirable time for students and the instructor (Biniyam Asmare Kassa 2015). The problem was solved using an AMPL-Gurobi package. AMPL reads the commands from the text files and the relevant data from the excel workbook. It then generates the optimization model. This model is then sent to the Gurobi linear and integer program solver which is then used to solve the sub problems (different stages). As the size of the Problem becomes larger i.e. the number of sections assigned to each room increases the software needs to be interrupted to come up with a solution. By interrupting we do not arrive at an optimal solution but a feasible solution. As a rule of thumb the team used the threshold of 10 minutes on the run time and stopped there after (Biniyam Asmare Kassa 2015). The solution obtained after 10 minutes was considered feasible. Particularly the solution time dependent on the (size of the problem) number of sections to be allotted to each rooms. With an increase in this the solution time increased (Biniyam Asmare kassa 2015).

...