Genetic Algorithm With Three-Dimensional Population Dominance Strategy for University Course Timetabling Problem

Introduction

University course timetabling is a great heavy and important task in the educational administration work. It is related to the overall quality of teaching and the overall use of teaching resources. In the information society, universities are in urgent need of an effective way to solve the problem. However, the university course timetabling problem is a multi-constrained and multi-objective combinatorial optimization problem, which has been proved to be a NP- problem (Zhang, Zhang, & Qian, 2017). At present, many algorithms have been proposed to solve this problem, such as constraint programming (Shahmoradi, Ketabi,& Esmaelian, 2017; Feras, Mahmoud, Fares, & Sahel, 2017; Luleseged, 2019; Muklason, Bwananesia, Hidayatul, Angresti,& Supoyo, 2018), particle swarm optimization (Shiau, 2011), adaptive large neighborhood search (Kiefer, Hartl, & Schnell, 2017), etc. Although these algorithms (Adewumi, Sawyerr,& Montaz, 2009; Thatchai, Pupong,& Srisatja, 2016; Velin, Radoslava, & Borislav, 2016; Muklason, Bwananesia, Hidayatul, Angresti, & Supoyo, 2018) can partly solve the university course timetabling problem, there are the following shortcomings:

• 1.

  The heuristic information of the search process depends on the actual situation, and the relevant solving solutions of the university course timetabling problem can only be used to solve a few practical problems, which cannot form a general and effective course scheduling method.

• 2.

  Although the expert system technology can effectively organize the knowledge of the course arrangement, it is difficult to obtain the relevant rules of all the elements required in the course arrangement, so the results are not ideal.

• 3.

  The relevant criterions are less, and the relevant algorithms can only be solved in one direction and cannot optimize the multi-direction of the university course timetabling problem.

Because the genetic algorithm needs only the objective function and the corresponding fitness function in the evolution process, the overall search strategy and the search method do not depend on gradient information or other auxiliary knowledge in the search process. It does not depend on the specific domain of the problem, which has more strong robustness (Feng, Lee, & Ilkyeong, 2017). In view of this, this paper uses a genetic algorithm to solve the university course timetabling problem. This paper gives up the pursuit of the “absolute best”, in addition to the basic hard constraint that teacher, class, classroom at any time can only be arranged once, if the university course timetabling scheme can meet the “reasonable, practical and unique” requirements in the artificial course arrangement, we think it is feasible and relatively advantageous.

Related Works

University course timetabling problem can be seen as a resource allocation problem (Salem & Sherali, 2015), that is, some quantitative resources are allocated to individual requirements under the premise of satisfying some constraints (Simon & Matias, 2015). The main goal is to arrange classrooms, teachers, classes, and courses in a non-conflicting time within a week (Soria-Alcaraz, Ochoa, & Swan, 2014).

There are many conflicts in the process of course arrangement, the main influencing factors are as follows (Salman, Mehdi, & Omid, 2013; Salwani, Hamza, & Barry, 2012; Aladag, Hocaoglu, &Basaran, 2009; Zhang, Liu, & Hallah, 2010; Anmar & Masr, 2009):

• 1.

  Time factors: In university course timetabling problem, the class time is usually calculated on a weekly basis. Weekly class time is not more than 7 days, each day is divided into morning time, afternoon time and evening time, and each time has the definite class sections. The smallest unit of class time is the section, a section is a class time, and a course class time is two sections.

• 2.

  Course factors: Each course has its own number, name, department and teaching plan, such as, which week begins, or which week terminates, and how many course class times a week, and so on.

• 3.

  Classroom factors: Each classroom has a corresponding number, house number and name, and can only accept a teaching course in a course class time, and its capacity should be not smaller than the number of students of the corresponding class.

• 4.

  Class factors: Each class has its own number, name, and can only accept a teaching course in a course class time.

• 5.

  Teacher factors: Each teacher has its own number, name, and can only teach a course in a course class time.