DonNTU   Masters' portal

Bezyglyi Maksim

Faculty of Computer Science and Technology

Department of automated control systems

Speciality Information Control Systems and Technologies

Preparation and optimization of timetables in a higher education instituti

Scientific adviser: Supervisor: Ph.D. Associate Professor, Department of automated control systems Sekirin Alexander

Resume Abstract

CONTENT

• INTRODUCTION
• 1. ACTUALITY
• 2. PURPOSES AND PROBLEMS OF WORK
• 3. SCIENTIFIC NOVELTY AND PRACTICAL VALUE
• 4. METHODS OF THE SOLUTION OF PROBLEMS OF DRAWING UP TIMETABLE
• 5. MATHEMATICAL DEFINITION OF PROBLEM
• 6. ESTIMATED RESUL
• 7. CONCLUSIONS
• BIBLIOGRAPHY

INTRODUCTION

One of the most important problems of the qualitative organization of educational process in an institution of higher education is the problem of formation of the qualitative educational timetable. This task is the main in activity of dispatching service in the institution of higher education. Qualitatively made timetable need to provide even workload of student's groups and the teachers, it influences on comfort of training of students, creative return of teachers and efficiency of use of resources of classroom fund and laboratories [1].

The timetable must consider the bigger number of restrictions of various type that is connected, for example, with introduction of a module - rating system of education. The timetable must optimize of academic, psychological and physical load of students.

In particular, it is expressed in requirement to consider the existing sanitary and epidemiology rules and norms (SANPIN), division of student's groups into subgroups, presence of part-time teachers and many other things. Now a question of quality of educational services and requirements of economies of resources in practice not only drawing up some "draft" version of the timetable, but also receiving optimum or the near optimal of timetable [2].

1. ACTUALITY

Drawing up the effective timetable of classes is one of the most important problems of management of educational process. In connection with it the problem of automation of drawing up timetable in educational systems of mass training remains to one of actual problems of the organization of educational process. Really, from that, how "successfully" made the timetable depends:

1. quality of educating;
2. economic efficiency of training;
3. comfort of study of students and work teachers [3].
4. and also allows to carry out educational process without failures and to avoid need of updating of the timetable after the beginning of an educational semester.

Automation of procedure of drawing up classes allows:

1. to consider all requirements imposed to the timetable;
2. to define criterias for an assessment of efficiency and optimization of the timetable;
3. to reduce expenditure of time on drawing up the timetable that it is especially important to receive if necessary quickly timetables after change of external conditions;
4. allow to consider wishes of teachers, concerning time and will provide a possibility of a part-time job.

Tasks of the theory of timetable don't have only important theoretical value as belonging to the class of NP-complete problem, but also have got wide practical circulation. It is necessary to make full search of all possible options for finding of the optimal solution of tasks of such class that it isn't always possible to make in a type of limitation of resources. Creation of the optimum plan of distribution of classes can take too much time and resources. There is a need for the methods which are characterized by a combination of polynomial dependence of time of the account on dimension of a task and accuracy close to optimum [4].

Evolutionary and genetic algorithms (EGA) which are the most flexible and effective of all known approximate algorithms [1].

For the solution of problems of drawing up the timetable the heuristic algorithm which at any entrance values would work equally effectively is still not found. For increase of efficiency algorithms are exposed to modification taking into account specifics of drawing up the timetable and requirements of an institution. As a method of drawing up it is offered to use the modified genetic algorithm which realizes all advantages of classical algorithm and it is save from some of his shortcomings.

The work [5] has the conclusion about a need of further researches, design of the new modified structure of genetic algorithm allowing to increase quality of the received decisions and approbation of the developed algorithm at the practical solution of a problem of drawing up the timetable of institution of higher education.

Thus, research of a possibility of the solution of tasks of the theory of timetables by means of approximate methods of class GA and automation of drawing up timetable of lessons in institution of higher education is an actual task.

2. PURPOSES AND PROBLEMS OF WORK

Main objective of work is drawing up algorithm capable to generate effective timetable of classes in the conditions of DonNTU.

For achievement of a goal it is necessary to solve the following problems:

1. definition of intellectual methods, for drawing up the correct timetable;
2. modification of algorithm for increase of its efficiency;
3. check of efficiency of the received algorithm;
4. studying of influence of various parameters of algorithm on speed and result of the solution of a task;
5. determination of effective values of parameters for the solution of a task;
6. design of the database for unification of algorithm.

3. SCIENTIFIC NOVELTY AND PRACTICAL VALUE

Creation of the modified genetic algorithm, adapted for the solution of a specialized problem of receiving relatives to optimum timetables of classes in an institution of higher education is offered.

Drawing up objective function, with an opportunity to consider both requirements, and the preference shown to the timetable.

4. METHODS OF THE SOLUTION OF PROBLEMS OF DRAWING UP TIMETABLE [6]

1. Methods of integer programming

The problem of integer programming is reduced to allocation of variables which value needs to be found, drawing up mathematical model of a task in the form of restrictions which describe a task and impose certain restrictions for required variables, and drawing up criterion function.

Application of algorithm:

1. setting off of variables;
2. drawing up mathematical model (setting off of restrictions for variables);
3. drawing up criterion function;
4. finding of a maximum (minimum) of criterion function by means of mathematical methods.

Main shortcomings:

1. exponential the extension of time on a search of the best (acceptable) decision with growth of dimension of a solvable task;
2. lack of a guarantee of obtaining the acceptable decision;
3. on the strength of the big dimension of mathematical model it is difficult to estimate influence of different factors on the process of the solution of a task and his result;
4. complexity of the accounting of preferences.

2. Method of the theory of graphs

In this case the unoriented graph, in whom each top represents the occupation planned by the curriculum. If between any two tops are possible the conflicts, then they unite a rib. It is equivalent to a ban of simultaneous conducting classes. Then the task is reduced to coloring of the graph in call-off quantity of colors. Application of algorithm:

1. allocation of a set of classes in the curriculum;
2. representation of each lesson in the form of the top of the graph;
3. connection of tops of the graph of ribs in case of impossibility of simultaneous conducting lessons;
4. the solution of a problem of a coloring of the graph in call-off quantity of colors.

Shortcomings:

1. small efficiency at application of exact methods for a coloring of graphs of big dimension;
2. lack of a possibility of the accounting of preferences.

Advantages:

1. simple for the understanding mathematical model;
2. application of the graph together with heuristic methods can give good results.

3. Agent approach

Essence of application of agent approach for the solution of any task following - splitting a task into some smaller tasks. For the solution of each of which is allocated the agent. The agent's purpose – to find the solution of the task it that it reconcile with decisions of other agents. Agents obtain coordination with each other by an exchange of information messages.

Application of algorithm:

1. splitting a global task into smaller subtasks;
2. for each type of a subtask is realized the special type of agents;
3. drawing up model of space in which agents act in the form of rules and axioms; 4. drawing up ontology of concepts;
4. replacement of all users of the timetable with agents, the purpose of everyone to find optimum the timetable.

Shortcomings:

1. there is no guarantee of obtaining the acceptable solution of a problem of creation of timetable of the lessons
2. almost impossible is an estimation of influence of values of parameters for internal logic of each of agents on result of the solution of a task.

Advantages:

1. a possibility of flexible control of individual preferences at the expense of a possibility of realization of own logic for each of agents;
2. possibility of dynamic change of preferences.

4. Method of an ant colony

It is based on ability of ants to find the shortest ways to food by means of allocation of a pheromone.

Application of algorithm:

1. to present a task in the form of the weighed graph;
2. to define value of a trace of a pheromone;
3. to define heuristics of behavior of an ant at creation of the decision;
4. to realize local search.

Shortcomings:

1. convergence of algorithm is guaranteed, but time of convergence isn't defined;
2. high interactive of algorithm;
3. the result of work of a method strongly depends from initial parameters of search which are selected experimentally;
4. theoretical an analysis of meaning of initial parameters it is complicated, researches are more experimental.

Advantages:

1. it can be used in dynamic applications;
2. uses memory of all colony that is reached due to modeling of allocation of pheromones;
3. convergence to the optimal solution is guaranteed.

5. Method of the imitation annealing

The algorithm of imitation of annealing is based on imitation of physical process which comes at crystallization of substance from a liquid state in firm.

Application of algorithm:

1. to make the correct timetable and to set high value of temperature of T = T0;
2. to change the timetable of Z = to Z';
3. to calculate objective function for the changed timetable Δf = f (Z') – f(Z);
4. to replace the previous timetable received if it is better previous (Δf ≤ 0) if isn't, then probability of replacement of p = e–Δf/T;
5. to lower temperature;
6. go to step 2 until some condition is met.

Shortcomings:

1. it is a little effective for drawing up timetables in modern systems of mass education in a type of big dimension of a task;
2. for obtaining the effective decision it is necessary to apply Boltzmann's scheme, or Cauchy that leads to considerable expenses of computing capacities.

6. Genetic algorithm

Genetic algorithms are based on use of mechanisms of the theory of natural evolution.

Application of algorithm:

1. to generate in a random way population of size P;
2. to calculate objective function;
3. to execute operation of a reproduction;
4. to execute operation of a crossing (Figure 1);
5. to execute operation of a mutation;
6. to execute operation of a reduction;
7. will check criterion if it isn't reached to pass to a step 2, otherwise to finish work.

Shortcomings:

1. quality of the decision considerably depends from the size and a variety of initial population;
2. the decisions received in a result of several experiments for the same task can slightly differ;
3. the weak accounting of specifics of a problem of drawing up the timetable of classes at the organization of her decision.

Advantages:

1. the algorithm works with codes in which is presented the set of the parameters directly depending on arguments of criterion function;
2. in the course of search the algorithm uses several points of search space, but doesn't pass from a point to a point;
3. in the course of work the algorithm can not use any additional information about a task, but if such is available it is possible to accelerate convergence of algorithm;
4. the genetic algorithm uses as probabilistic rules for generation of new points of search, and determined for transition from one points to others;
5. for problems of high dimension the speed of work of algorithm can be "regulated" the population sizes.
6. for the solution of problems of drawing up the timetable is still not found the heuristic algorithm which at any entrance values would work equally effectively.
7. for efficiency increase algorithms are exposed to modification taking into account specifics of drawing up the timetable and requirements of an institution. As a method of drawing up it is offered to use the modified genetic algorithm which realizes all advantages of classical algorithm and it is relieved of some of his shortcomings.

5. MATHEMATICAL DEFINITION OF PROBLEM

The timetable, in fact, represents the schedule of conducting classes which are given by teachers for concrete groups in a certain classroom in the designated time. From this it is possible to deduce that the timetable can be submitted in functions:

S (P,G,A,T,D,V),
where G - the set of the trained groups;
A - set of audiences;
D - set of disciplines;
P - set of teachers;
T - set of educational couples

V - Working curricula the three-dimensional matrix defining for each occupation what teachers it conduct and what groups are present at it.

If to simplify a task and not to consider curricula and disciplines, then the timetable can be presented in the form of the Cartesian product

S=G×P×A×T→{0,1}, where G set of the trained groups;
A – set of audiences;
P – set of teachers;
T – set of educational couples.

This expression is deciphered as follows if in certain time of T the teacher R at group G gives classes in classroom, and, then value of expression is equal 1, differently 0.

Objective function P is the sum of penalties for violations of preferences by drawing up the timetable.

where NW – the number of requirements;
W – the list of penal coefficients length by NW conforming to requirements;
N – the number of lessons in the timetable (quantity of genes in a chromosome);
Z – list of lessons length by N; z_i^r the list from Boolean length of NW values where to each value corresponds the requirement and penal coefficient from the list W.

In the majority of educational institutions the main restrictions to the timetable are:

1. lack of slips in the timetable of the teacher of groups and classrooms;
2. compliance of classrooms to requirements for conducting classes;
3. restriction of number of lessons per week for the teacher and group.

6. ESTIMATED RESULTS

As a result of performance of this work is supposed making a drawing up the modified genetic algorithm allowing to make effective timetable of classes in the conditions of institution of higher education, program realization of this algorithm and finding of effective parameters for reduction expenditure of time for search of the decision.

7. CONCLUSIONS

The analysis of the existing methods, models and algorithms allowing to make effective timetable of classes in institution of higher education revealed their merits and demerits.

For overcoming of the above shortcomings develop of the modified genetic algorithm allowing to make the correct timetable with a glance all restrictions. Criteria of efficiency of the timetable in the conditions of DonNTU are defined. The experimental evidence confirm efficiency of the made timetables, and also the parameters allowing to increase efficiency of algorithm.

On the basis of results of experimental evidence are formulated and made recommendations about drawing up effective timetables in the conditions of DonNTU.

BIBLIOGRAPHY

1. Budilovsky Dmitry Mikhailovich Optimization solutions scheduling problems based on evolutionary-genetic model of distribution of tasks // System analysis, management and information processing (on branches) // Rostov-on- Don 2007;
2. Lopateeva Olga Automated System training schedule in a higher education institution on the basis of heuristic algorithms // System analysis, management and information processing (on branches) // The thesis is Krasnoyarsk 2006 ;
3. Nizamova Guzel Fanisovna Mathematical and software for scheduling training sessions based on the aggregation of genetic algorithms //abstract // Ufa 2006;
4. Sekirin AI software package for modeling, analysis and optimization of automated technological complexes machining // Proceedings of Donetsk National Technical University. Series: "Computers and Automation". Issue 90 - Donetsk: Donetsk National Technical University, 2005;
5. Konkova IS Genetic algorithms in solving the problem of co-representation zanyty schedules in college. // Problems of Informatics in education, management, economics and engineering: Coll. Articles XII Intern. Scientific and Technical. Conf. - Penza: ETC, 2012. - S. 26 29;
6. MA Bezugly, AI Sekirin, Assoc. cafes. ACS. Methods to improve the efficiency of scheduling in a school. // International scientific-technical conference of students, graduate students and young scientists Computer and Software Engineering - 2015 // Donetsk National Technical University, 2015
.