Next Article in Journal
A Review of Agent-Based Programming for Multi-Agent Systems
Previous Article in Journal
Acknowledgment to Reviewers of Computers in 2020
Open AccessArticle

A Compromise Programming for Multi-Objective Task Assignment Problem

1
Center for Research in Data Science, Department of Computer and Information Sciences, Universiti Teknologi PETRONAS, Tronoh 32610, Malaysia
2
Information and Communication Technology Department, FPT University, Hanoi 100000, Vietnam
*
Author to whom correspondence should be addressed.
Received: 14 December 2020 / Revised: 19 January 2021 / Accepted: 20 January 2021 / Published: 25 January 2021

Abstract

The problem of scheduling is an area that has attracted a lot of attention from researchers for many years. Its goal is to optimize resources in the system. The lecturer’s assigning task is an example of the timetabling problem, a class of scheduling. This study introduces a mathematical model to assign constrained tasks (the time and required skills) to university lecturers. Our model is capable of generating a calendar that maximizes faculty expectations. The formulated problem is in the form of a multi-objective problem that requires the trade-off between two or more conflicting objectives to indicate the optimal solution. We use the compromise programming approach to the multi-objective problem to solve this. We then proposed the new version of the Genetic Algorithm to solve the introduced model. Finally, we tested the model and algorithm with real scheduling data, including 139 sections of 17 subjects to 27 lecturers in 10 timeslots. Finally, a web application supports the decision-maker to visualize and manipulate the obtained results.
Keywords: timetabling; task assignment; MOP; combinatory optimization; compromise programming; genetic algorithm timetabling; task assignment; MOP; combinatory optimization; compromise programming; genetic algorithm

1. Introduction

1.1. Background

In many fields such as production management, engineering…etc., scheduling plays a key role in productivity enhancement. The scheduling process is responsible for assigning machines and resources to tasks such that all tasks are executed while meeting business constraints. In the training institutions, the scheduling problems are mostly presented in the form of timetabling problems. The university timetabling problem’s goal is to find a method to allocate the predefined resources that minimize the cost where all constraints within the problem must be satisfied. The resources here consist of classes (groups of students with the same schedule), a subject that requires one or more specific skills and knowledge, time slots that determine when a particular class and subject are attached. The university usually performs a scheduling task before a semester begins [1,2,3,4,5]. The teaching assignment problem, in essence, is a branch of the timetabling problem. The scheduler must assign courses to trainers to satisfy the professional constraints and working time [6]. A lecturer can teach only the courses that they are qualified in, and at their available timeslots.
This research was conducted on a practical case study at FPT University in Vietnam. Currently, the university’s scheduling process is a manual process. In the situation, the student can register for their studies very soon before the department head has enough resources to determine the final schedule (of course, some classes could be canceled due to lack of resources later). The training department creates groups of students who would like to study the same subject based on the registrations and select the time slots. However, the department heads still need to assign their lecturer to teach these classes later. The reason for this is that we are student-centered. Other resources revolve around students to support them. In short words, the lecturers’ timetables are considered last. The project aims to provide an automated task assignment tool to replace the manual process of matching lecturers to their courses, as shown in Figure 1. The system assigns these courses to the lecturers based on their skills and expectations (more detail in Section 2).

1.2. Related Work

There have been many studies on the problem of university scheduling. Many of them have used an integer programming (IP) model to formulate the problem. For example, Andrade et al. have built a Non-Linear Binary Integer Programming mathematical model to develop the school timetabling problem, which is used to assign teaching tasks to teachers at a defined time frame [1]. Gianpaolo et al. proposed an Integer Programming formulation of selecting the training offer and the related timetabling for high-school remedial courses subject to constraints on budget and business operations [3]. Daskalaki et al. presented a binary integer programming model of the university timetabling problem, which tries to minimize the linear cost function [7]. Feng et al. developed a mixed-integer linear program for the university timetabling problem. The original problem converted to the three-dimensional container packing problem. They consider day, period, and room as the three dimensions of one container and the lectures as different sized items then assign them into the container [8].
Several researchers proposed models focused on assignments for rooms and time slots to achieve workable schedules while optimizing the lecturer’s interests. For example, Nouri and Driss [9,10] use the multi-agent approach, where the agents represent teachers of different levels and seek to assign their lectures according to their interests. Higher-ranking teachers are given priority in meeting their interests. Malik et al. built a model for mapping the task to the lecturer that maximizes their preference on the time-slot [11]. There are many different views about the compact schedule. The goal is to avoid idle time on the teacher’s plan and minimize working days [12,13].
The task assignment problems exist in many different forms. While some of them, like the classical problem, have polynomial-time solutions [14], others are NP-hard combination optimization problems [15] that require approximation approaches. A metaheuristic is widely known [16]. In [17], Lewis classifies several metaheuristic-based techniques into three classes for University Timetabling problems in their survey. Muthuraman and Venkatesan also conducted a survey of meta-heuristic algorithms for solving combinatorial optimization problems [18]. They reviewed several algorithms, such as ant colony optimization, evolutionary computation, particle swarm optimization, etc. Many researchers used genetic algorithms, an evolutionary algorithm to solve scheduling problems, and task assignment problems [19,20,21]. Genetic Algorithm generates high-quality solutions to optimization and search problems. A particular researcher can have different designs of the Genetic Algorithm to solve specific problems. Feng et al. combine genetic algorithms and search strategies to create offspring in populations based on information collected from the best individuals of previous generations and with a local search that improves the efficacy of the proposed Genetic Algorithm [8]. Yang develops an efficient hybrid genetic algorithm based on algorithms for the converted problem [22]. In [23], Corne suggested some of timetabling constraints including: unary constraints, binary constraints, capacity constraints, event spread constraints, agent constraints.
The common of the above studies is that they basically have the right target orientation to handle timetabling. However, the proposed model is too simple. It does not cover enough the achievements that complex business required. University lecturers are experts, enabling them to perform their jobs as important as cost optimization. The preferences of the trainer have not been properly considered in the resource optimization process. The use of metaheuristic algorithm to solve the combinatorial optimization problem is a reasonable direction. This study introduces a multi-objective optimization problem that used binary integer decision variables and a version of the Genetic Algorithm to solve the task assignment problem mentioned in Section 1.1.

1.3. Contribution

In this study, we present an approach to construct a task assignment support system for the university—the research output, including an optimization model, algorithm, and software application for actual use. The application plays a stage in the automatic scheduling solution at FPT University. It is a new variant of the teaching task assignment problem. The related research to the scheduling and task assignment may benefit from our study. Our mission is to arrange the teaching tasks for available human resources. We built a multi-objectives model that accesses each individual’s level of interest assigned to the job, providing a binding compliance solution. Our proposed model covers more business requirements than previous works since the many aspects of lecturer preferences are considered. The optimization model of the problem is described in Section 2.
There are many ways to solve the proposed optimization model. We choose compromising programming to transform the multi-objective problem into a single-objective problem. Each MOP approach has its advantages and disadvantages and is suitable for different decision-makers groups. Still, compromise programming works extremely better if no preference is indicated (it is assumed that the people are treated equally). We have implemented a Genetic Algorithm that solves both optimal models of a target mentioned above—the detail of the implementation is described in Section 3. In the following sections of this paper, we present our experiments using the scheduling data of Computer Fundamentals at FPT University. A review of the algorithm is also discussed in Section 4. The remaining are discussion and conclusion.

2. Mathematical Problem

2.1. Multi-Objective Task Assignment Problem

In this research, we also define our timetable problem in the form of IP as follows:
  • Let G is the number of lecturers.
  • Denote S is the number of subjects.
  • T is the number of available time slots, in our case, T = 10 as described in Table 1.
  • H is the number of section, a section represents a particular class studies a specific subject at a timeslot.
  • c h ,   s h ,   t h are class, subject, and time slot of section h -th respectively.
  • D g is a number of classes that lecturer g -th prefers to teach.
  • M g is a minimum number of classes that the lecturer g -th has to teach.
  • a s , g 0 as integer for every s = 1 S ,   g = 1 G represent the rating of the lecturer g -th to teach subject s -th. The value 0 indicates that the lecturer does not want to teach the subject. Other values respectively mean “like a little” to “like very much”.
  • b t , g 0 as integer for every t = 1 T ,   g = 1 G denote the rating of the lecturer g -th to teach at time slot t -th. The value 0 indicates that the lecturer does not want to teach at the time slot. Other values respectively mean “like a little” to “like very much.”
  • x h , g is the decision variable for every h = 1 H ,   g = 1 G . x h ,   g = 1 if the lecturer g -th is assigned to section h -th, x h , g = 0 otherwise.
We define several constraints to the problem as follows:
  • All section must be assigned lecturer and at most one lecturer is assigned to a section.
    g = 1 G x h , g = 1       s s = 1 H
  • A particular lecturer does not teach the subject that he/she does not have skill.
    a s h , g x h , g       h = 1 H , g = 1 G
  • A particular lecturer does not teach at the time-slot that he/she is not available.
    b t h ,   g x h , g       h = 1 H , g = 1 G
  • All lecturers have to satisfy the quota for the number of sections they have to teach.
    h = 1 H x h , g M g       g = 1 G
In this research, we have defined some objectives functions that maximize the lecturer’s preference level on time-slots, subjects, and the number of classes that the lecturer expects to teach. The objective functions described as follows:
  • Maximize the expectations of the lecturers on the subject they want to teach.
    max { h = 1 H x h , g a s h , g }       g = 1 G
  • Maximize the expectations of the lecturers on the time slots they want to teach.
    max { h = 1 H x h , g b t h , g }       g = 1 G
  • Minimize the errors on the number of classes that the lecturers want to teach.
    min { | h = 1 H x h , g D g | }       g = 1 G
Minimize the number of parts of the day, which lecturers must work (morning, afternoon every day). The lecturer would register three classes, even if he expressed his interest in all of the time-slots. It is better to assign him/her to work in the slot-times (E1, E2, E3) instead of (E1, E4, M1):
max { p o d ( { x h , g |   h = 1 H } ) }       g = 1 G
where p o d is a fuzzy logic membership function that returns the rating for the number of parts of the day, which lecturers have to work, the detailed implementation can be different in different situations. We show our implementation in the part of the experiment to suit the context of FPT University.
The proposed model is in the form of a multi-objective programming problem (MOP) [24]. Since there are often many Pareto optimization solutions for MOP problems, solving such a problem is not as simple as a typical single goal optimization problem. In the following sections, we present an approach to transform the optimal problem into a more suitable form to find the optimal solution in the decision space.

2.2. Compromise Programming for MOP

Our proposed scheduling problem becomes MOP. There are two main approaches to solving the MOP problem: preference method and non-preference method, as mentioned in Hwang’s survey [24]. The most useful solution is found using different philosophies that depending on the subjective preferences of the decision-makers. In the decision-making process, decision-makers can place interest in each criterion according to his/her subjective preferences. Here, the decision-maker should be an expert in the domain. It is challenging to find the desired weights for different objectives. This section of this paper discusses the compromise programming approach that requires no pre-defined decision-maker preferences.
The problem of 4* G objective functions is complicated for decision-makers to define the weights corresponding to each lecturer. There are many proposed methods to solve multi-objective problems. Zeleny [25] introduced the ideal solution defined as the best-compromise solution that is the nearest to perfection. Ngo et al. [26,27,28] applied compromise programming to solve the problem of the binary objective in team selection, where they introduced the idea point E and try to find the solution that has minimum distance to E. Mahmudova used a variant of compromise programming called TOPSIS to identify the criteria and alternatives for software. They chose an alternate variant that has to be at the shortest Euclidean distance from the positive ideal solution and the farthest Euclidean distance from the negative ideal solution. The value of best and worst alternatives to software efficiency was found using the estimates of professional programmers [29]. Xu et al. determined the best compromise solution using a linear fuzzy membership function that represents the degree of achievement of an objective function as a value between 0 and 1. The best compromise solution is the one that archived the highest value of the normalized membership function μ k calculated at the k -th solution [30]. Wei and Tian used a fuzzy statistic algorithm to select the best compromise solutions after obtaining Pareto-optimal solutions [31].
When the decision-maker stands in the view of lecturers, they declare their preferences on subjects and time-slots. It is hard to find the solution to archive the best, but we can define the best schedule they expect. The only goal left is to find a solution that is closest to this predefined point. The question we may ask decision-maker and predictable answer for them is as follows:
  • How much faculty satisfaction on preferred time-slot and skill is good? Ideally, what they receive should be what they expect.
The decision-maker mostly provides this pair of the above question and answer for the time-slot, skill, number of courses, and part of the days they have to work. The objective function is now expressed as follow:
  • Denote E     G × ( T + 2 ) = { E 1 , E 2 , , E G }   is the matrix of idea timetable.
Where E g = { E g , 1 , E g , 2 , , E g , T , E g , T + 1 , E g , T + 2 }   is the vector of expected timetable for lecturer g -th, such that
E g , j = { max h = 1 H t h = j   ( a s h , g b j , g )           i f   j T                       n o r m ( D g )                             i f   j = T + 1                                                               o t h e r w i s e                      
The n o r m denotes the normalization function, is max rating for the number of parts of the days that a lecturer has to work.
  • Let F is the matrix of the solution. F     G × ( T + 2 ) = { F 1 , F 2 , , F G } where F g = { F g , 1 , F g , 2 , , F g , T , F g , T + 1 , F g , T + 2 } is the vector of final timetable for lecturer g -th, such that:
    F g , j = { h = 1 t h = j H x h , g a s h , g b j , g   i f   j T               n o r m ( h = 1 H x h , g )   i f   j = T + 1                   p o d ( { x h , g |   h = 1 H } )   o t h e r w i s e                        
  • Q is the matrix of the worse possible solution. Q     G × ( T + 1 ) = { Q 1 , Q 2 , , Q G } where Q g = { Q g , 1 , Q g , 2 , , Q g , T , Q g , T + 1 ,   Q g , T + 2 } is the vector of the worse timetable for lecturer g -th, such that:
    Q g , j = { { 0   i f   max s s = 1 S S t m s s = j   ( a s b s s , g b j , g ) 2 > m a x _ r a t i n g   m a x _ r a t i n g   O t h e r w i s e                                                   i f   j T { 0   i f   D g 2 > T     T 2   O t h e r w i s e                                             i f   j = T + 1                 0   o t h e r w i s e                                                                                        
The original multi-objective functions (O1), (O2), (O3), and (O4) are rewritten in the form of compromise problem (CP):
m a x i m i z e ( o b j ) = ( 1   d i s t a n c e ( [ E 1 , E 2 , , E G ] , [ F 1 , F 2 , , F G ] ) d i s t a n c e ( [ E 1 , E 2 , , E G ] , [ Q 1 , Q 2 , , Q G ] ) = 1 i = 1 G j = 1 T + 1 ( E i , j F i , j ) 2 i = 1 G j = 1 T + 1 ( E i , j Q i , j ) 2 )

3. Proposed Algorithm

3.1. Introduction to Genetic Algorithm

The Genetic Algorithm [32,33] is a population-based metaheuristic method extensively used in scheduling problems. It searches a solution space for the optimal solution to a problem. This search is done in a fashion that mimics the operation of evolution. In essence, a “population” of possible solutions formed, and new solutions are created by “breeding” the best individual from the population’s members to build a new generation. When the algorithm converged after several generations, the best solution returned. Genetic algorithms are particularly useful for problems where it is extremely difficult or impossible to get an exact answer or severe problems where a correct solution may not be required. They offer an exciting alternative to the typical algorithmic solution methods and are highly customizable. This notion can apply to a search problem. We consider a set of solutions for a challenge and select the set of best ones out of them. There are five phases considered in a genetic algorithm. This study introduces a version of the Genetic Algorithm to solve the MOP model Compromise Programming approach with a new added phase called “repair” to correct the errors. The flow of the proposed scheme is displayed in Figure 2.

3.2. Genetic Algorithm Scheme

3.2.1. Genetic Representation

Chromosome is represented as a matrix of G rows and T columns, rows i -th represent the section assignment for lecturer i -th. Cell ( g , t ) contains section lecturer g -th assigned to time-slot t -th, or 0 if lecturer g -th is not assigned to any section at the time-slot t -th.

3.2.2. Fitness Function

The fitness function contains two components: the penalty function and the objective function. While the objective function focuses on optimizing the lecturer’s satisfaction, the penalty function deals with constraints. We separate constraints into two groups, group 1st includes constraint (H4) handled by penalty function and group 2nd includes the remaining constraints (H1), (H2), (H3) handled by repair mechanism described in Section 3.2.4. So, we have the fitness function:
f = w p e n p e n +   w o b j o b j
where p e n ,   o b j ,   w p e n ,   w o b j denote penalty function, objective function, penalty function weight, and objective function weight respectively. We normalize the penalty function, objective function, and weights to 0–1 range. So we have the constraints: 0 w p e n , w o b j 1 , and w p e n + w o b j = 1 . Let V be the number of lecturer violate constraint ( H 4 ) , the penalty function is normalized as follows:
p e n = 1 1 + V

3.2.3. Algorithm Operations

Denote:
  • U represents the size of the population.
  • P e = { p i e |   i = 1 U } as the population at generation e -th.
  • p i e as the individual i -th of the population at generation e -th, represented as chromosome matrix described in Section 3.2.1. p i e n , m denotes the value of the cell at row n -th and column m -th.
  • t as the set of sections that learn at time-slot t -th.
  • φ as the tournament size for selection.
  • Β as the mutation rate
Step 1: Generate the initial population: Columns k-th of an individual p i e contain k and exactly G | k | number 0 . So, for each column k k = 1 T , fill k and G | k | number 0 to that column, and shuffle its element to ensure the randomness of the initialized population. After filling all columns to chromosome matrix, apply repair operator to ensure the created chromosome respects constraints ( H 1 ) ,   ( H 2 ) , and ( H 3 ) .
Step 2: Selection: we implemented the selection process based on Tournament Selection [34]. Randomly select φ individuals from P e and perform a tournament that return the best individuals based on fitness value among them.
Step 3: Crossover: p f a t h e r e and p m o t h e r e are the parents to crossover. The set of numbers in each column of p f a t h e r e and p m o t h e r e is permutation of each other, so we can choose any ordered crossover method to apply. Partially mapped crossover (PMX) [35] is one of the most effective crossover techniques for ordered list, so it is chosen in this study.
Step 4: Mutation: For each individual p i e , have rate B to swap only once for any two elements in any column. Similar to generating initial population process, the created chromosome after performing crossover and mutation must be applied to repair operator to ensure there are no invalid results during the processing.

3.2.4. Repair Process

Input a chromosome matrix p which may violate constraints ( H 1 ) ,   ( H 2 ) , and ( H 3 ) , genetic repair operator rearrange elements in p so that new chromosome p satisfies all these constraints. Moreover, p should retain as many p ′s genes as possible. The purpose we combine constraints ( H 1 ) ,   ( H 2 ) ,   ( H 3 ) into one group is because it is very easy to convert them into the maximum matching problem in bipartite graph. In this study, we use the Hopcroft–Karp algorithm [36], a polynomial algorithm to find the maximum matching. The repair process is performed in three steps as follows:
Step 1: Build a graph = ( V ,   E ) , with vertex set V = X Y , X represents vertex set of G × T items for each lecturer in each timeslot, Y represents vertex set of H items represent for sections. For each vertex 𝓉 X ( 𝓉 is the vertex represents for lecturer g -th at timeslot t -th), h Y ( h is the vertex represents for section h t h ), we add an edge from 𝓉 to h if and only if t = t h , a s h , g > 0 and b t , g > 0 .
Step 2: For each lecturer g g = 1 G at each timeslot t t = 1 T , pair the vertex u X ( u is the vertex represents for lecturer g -th at timeslot t -th) to vertex v Y ( v is the vertex represents for section p g , t   t h ) if p g , t > 0 and the pairing does not violate any constraints in ( H 1 ) ,   ( H 2 ) ,   ( H 3 ) . This step aims to retain the good genes from p .
Step 3: Apply the Hopcroft–Karp algorithm to graph built in step 1 with pre matching in step 2, we get the final matching which represents the repaired chromosome p .

4. Experiment and Result

To evaluate the proposed model and algorithm, we use the data collected in the spring semester of 2020 of the Computing Fundamental department at FPT University. A total of H = 139 sections of S = 17 subjects were assigned to G = 27 lecturers. The p o d function’s returned values were collected depending on the different business settings. Table 1 illustrates the definition of the timeslots at the institution. The merged cells described that two real-life slots are marked as the same time slot in the mathematical model.
We construct a fuzzy function p o d to fit the definition of the timeslots as the following algorithms. Our goal is to determine the number of sessions per day that the instructor must be in college and rate it. A good schedule that is matching the number of sections to teach with the number of part of days that lecturer has to present at the school gain 100% satisfaction (   points). Satisfaction is inversely proportional to the instructor’s waiting time. For some situations, when hiring qualified lecturers is not easy work, a compact schedule in the aspect of time may give more flexibility to the human resources organizing process.
Function: p o d
Input: { x h , g |   h = 1 H }
1: = 100
2: r = N u m P o d ( { x h , g |   h = 1 H } )
3: n = h = 1 H x h , g
4:If ( 1 n 3 ) and ( r = 1 ) Return 
5:If ( 1 n 3 ) and ( r = 2 ) Return  / 5
6:If ( 1 n 3 ) and ( r 3 ) Return  0
7:If ( 4 n 6 ) and ( r = 2 ) Return 
8:If ( 4 n 6 ) and ( r = 3 ) Return  / 5
9:If ( 4 n 6 ) and ( r = 4 ) Return  0
10:If ( 1 n 3 ) and ( r = 1 ) Return 
11:If ( 7 n 8 ) and ( r = 3 ) Return 
12:If ( 7 n 8 ) and ( r = 4 ) Return  / 2
13:If ( 9 n 10 ) Return 
The N u m P o d function defined as:
Function: N u m P o d
Input: { x h , g |   h = 1 H }
1: N u m   =   0
2:If ( t h { M 1 , M 2 , M 3 } x h , g 1 ) Then N u m   =   N u m   +   1
3:If ( t h { E 1 , E 2 , E 3 } x h , g 1 ) Then N u m   =   N u m   +   1
4:If ( t h { M 4 , M 5 } x h , g 1 ) Then N u m   =   N u m   +   1
5:If ( t h { E 4 , E 5 } x h , g 1 ) Then N u m   =   N u m   +   1
6:Return N u m
We built a webpage to collect lecturer preferences of the subjects, time-slots, and the number of time-slots they want to teach, as shown in Figure 3. The preferences gathering process needs to be done before starting the scheduler triggered. The lecturers use their personal accounts to make declarations with the system. In this experiment, we set the preferences received the values in the range of a s , g [ 0 5 ] and b t , g [ 0 5 ] .
The developed system described in this report was deployed on a computer configured as follows: Processor: Intel(R) Xeon(R) CPU X5650 @2.67 GHz (4 CPUs), ~2.3 GHz; Memory: 8096 MB RAM; all code implemented in java 8.
The designed genetic algorithm operated based on several parameters. They have a significant influence on the results of the algorithm. In this section, we describe how the values of this parameter are selected. To select the most suitable parameters for the genetic algorithm, we execute the algorithm multiple times. Observed effects on the corresponding MOP approaches are listed in Table 2.
The tested ranges of the importance of the parameters show good results. The small tournament size makes the crossover loses diversity. It negatively affects the algorithm results as well as the time of convergence. The tournament size = 7 seems to generate good results for the scalarizing approach, and tournament size > 9 increases the processing time even though it maintains an excellent fitness value. Population size > 100 gets worse for both fitness values and processing time. Based on the observed results, we selected the parameter set to run the algorithm according to Table 3.
To evaluate the proposed algorithm. We have run the algorithm multiple times with the same initial value. Figure 4 shows the fitness values over 13 executions. It shows that the result is nearing expected values (approximately 1) on tested data. The average time execution is around 33 s, as shown in Figure 5. In fact, the teaching assignment process accounts for an average of 1 working day of the head of department. In many cases when the number of sections is too large, it is even more time-consuming.
The fitness values change during each generation of the Genetic Algorithm is shown in Figure 6. After about the first 20 generations, the fitness value came very close to the convergence value. The proposed model allows faculty preferences for four aspects: skills, timeslots, number of classes, and working time. It considers more aspects of stakeholders’ needs than the simple “sum of favorites on the particular wish of lecturers” model introduced by previous research [17,21]. We use a non-preference approach for the multi-objective problem. Compromise programming gives a satisfactory answer in cases where there is not any priority assigned. The lecturer’s satisfaction degrees corresponding to the groups of objective functions were obtained by executing GA displayed in Figure 7. It observed that teachers who are registered to teach many subjects could guide in many different time frames and naturally prioritize various topics. Meanwhile, with the target function’s current scoring: 100%~5 stars of subjects * 5 stars of time slots, which leads to those who can teach few items or more constrained about time constraints may receive a less-satisfied schedule.
We illustrate the optimal solution in Figure 8. A directed graph is used to represent matching between instructor and sections. Each section node will only associate with one node trainer. In this situation, the arrow comes from a trainer node and points to the corresponding section node.
The Genetic Algorithm (and also other approximation algorithms) does not guarantee to find the global solution. The obtained solutions may be local optima. Since our model is different from previous models, it is not feasible to compare the proposed algorithm with the available settings. However, we can evaluate whether the algorithm works well in terms of a smaller search space. We extracted a data set from 5 lecturers, and 12 sections then found the global solution using exhaustive search. The proposed scheme’s comparison results with the implementation of the Brute Force algorithm are shown in Table 4, and the optimal solution is illustrated in Figure 9.
Decision-maker may have their customization on the provided schedule in this situation. To support them, modify the plan quickly, we design a web page to help drag and drop, as shown in Figure 10. The decision-maker can choose any course and assign it to another instructor by dropping the item in the corresponding line. The information systems part plays a vital role in compensating for the shortcomings of the proposed algorithm.

5. Conclusions

In this study, we have proposed a multi-objective optimization model for the assignment task. The proposed model satisfies the lecturers’ preferences regarding skills, time, and the number of jobs while ensuring related constraints. Our model was applied to the FPT University lecturers scheduling problem and defined a generic solution for multi-objective task assignment problems. We use compromise programming to turn the multi-objective problem into a single-objective problem. Although in the preferred approach, users can set different values for each weight of the target function. It is flexible, but in a multi-dimensional space, the visualization of the results corresponding to a parameter set is difficult. It leads decision-makers to explore parameter sets in an ample search space. On the other hand, a compromise model is a single-shot solution for decision-makers. It avoids them having to define preference information for the objectives. The model itself has found a way to the best. However, the low use of parameters reduces the ability to interact with the model of a decision-maker. The proposed scheme for genetic algorithm shows that it works effectively; the repair step has removed all binding violation solutions without affecting crossovers’ diversity. Shortly, we are looking to build an integrated model with lecturers and students’ scheduling simultaneously. Refining the parameters of the algorithm is also a job in our plan.

Author Contributions

Conceptualization, S.T.N., B.N.A. and J.J.; formal analysis, B.N.A.; funding acquisition, B.N.A.; investigation, S.T.N.; methodology, S.T.N.; resources, S.T.N. and B.N.A.; software, S.T.N. and B.N.A.; supervision, J.J. and I.A.A.; validation, J.J. and I.A.A.; writing—original draft, S.T.N. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by FPT University, grant number DHFPT/2020/12.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Andrade, P.R.L.; Steiner, M.T.A.; Góes, A.R.T. Optimization in timetabling in schools using a mathematical model, local search and Iterated Local Search procedures. Gestão Produção 2019, 26, e3421. [Google Scholar] [CrossRef]
  2. Lemos, A.; Melo, F.S.; Monteiro, P.T.; Lynce, I. Room usage optimization in timetabling: A case study at Universidade de Lisboa. Oper. Res. Perspect. 2018, 100092. [Google Scholar] [CrossRef]
  3. Ghiani, G.; Manni, E.; Romano, A. Training offer selection and course timetabling for remedial education. Comput. Ind. Eng. 2017, 111, 282–288. [Google Scholar] [CrossRef]
  4. Vermuyten, H.; Lemmens, S.; Marques, I.; Beliën, J. Developing compact course timetables with optimized student flows. Eur. J. Oper. Res. 2016, 251, 651–661. [Google Scholar] [CrossRef]
  5. Babaei, H.; Karimpour, J.; Hadidi, A. A survey of approaches for university course timetabling problem. Comput. Ind. Eng. 2015, 86, 43–59. [Google Scholar] [CrossRef]
  6. Pentico, D.W. Assignment problems: A golden anniversary survey. Eur. J. Oper. Res. 2007, 176, 774–793. [Google Scholar] [CrossRef]
  7. Daskalaki, S.; Birbas, T.; Housos, E. An integer programming formulation for a case study in university timetabling. Eur. J. Oper. Res. 2004, 153, 117–135. [Google Scholar] [CrossRef]
  8. Feng, X.; Lee, Y.; Moon, I. An integer program and a hybrid genetic algorithm for the university timetabling problem. Optim. Methods Softw. 2016, 32, 625–649. [Google Scholar] [CrossRef]
  9. Nouri, H.E.; Driss, O.B. MATP: A Multi-agent Model for the University Timetabling Problem. In Software Engineering Perspectives and Application in Intelligent Systems; Silhavy, R., Senkerik, R., Oplatkova, Z., Silhavy, P., Prokopova, Z., Eds.; Advances in Intelligent Systems and Computing; Springer: Cham, Switzerland, 2016; Volume 465. [Google Scholar] [CrossRef]
  10. Nouri, H.E.; Driss, O.B. Distributed model for university course timetabling problem. In Proceedings of the 2013 International Conference on Computer Applications Technology (ICCAT), Sousse, Tunisia, 20–22 January 2013. [Google Scholar] [CrossRef]
  11. Malik, B.B.; Nordin, S.Z. Mathematical model for timetabling problem in maximizing the preference level. In Proceeding of the 25th National Symposium on Mathematical Sciences (Sksm25): Mathematical Sciences as the Core of Intellectual Excellence, Pahang, Malaysia, 27–29 August 2017; AIP Conference Proceedings. p. 020037. [Google Scholar] [CrossRef]
  12. Santos, H.G.; Uchoa, E.; Ochi, L.S.; Maculan, N. Strong bounds with cut and column generation for class-teacher timetabling. Ann. Oper. Res. 2012, 194, 399–412. [Google Scholar] [CrossRef]
  13. Dorneles, Á.P.; de Araújo, O.C.B.; Buriol, L.S. A fix-and-optimize heuristic for the high school timetabling problem. Comput. Oper. Res. 2014, 52, 29–38. [Google Scholar] [CrossRef]
  14. Hmer, A.; Mouhoub, M. Teaching Assignment Problem Solver. Lect. Notes Comput. Sci. 2010, 298–307. [Google Scholar] [CrossRef]
  15. Kuhn, H.W. The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 1955, 2, 83–97. [Google Scholar] [CrossRef]
  16. Fisher, M.L.; Jaikumar, R.; Wassenhove, L.N.V. A multiplier adjustment method for the generalized assignment problem. Manag. Sci. 1986, 32, 1095–1103. [Google Scholar] [CrossRef]
  17. Lewis, R. A survey of metaheuristic-based techniques for University Timetabling problems. OR Spectr. 2007, 30, 167–190. [Google Scholar] [CrossRef]
  18. Muthuraman, S.; Venkatesan, V.P. A Comprehensive Study on Hybrid Meta-Heuristic Approaches Used for Solving Combinatorial Optimization Problems. In Proceedings of the 2017 World Congress on Computing and Communication Technologies (WCCCT), Tiruchirappalli, India, 2–4 February 2017. [Google Scholar]
  19. Sigl, B.; Golub, M.; Mornar, V. Solving timetable scheduling problem using genetic algorithms. In Proceedings of the 25th International Conference on Information Technology Interfaces (ITI 2003), Cavtat, Croatia, 19 June 2003; pp. 519–524. [Google Scholar]
  20. Savić, A.; Tošić, D.; Marić, M.; Kratica, J. Genetic algorithm approach for solving the task assignment problem. Serdica J. Comput. 2008, 2, 267–276. [Google Scholar]
  21. Sapru, V.; Reddy, K.; Sivaselvan, B. Time table scheduling using Genetic Algorithms employing guided mutation. In Proceedings of the 2010 IEEE International Conference on Computational Intelligence and Computing Research, Coimbatore, India, 28–29 December 2010; pp. 1–4. [Google Scholar]
  22. Yang, S.; Jat, S.N. Genetic algorithms with guided and local search strategies for university course timetabling. Syst. Man Cybern. Part C Appl. Rev. 2011, 41, 93–106. [Google Scholar] [CrossRef]
  23. Corne, D.; Ross, P.; Fang, H. Evolving timetables. In The Practical Handbook of Genetic Algorithms; Chambers, L.C., Ed.; CRC: Boca Raton, FL, USA, 1995; Volume 1, pp. 219–276. [Google Scholar]
  24. Hwang, C.-L.; Masud, A.S.M. Multiple Objective Decision Making, Methods and Applications: A State-of-the-Art Survey; Springer: Berlin/Heidelberg, Germany, 1979; ISBN 978-0-387-09111-2. [Google Scholar]
  25. Zeleny, M. Compromise Programming. In Multiple Criteria Decision Making; Cochrane, J.L., Zeleny, M., Eds.; University of South Carolina Press: Columbia, SC, USA, 1973; pp. 262–301. [Google Scholar]
  26. Son, N.T.; Thanh, L.V.; Duong, T.B.; Anh, B.N. A decision support tool for cross-functional team selection: Case study in ACM-ICPC team selection. In Proceedings of the 2018 International Conference on Information Management & Management Science (IMMS‘18); ACM: New York, NY, USA, 2018; pp. 133–138. [Google Scholar] [CrossRef]
  27. Son, N.T.; Thuy, T.T.; Anh, B.N.; van Dinh, T. DCA-Based Algorithm for Cross-Functional Team Selection. In Proceedings of the 2019 8th International Conference on Software and Computer Applications (ICSCA‘19); ACM: New York, NY, USA, 2019; pp. 125–129. [Google Scholar] [CrossRef]
  28. Ngo, T.S.; Bui, N.A.; Tran, T.T.; Le, P.C.; Bui, D.C.; Nguyen, T.D.; Phan, L.D.; Kieu, Q.T.; Nguyen, B.S.; Tran, S.N. Some Algorithms to Solve a Bi-Objectives Problem for Team Selection. Appl. Sci. 2020, 10, 2700. [Google Scholar] [CrossRef]
  29. Mahmudova, S. Application of the TOPSİS method to improve software efficiency and to optimize its management. Soft Comput. 2020, 24, 697–708. [Google Scholar] [CrossRef]
  30. Xu, X.; Hu, Z.; Su, Q.; Xiong, Z. Multiobjective Collective Decision Optimization Algorithm for Economic Emission Dispatch Problem. Complexity 2018, 2018, 1027193. [Google Scholar] [CrossRef]
  31. Wei, W.; Tian, Z.-Y. An improved multi-objective optimization method based on adaptive mutation particle swarm optimization and fuzzy statistics algorithm. J. Stat. Comput. Simul. 2017, 1–14. [Google Scholar] [CrossRef]
  32. Van Veldhuizen, D.A.; Lamont, G.B. Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art. Evol. Comput. 2000, 8, 125–147. [Google Scholar] [CrossRef] [PubMed]
  33. Thede, S.M. An Introduction to Genetic Algorithms. J. Comput. Sci. Coll. 2004, 20. [Google Scholar]
  34. Miller, B.; Goldberg, D. Genetic Algorithms, Tournament Selection, and the Effects of Noise. Complex Syst. 1995, 9, 193–212. [Google Scholar]
  35. Otman, A.; Jaafar, A. A comparative study of adaptive crossover operators for genetic algorithms to resolve the travelling salesman problem. Int. J. Comput. Appl. 2011, 31, 49–57. [Google Scholar]
  36. Hopcroft, J.E.; Karp, R.M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 1973, 2, 225–231. [Google Scholar] [CrossRef]
Figure 1. The teacher assignment problem.
Figure 1. The teacher assignment problem.
Computers 10 00015 g001
Figure 2. Basic workflow of the proposed Genetic Algorithm’s scheme.
Figure 2. Basic workflow of the proposed Genetic Algorithm’s scheme.
Computers 10 00015 g002
Figure 3. Webpage to collect the preferences of a particular lecturer on the subjects and time-slots.
Figure 3. Webpage to collect the preferences of a particular lecturer on the subjects and time-slots.
Computers 10 00015 g003
Figure 4. Fitness values of GA over several executions.
Figure 4. Fitness values of GA over several executions.
Computers 10 00015 g004
Figure 5. Execution time of GA over several executions.
Figure 5. Execution time of GA over several executions.
Computers 10 00015 g005
Figure 6. Fitness values changing over generations.
Figure 6. Fitness values changing over generations.
Computers 10 00015 g006
Figure 7. Satisfaction degrees of the lecturers. (A) Satisfaction degree on the assigned subjects. (B) Satisfaction degree on the assigned timeslots. (C) Satisfaction degree on the assigned number of classes. (D) The returned values of the part of the day function (pod).
Figure 7. Satisfaction degrees of the lecturers. (A) Satisfaction degree on the assigned subjects. (B) Satisfaction degree on the assigned timeslots. (C) Satisfaction degree on the assigned number of classes. (D) The returned values of the part of the day function (pod).
Computers 10 00015 g007
Figure 8. Obtained solution visualized by a directed graph.
Figure 8. Obtained solution visualized by a directed graph.
Computers 10 00015 g008
Figure 9. Global Solution obtained by Brute Force.
Figure 9. Global Solution obtained by Brute Force.
Computers 10 00015 g009
Figure 10. The webpage allows the decision-maker to customize the generated schedule.
Figure 10. The webpage allows the decision-maker to customize the generated schedule.
Computers 10 00015 g010
Table 1. The details of 10-time slots defined at the FPT University for a week.
Table 1. The details of 10-time slots defined at the FPT University for a week.
DoWMondayTuesdayWednesdayThursdayFridayPart of the Day
Time-Slot
1M1M4M1M4M1Morning
2M2M2M5M2
3M3M5M3M3
4E1E4E1E4E1After Noon
5E2E2E5E2
6E3E5E3E3
Table 2. The observation result of the algorithm for each set of parameters.
Table 2. The observation result of the algorithm for each set of parameters.
ParamValueObservation Results
mutation0.9–1Stable results, processing time increased slightly
0.5–0.8Stable results, processing time increased
0–0.5Stable results, stable time execution
tournament size2Results decreased slightly, stable time execution
3Stable results, processing time increased
5Stable results, stable time execution
7Stable results, processing time decreased
9Stable results, processing time decreased
population size100–150Stable results, processing time increased
151–200Stable results decreased, processing time increased
Table 3. Parameters to run the algorithm.
Table 3. Parameters to run the algorithm.
Parameter B U φ Stop after w o b j w p e n
Value0.41007300.30.7
Table 4. Comparison between Genetic Algorithm and Brute Force Algorithm.
Table 4. Comparison between Genetic Algorithm and Brute Force Algorithm.
AlgorithmFitness ValuesTime Execution (s)
Brute Force0.95919468
Genetic Algorithm0.959190.55
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Back to TopTop