Abstract

Introduction

Organization of educational process in higher education is a foundation of success. The basis of the educational process of learning is in making an "optimal" schedule of training sessions. Schedule of training sessions should meet increasing requirements of future professionals. There are quite a number of software systems for curriculum schedules. Automating of scheduling of training sessions began in the early 90s. Unfortunately, only a small part of the educational institutions of different levels actually use such schedules. The main problems remain: the high complexity of obtaining solutions, imperfect technology of schedules design, poor ergonomics procedures and high time costs [1].

1. The purpose of the study, expected results

task of automating scheduling is one of those tasks that has worried mathematicians and programmers for a very long time. Extensive development in this direction was carried out from the beginning of XX century.

With the development of computer hardware and computer calculations there are still a lot of problems in turning scheduling to fully automatic calculation mode. Not surprisingly, since the mid 90's a real boom in programs of automatic scheduling started. Such programs have been set, they have implemented a variety of algorithms, but they didn't solve the problem. The results of operations of these programs have following disadvantages:

1) long time of work. The user could start a program, go home, and it took a week to get the message about the impossibility of combining hours, although this curriculum manager was placed in the schedule grid, even with the stock.

2) Inconvenient interface and database loading

3) inconvenient schedules for both students and teachers.

4) extremely difficult to calculate when the subject involves dividing the group into subgroups.

The result is that some of the theories have been put forward. They stated that there is no solution, and therefore this problem can not be solved by algorithms and subsequent automation [1].

In developing classes of algorithms for automated scheduling it acute a problem of creating universal algorithms that take into account the specific circumstances of each particular task. Such algorithms shall be sufficiently "soft", i.e. without a significant changethat they could be included or excluded from the requirements of the system, requirements for the schedule. However, solving the problem with one single universal algorithm for currant moment is not possible. Algorithms to solve a wide class of problems, do not give the same level of performance to provide more specific, adapted to the specific conditions algorithms.

Systems for schedule formation are characterized by a strong dependence on the specification of educational institutions at the level of mathematical models and data representation, which makes the use of typical systems more difficult. System, which was created in one institution, usually without changes and improvements can not be effectively used in another. In addition, many of them were created a long time ago and they can not effectively solve the task [2].

The main purpose of this work is the analysis of the main methods of automated scheduling system. Analyzing the main methods of automated scheduling, we can choose the one which in the future will be used to build an automatic system of forming the first version of the schedule in the ASA "Dean" FKNT Donetsk National Technical University. It will be the result of the work.

2. Problem Statement

Formally task scheduling can be viewed as following: Given:

• Many teachers.

• Many groups.

• A set of audiences.

• A set of subjects.

• Curriculum.

two sets of requirements may also be put forward for the schedule:

• Hard or mandatory requirements:

o Some classes need bigger room (for example, streaming lecture).

o Some classes need the appropriate room with special equipment (eg, an auditorium with analog computing systems for practical training in subjects related to electronics).

• Soft Requirements:

o Students have no windows in schedule

o Teachers have no windows in schedule

o The minimum number of crossings between the groups of university buildings, if the campus is not in the same place (for example, the Donetsk National Technical University has three groups of buildings are sufficiently far from each other) .

o Lectures should be first during the day, practice sessions–should be last.

o Uniform load of students

o Library days for teachers

o Other conditions

As seen from the statement, to assess the quality of the schedule is possible only after a full compilation.

The problem itself is very heavy, and some scientists called it "the task without solutions." Taking a look at the figure 1, you can see how many pieces are in this difficult puzzle.

To solve the problem, we need to build a flexible and adaptable system based on new principles, with the use of modern computer technology. System should use as many criterias and specified requirements as it can, ie the person would do less manual work. These opportunities should also be carried out without changing the source code of the system to be used by users, non-programmers. To cover the most typical cases, it needs analysis, and the use of several standard algorithms that implement scheduling. It needs a decision support system that has the ability to customize, take to consideration all possible constraints and requirements.

This system should:

• be able to add and modify existing database

• be able to add and modify the UI

• provide an opportunity to connect additional self-developed algorithms, possibly with a call to some typical algorithms provided by the system.

All this would make it possible to define the requirements of each institution to meet its terms, and with the help of selecting and setting a suitable algorithm to obtain the required schedule.

3. Review of existing algorithms.

in scheduling theory we can allocate such group problem-solving methods:

• Exact methods (methods based on complete enumeration) These include linear programming, integer programming, Gomory algorithm, which assumes that all of the coefficients in terms of the objective function and are integers. If some jobs and resources combinatorial operations are connected and have combinatorial character of operations, such a method has certain features.

• Approximate methods.

They can be grouped as follows:

o local optimization techniques

o modification of the exact methods

o heuristics, take into account the specifics of tasks

o random search methods

o methods that combine local optimization with random search.

Note that many approximation algorithms allow us to solve discrete optimization problem in interactive mode. This makes it possible, depending on the allocation of resources (time, memory, computer, etc.), to consistently improve the solution obtained by changing some or all of the original data. A significant part of the approximate discrete optimization algorithms based on the use of numerical schemes known exact methods such as branch and bound, sequential analysis of options and others. One of the most developed approximate methods are local optimization methods, which finds locally optimal solutions.

Often these methods at certain stages of solving the problem of random search methods are used, as well as a variety of ways (heuristics) that enable to reduce the progress of options and take into consideration the specificity of the problem. It should be noted that the algorithms that combine various ideas in practice often the most effective. With these methods many difficult problems of classification of objects, placement, planning and design have been solved. The main advantage of these methods is simple implementation, the main drawback is that they can not adapt to the task. A much more flexible methods are those in which the probability depends on the outcomes of previous trials and changes from iteration to iteration. These are the methods of random search with learning.

In my work, I will examine the four basic algorithms that are used most often in automation scheduling: brute force, method of borders and branches, genetic method, heuristic methods

analyzing algorithms automate scheduling can draw the following conclusions:

• The existing scheduling methods can be divided into two groups: exhaustive search (exact methods) and methods of reducing the exhaustive search (approximate methods).

• Choice of algorithm directly depends on the task at hand. To schedule the task–the number and type of resources, tasks and constraints.

Thus we can understand that the successful implementation of the idea of automatic scheduling with the introduction of it in the ASA "Dean" of Donetsk National Technical University needs starting work with finding out exactly:

• curriculum.

• number of audiences.

• soft and hard limits.