International Conference on Information and Communication Technology and Its Applications (ICTA 2016) Federal University of Technology, Minna, Nigeria November 28 – 30, 2016 Concurrent Student Seminar Scheduling Using Genetic Algorithm Ojoajogu Ajanya and Hamza O. Salami Department of Computer Science, Federal University of Technology, Minna, Nigeria ogajanya@yahoo.com, ho.salami@futminna.edu.ng Abstract—Scheduling involves assigning variables to specific teachers and the students. Timetable problem is a real-life domains according to resources and wishes. Usually, many combinational problem concerned with scheduling of a students are ready to present seminars at the same time. In certain number of events within a specific time frame. order to maximize time, student seminars can hold Therefore, seminar scheduling is an example of the concurrently in multiple venues. Manual scheduling of student timetabling problem. seminars is tedious since it must be painstakingly planned to Seminar scheduling entails arranging time slots for minimize clashing of panelists, who must be present when seminar sessions while considering some constraints like students present. This paper presents a genetic algorithm (GA) number of participants, capacity of the venue, number of for automatically scheduling parallel student seminars to presentations by facilitators, and so on. Seminar scheduling minimize clashes and inconvenience to panelists. Experimental results show that GA-based seminar scheduling is promising. problem is a problem related to assigning variables to specific domains according to resources and wishes. As Keywords-genetic algorithm; seminar scheduling; parallel population of participants gets larger and larger while seminars resources like venues and supervisors remain constant or diminish, manually performing scheduling under these constraints becomes an incredibly hard problem. Also, each I. INTRODUCTION defined constraint restricts the area and the problem becomes Order is a critical factor that guarantees proper harder, thus it takes a long time to get a solution by human- organization of events; where there is disorderliness, there is based techniques. bound to be confusion and ultimately, loss of productivity. In The main contribution of this paper is in the use of the academic community seminars are examples of events Genetic Algorithm (GA) to plan concurrent student seminars which must be properly ordered. Student seminars are oral in order to avoid/minimize conflicts in the seminar presentations which are part of the requirements for students’ schedules. GA is a search and optimization technique based academic programmes. Seminars are usually coordinated by on natural genetics and natural selection [2]. The rest of this a designated member of staff who takes into consideration paper is organized as follows: A review of related works is the schedules of the panelists who should be physically presented in Section II. The seminar scheduling problem is present at the seminars. A student’s panelists comprise explained in Section III. In Section IV, a detailed description his/her project supervisors, co-supervisors and of a GA for automatic seminar scheduling is presented. examiners/assessors. Experimental results appear in Section V, while the paper is In cases where many students are ready to present concluded in Section VI. seminars around the same period, two approaches can be adopted. On one hand, students can present seminars one-at- a-time. Even though this approach eliminates the clashing of II. RELATED WORKS panelists, it creates the problem of having all panelists available throughout the seminar presentations. On the other Although little has been written about seminar hand, seminars can be scheduled to run concurrently. The scheduling, it is closely related to other problems that have latter approach minimizes the overall seminar presentation received significant research attention like the timetabling time, but requires that students are carefully scheduled such problem and examination scheduling [3]. that the panelists who should be on ground during the A genetic algorithm-based intelligent system was presentations are not required to be in more that one seminar proposed in [4] for course scheduling in higher education. location at any given time. The GA helped to optimize the preparation of class A timetable is “a table of events arranged according to schedules. The test result obtained 99 conflicting classes the time when they take place” [1]. Timetables are very from 635 existing classes. The average non-conflict important for the university administration; they give scheduling accuracy of the system is 84.4%. students and teachers a schedule indicating the right time and In [5], GA was used to develop an optimization-based the right place to be, the availability of the rooms, the time to prototype for nurse assignment that makes daily decisions on be spent by the teachers for the period, the availability of the assigning nurses to patients. A prototype for assigning nurses 56 International Conference on Information and Communication Technology and Its Applications (ICTA 2016) to patients with the purpose of minimizing excess workload present during a student’s seminar because they ask on the nurses was developed. questions and based on the student’s response, determine if According to [6], scheduling classes is a time consuming the student can proceed to the next stage of study or not. It is job for administrators. Many constraints are defined for important for supervisors to be present during their classrooms, faculty members, and courses, whereby, a course supervisees’ seminars because they might be required to may require a classroom with some minimum number of clarify issues related to their supervisees’ research. seats and with some audiovisual equipment. Also, a faculty Let S = {s1, s2, s3 … sNS} be a set of NS students and let L member may prefer not to teach two or more courses in a = { l1, l2, l3 … lNL} be a set of NL lecturers. The panelist row, or may prefer teaching before certain time. In view of matrix P is a NS x NL matrix. The entry Pij in the matrix is 1 these, the researcher employed GA for finding a “good” if the jth lecturer lj is a panelist for the ith student si. schedule that results in an efficient use of each classroom, in Otherwise, the entry is zero. A sample of the panelist matrix relation to time, space, and constraints. is shown in Fig. 1. From the first row of the matrix, l2 and l3 Analytical Hierarchy Process (AHP) and GA have been are panelists for s1. Furthermore, from column one of the combined to create a time table schedule that matches most matrix, l1 is a panelist for only s3. Let the number of periods of the teachers’ preferences [7]. The approach consists of the (i.e., time slots) and venues be denoted by NP and NV, integration of a satisfaction function to the genetic algorithm. respectively. Assume that the NS students are to be The parameters of the satisfaction function are the teachers’ scheduled concurrently in NV venues within NP periods. Let loads and a set of scores calculated using the analytical a session be defined as a combination of a venue and a hierarchy process. The key point of AHP in calculating the period. Fig. 2 shows how sessions are numbered from scores is the pairwise comparison of a set of teachers’ periods and venues. Note that the number of sessions, NSS = criteria. The new approach was consequently a combination NV * NP. of AHP and GA, and it gives rise to a new methodology to SSP involves assigning students to different sessions solve the time table problem that is called AHP/GA. such that certain hard and soft constraints are satisfied. Hard Researchers in [8] presented an experimental constraints are constraints that need to be satisfied for a investigation into solving the Assignment model using GA solution to be feasible. Soft constraints are constraints that and Simulated Annealing. Various parameters affecting the must not necessarily be fulfilled, that is, they are allowed to algorithms are studied and their influence on convergence to be violated. the final optimum solution was shown. While solving this The hard constraints for the SSP are: problem through GA, a unique encoding scheme was used  Each student shall present exactly one seminar. together with Partially Matched Crossover (PMX).  Only one student can present a seminar in a given In their work, [9] combined the attributes of fuzzy logic session. and Genetic Algorithm to create a Fuzzy Genetic Heuristic  All the panelists for a student must be present during (FGH) Algorithm which they used to solve the university the student’s seminar. course timetable problem. They posit that fuzzy logic models  No panelist can be in more than one venue at a time. are easy to comprehend because they use linguistic terms and The only soft constraint considered seeks to minimize structured rules but do not come with search algorithms. inconvenience resulting from lecturers moving from one Unlike GA, fuzzy models adopt techniques from other areas venue to another at different time periods: such as statistics and linear system identification. Thus they Each panelist should remain in one venue throughout the harnessed GA’s search ability by merging both paradigms entire seminar presentations. and created FGH algorithm, which describes Fuzzy Set Fig. 3 shows two ways of scheduling student seminars model using GA search attribute. FGH uses an indirect within two venues and two periods. Panelists (obtained from representation featuring event allocation priorities and Fig. 1) are shown alongside each student. Panelists causing invokes a timetable builder routine for constructing complete hard constraint violations are shown in red, while those timetable. causing soft constraint violations are shown in green. There The work reported in [3] focused on the preference-based are two hard constraint violations from the seminar schedule conference scheduling (PBCS) problem, in which of Fig. 3(a) since l2 and l5 are required to be in multiple preferences of conference attendees are taken into venues at the same period; l2 is required to be in venue 1 and consideration. PBCS was formulated as an integer venue 2 in period 1, whereas l5 is required to be in both programming problem. Since the formulation is NP venues in period 2. Furthermore, there are two soft constraint complete, simulated annealing was used to obtain good violations from Fig. 3(a); l3 moves from venue 1 to venue 2, solutions to a PBCS for a real life conference that involved while l4 moves from venue 2 to venue 1. There are no hard scheduling 213 sessions over 10 time-blocks for 520 constraint violations on Fig. 3(b). The only soft constraint attendees who had preferences. violations are as a result of l2 and l5 changing venues. III. SEMINAR SCHEDULING PROBLEM IV. GENETIC ALGORITHM The seminar scheduling problem (SSP) is concerned with Genetic Algorithm (GA) is a search algorithm which arranging concurrent student seminars in such a way that no mimics the survival of the fittest strategy that occurs in the panelists are required to be in more than one seminar at the natural world [7]. It is an iterative search technique same time, and the movement of panelists to different venues developed based on evolutionary genetics which seeks the is minimized. A student’s panelists are his/her research best of a set of solutions [10]. GA follows five phases supervisors and examiners/assessors. Examiners must be namely: generating an initial population, evaluating the 57 International Conference on Information and Communication Technology and Its Applications (ICTA 2016) fitness of the chromosome, selection, crossover and which is an encoded version of potential solution parameters mutation. The process of selection, crossover and mutation rather than optimizing the parameters themselves [12]. are iterated until the optimal solution is obtained [11]. This Thirdly, GA uses fitness values obtained from objective algorithm explores the search space and makes use of the functions without other artificial over engineered black box generated knowledge to find a better population. A flowchart mathematics [7]. The user typically chooses the best of the standard GA is presented in Fig. 4. The performance structure of the last population as the final solution. The of GA is usually evaluated in terms of convergence rate and algorithm is complete when one of the following occurs: a the number of generations to reach the optimal solution. specified tolerance threshold is achieved; a specified number of generations has passed; a specified amount of Lecturers computational time has passed; or the solution fitness has plateaued [13]. The inputs to the GA for solving the SSP are the number l1 l2 l3 l4 l5 of venues NV, the number of periods NP, and the panelist s1 0 1 1 0 0 matrix P. The output of the GA is the seminar schedule Students similar to those shown in Fig. 3. s2 0 1 0 1 0 s3 1 0 1 0 1 A. Chromosome Representation Each chromosome is a row vector having NS genes. The s4 0 0 0 1 1 value in each gene determines the session in which a student presents his/her seminar. For example, the value of the first Figure 1. A Panelist Matrix with Four Students and Five Lecturers gene states the session during which s1 presents, the value of the second gene specifies the session during which s2 presents, and so on. Because each student must present in a unique session, the values in the chromosome are distinct Period 1 Period 2 integers ranging from 1 to NSS. It is noteworthy that this chromosome representation ensures that the first two hard Venue 1 Session 1 Session 4 constraints are always satisfied. Fig. 5 shows how the seminar schedules shown in Fig. 3 are encoded as Venue 2 Session 2 Session 5 chromosomes. The chromosome in Fig. 5(a) indicates that s1, s2, s3 and s4 present in the first, second, fourth and third Venue 3 Session 3 Session 6 sessions respectively, while Fig. 5(b) shows that s1, s2, s3 (a) and s4 present in the first, fourth, third and second sessions, respectively. Period 1 Period 2 Period 3 Session 1 Session 3 Session 5 B. Fitness Function Venue 1 As mentioned in Section IV(A), the first two hard Venue 2 Session 2 Session 4 Session 4 constraints have been taken care of from the chromosome (b) representation. The third hard constraint is assumed to hold all the time. Thus once a student appears in a session, all the Figure 2. Sessions (a) three venues and two periods (b) two venues and student’s panelists are assumed to be present. The fitness three periods function therefore handles the last hard constraint and the only soft constraint. The last hard constraint states that panelists can only be in one place at a time. A clash occurs Period 1 Period 2 when a panelist is required to be in different venues at the Venue 1 s1 (l2, l3) s4 (l4, l5) same period. Similarly, the soft constraint seeks to eliminate the inconvenience of panelists moving from one venue to the Venue 2 s2 (l2, l4) s3 (l1, l3, l5) other. The fitness function F for the GA can be described (a) mathematically using (1). Period 1 Period 2 NL s1 (l2, l3) s3 (l1, l3, l5) F (C )   (100 * Clashes (C , i)  Movements(C , i))   Venue 1 i 1 Venue 2 s4 (l4, l5) s2 (l2, l4) Where, NL is the number of lecturers; C is the (b) chromosome; and Clashes(C, i) is a function that computes Figure 3. Constraint violations (a) Hard and soft constraints violations (b) the number of times li is required to be in multiple venues at Soft constraints violations the same period, when chromosome C is used to generate the seminar schedule. Movements(C, i) is a function that A notable characteristic of GA is that it is a parallel computes the number of times li is required to move from population-based search with stochastic selection, crossover one venue to another, when chromosome C is used to and mutation [12]. Secondly, GA works on the chromosome generate the seminar schedule. 58 International Conference on Information and Communication Technology and Its Applications (ICTA 2016) E. Mutation Start Mutation is the infrequent introduction of new features into the solution strings of the population pool to maintain Initialization diversity in the population. Mutation was achieved by swapping two randomly selected genes of a chromosome based on the probability of mutation. The mutation operator Evaluation stops the algorithm from getting stuck in local minima. Fig. 6 shows how mutation swaps a pair of genes (sessions) between two students. The first and third genes, which are Selection shaded were swapped during mutation. F. Stopping Criteria Crossover Selection, crossover and mutation were repeated after generation of the initial population until one of the following conditions is satisfied: (i) the best fitness value of zero is Mutation obtained, signifying that no constraint is violated, (ii) the No maximum number of generations is reached, (iii) or the fitness value does not improve within a preset number of Meet stopping criteria generations. Yes V. EXPERIMENTAL RESULTS End This section discusses experimental results used to validate the proposed GA. The GA was implemented using Figure 4. Flowchart of the Genetic algorithm process [14] the MATLAB® simulation tool. Because hard constraints are more severe than soft A. Evaluation Criteria constraints, the former are penalized 100 times more than the The fitness values and running times were used to latter. The GA searches for the chromosome with the evaluate the performance of the developed GA-based minimum fitness value (minimum total number of clashes seminar scheduler. and movements). The fitness values of the seminar schedule presented in Fig. 3(a) is 202 since there are two clashes and B. Experimental Dataset two movements of panelists. On the other hand, the schedule Eleven datasets were used to evaluate the GA-based in Fig. 3(b) has a fitness value of 2 since all hard constraints student seminar scheduler. Table I shows the characteristics were satisfied but panelists changed venues twice. of each dataset. The first dataset comprises real data obtained C. Selection from the Department of Computer Science, Federal University of Technology, Minna when Masters students of This process is used in the GA to determine which the Department presented their final thesis seminars in April solutions are to be preserved and allowed to reproduce and 2016. The panelist matrix for that dataset is shown in Table which ones are to be discarded based on their fitness values. II. For the other ten datasets, the number of venues, number The primary objective of the selection operator is to retain of periods, and the panelist matrices were randomly the good solutions and eliminate the bad ones in a population generated such that each student had between two and four and still keep the population size constant. The type of randomly selected panelists. Note that the second, third, selection operator to be used is the rank selection, chosen for fourth and fifth datasets have the same panelist matrix and its ability to allow fittest individual to be selected. The number of sessions, but different combinations of number of fitness values of the chromosomes were used to sort them in venues and periods. ascending order. This prevents bias towards individuals that are highly fit, thereby reducing speedy convergence. C. Experimental Setup D. Crossover MATLAB R2010a was used to implement the GA. The The crossover operator is used to create new solutions experiments were carried out on a computer system having a from the existing solutions available in the mating pool after processor speed of 2.4GHz as well as main memory capacity applying rank selection operator. Crossover exchanges the of 4GB, and running the 64-bit windows 7 operating system. gene information between the solutions in the mating pool. The parameters used to run the GA experiments are as Partially-mapped crossover was used in this work because it follows: the GA was halted after 1,000 generations or if the prevents duplication of genes. Crossover operators like best fitness value obtained did not improve within 50 single point crossovers and double point crossovers often generations. The probability of mutating each gene in the result in duplication of genes indicating that a student population is 0.02 while the probability of crossover is 0.9. presents in multiple sessions, violating the hard constraint All the experiments were run 30 times since GA is that requires each student to present his/her seminar once. stochastic. 59 International Conference on Information and Communication Technology and Its Applications (ICTA 2016) D. Results and Discussion 1 2 3 4 1 2 3 4 Fig. 7 shows a seminar schedule generated by GA. The 1 2 4 3 1 4 3 2 fitness value obtained from this schedule is four, since there (a) (b) are no panelist clashes but panelists had to change venue four Figure 5. Chromosome representation for seminar schedule (a) times, as indicated by the green-colored panelists. Chromosome for Fig. 3(a); (b) Chromosome for Fig. 3(b) The second, third, fourth and fifth datasets all have 12 sessions as well as the same panelist matrix. They only differ in the number of venues and periods. Fig. 8 shows the relationship between the average fitness value and number of venues for a fixed number of sessions using the four datasets. It can be seen that as the number of venues increases, the 1 2 3 4 1 2 3 4 number of constraint violations also increases. In the extreme case of excessive parallelism, there is only one period and 2 4 1 3 1 4 2 3 (a) (b) multiple venues, so all seminars take place at once, resulting in significant constraint violations. On the other hand, when Figure 6. Mutation (a) Before mutation (b) After mutation there is only one venue, there are no constraint violations because is no parallelism at all and each student presents in a distinct period. Table III shows the fitness values and execution time of GA for all the datasets. There are no results for Dataset 9, TABLE I. SUMMARY OF THE DATASETS because the GA is programmed to compare the number of Dataset Number Number of Number of Number of students with the number of sessions before actual execution of venues periods students Panelists starts. If the former is greater than the later, the GA displays 1 2 7 11 13 an error message and terminates because hard constraint(s) 2 6 2 6 10 are guaranteed to be violated when the number of students 3 4 3 6 10 exceeds the number of sessions. Otherwise, the GA proceeds 4 3 4 6 10 5 2 6 6 10 normally. The number of venues and periods for Dataset 9 6 3 6 15 15 are two and twelve respectively, resulting in twenty four 7 3 8 20 18 sessions, while the number of students is twenty seven. 8 3 10 25 18 Fitness values for majority of the datasets shown in Table III 9 2 12 27 20 are less than 100, indicating that only soft constraints were 10 3 15 30 20 11 2 20 40 20 violated. This shows that the GA is highly successful in finding good seminar schedules. VI. CONCLUSION TABLE II. PANELIST MATRIX FOR FIRST DATASET In this research work, a Genetic Algorithm was formulated Lecturers for scheduling seminars. The GA seeks to minimize clashes 1 2 3 4 5 6 7 8 9 10 11 12 13 among panelists and inconvenience due to panelists’ change 1 1 0 0 1 0 0 0 0 0 1 0 0 0 of venues. Experimental results show that soft constraint 2 0 1 1 0 1 0 0 0 0 0 0 0 0 violations regarding movement of panelists can hardly be 3 0 1 1 0 0 0 0 0 0 0 0 0 1 Students 4 1 0 1 0 0 0 0 0 0 0 1 0 0 avoided, whereas hard constraint violations can be avoided 5 0 0 1 0 0 0 0 1 1 0 0 0 0 depending on the inputs to the GA. In future, we plan to 6 1 0 0 0 0 1 0 0 0 0 0 1 0 incorporate panelists’ preferences for period(s) in the GA. 7 1 1 0 0 1 0 0 0 0 0 0 0 0 Furthermore, the GA can be improved so that empty 8 0 1 0 0 0 0 1 0 0 0 0 0 0 sessions when no students are presenting do not appear 9 1 1 0 0 0 0 0 0 0 0 0 0 0 between sessions when students are presenting. For 10 1 1 0 0 1 0 0 0 0 0 0 0 0 11 1 0 0 0 0 0 1 0 0 0 0 0 0 example, sessions 3, 5 and 11 on Fig. 7 are empty, so they should appear at later periods, so that students and lecturers can finish with the seminar as soon as possible. Period 1 Period 2 Period 3 Period 4 Period 5 Period 6 Period 7 Venue 1 s1 s11 s9 s8 (l1, l4, l10) (l1, l7) (l1, l2) (l2, l7) Venue 2 s3 s10 s7 s2 s5 s4 s6 (l2, l3, l13) (l1, l2, l5) (l1, l2, l5) (l2, l3, l5) (l3, l8, l9) (l1, l3, l11) (l1, l6, l12) Figure 7. Generated schedule for first dataset 60 International Conference on Information and Communication Technology and Its Applications (ICTA 2016) Figure 8. Relationship between average fitness value and number of venues TABLE III. FITNESS VALUES AND EXECUTION TIMES FOR GA Fitness Value Execution Time (seconds) Dataset Mean Min Max Mean Min Max 1 4.20 3.00 6.00 0.90 0.56 1.64 2 501.00 501.00 501.00 0.53 0.39 0.69 3 201.27 201.00 202.00 0.51 0.37 0.74 4 102.00 102.00 102.00 0.40 0.28 0.48 5 0.00 0.00 0.00 0.01 0.00 0.02 6 112.47 109.00 115.00 1.27 0.57 3.52 7 16.83 14.00 20.00 2.21 0.96 3.71 8 24.10 20.00 29.00 2.88 1.30 4.94 9 - - - - - - 10 23.50 20.00 28.00 2.17 1.27 6.54 11 18.17 13.00 26.00 3.94 2.17 7.09 [8] A. Sahu, and R. Tapadar, “ Solving the assignment problem using REFERENCES genetic algorithm and simulated annealing,” IMECS, pp. 762-765, 2006. [1] Collins Dictionary, “Timetable,” retrieved 16th October, 2015 from https://www.collinsdictionary.com/dictionary/english/timetable. [9] A. Chaudhuri, and K. De, “Fuzzy genetic heuristic for university course timetable problem, “ International Journal of Advances in Soft [2] D. A. Singh, E. Leavline, R. Priyanka, and P. Priya, “Dimensionality Computing and its Applications, vol. 2 no. 1, pp.100-123, 2010. reduction using genetic algorithm for improving accuracy in medical diagnosis,” I.J. Intelligent Systems and Applications, vol. 8 no. 1, pp. [10] T. Engin, “Genetıc algorithm optimization method in the timetable 67-73, 2016. schedules of public transportation,” International Journal Of Engineering Sciences & Research Technology, vol. 3 no. 5, pp. 555- [3] S. E. Sampson, “Practical implications of preference-based 562, 2014. conference ccheduling.,” Production and Operations Management, vol. 13 no. 3, pp. 205-215, 2004. [11] N. Kumar, and R. K. Karambir, “A comparative analysis of PMX, CX and OX crossover operators for solving traveling salesman [4] A. Mardiyono, “An intelligent system for course scheduling in higher problem,” International Journal of Latest Research in Science and educations,” International Journal of Information Technology and Technology, vol. 1 no. 2, pp 98 – 101, 2012. Business Management, vol. 32 no. 1, pp. 29-34, 2014. [12] M. Tabassum, and K. Mathew, “A genetic algorithm analysis towards [5] P. Punnakitikashem, J. M. Rosenberger, D. B. Behan, R. L. Baker, optimization solutions,” International Journal of Digital Information and K. Goss, “An optimization-based prototype for nurse and Wireless Communications, vol. 4 no. 1, pp. 124-142, 2014. assignment,” Proc. 7th Asian Pacific industrial engineering and management systems conference, 2006, pp. 17- 20. [13] O. Al Jadaan, L. Rajamani, and C. R. Rao, “Improved selection operator for GA,” Journal of Theoretical & Applied Information [6] K. Ellingsen, and M. Penaloza, “A genetic algorithm approach for Technology,” vol. 4 no. 4, pp. 269-277, 2008. finding a good course schedule,” South Dakota School of Mines and technology 2003, unpublished. [14] W.-J Shyr, “Parameters determination for optimum design by evolutionary algorithm,” INTECH Open Access Publisher, 2010. [7] I. Sbiety, M. Dbouk, and H. Kobeissi, “Combining the analytical hierachy process and the genetic algorithm to solve the timetable problem,” International Journal of Software Engineering and Applications (IJSEA) vol. 5 no. 4, pp. 39-50, 2014. 61