Conference publications

Abstracts

XVI conference

Modelling of a problem of drawing up of schedules predfractal grafs

Kononova N.V.

The Stavropol institute of economy and management of a name O.V.Kaznacheeva (branch) GOU VPО «Pyatigorsk state technological university», Russia, Stavropol, Теl.: (8652)73-29-33, fax: (8652)38-68-11, E-mail: knv_fm@mail.ru

The problem of drawing up of schedules is one of the most widespread problems solved by each person almost daily. Therefore with development of computing technologies workings out of the automated systems of drawing up of the schedule are conducted. In some special cases it was possible to develop the algorithms, capable to find the decision for comprehensible time. At the same time the majority of real problems of drawing up of the schedule belong to the class NP-full. It does working out of the algorithm, capable to solve them for admissible time, really challenge even if it is possible to put a corresponding subject problem as однокритериальную. The situation is essentially aggravated with that the majority of real problems of drawing up of schedules многокритериальны. Various problems of drawing up of schedules can have much in common. For example, in problems of drawing up of a lesson schedule in high school and a drawing of works at the enterprise it is possible to draw following analogies between resources: Groups of students and employees, teachers and changes, an audience and qualification of employees, subjects and employers. Therefore the methods developed for one subclass of problems, it is often possible to transfer on others. The problem of drawing up of the schedule can be considered as a problem раскраски the count. We will remind that a problem раскраски the count names search of chromatic number of the count or, in other words, search of the minimum number of the colours necessary for раскраски of tops of some count with use for each pair of the next tops of various colours. The problem of search of chromatic number represents a NP-full problem for which decision various greedy algorithms are in most cases used. For statement of a problem of drawing up of the schedule as problems раскраски the column is under construction the count in whom each top represents the employment planned by the curriculum. In the event that between any two tops conflicts are possible, for example, both employment are spent in one audience or with one teacher they incorporate an edge. It is equivalent to an interdiction simultaneous проведенияэтих employment. Then the problem of drawing up of the schedule is represented as minimisation of number of the colours necessary for раскраски the column. Each colour corresponds to one period of the schedule. Application of this approach for the decision of real problems, apparently, ineffectively. At the same time, the problem раскраски the column at drawing up of schedules can appear useful in case of its combination with other algorithms.

• view as PDF (in Russian) (PDF)