Задача учебного расписания: постановка и решение

Abstract

Задачу навчального розкладу розглянуто як багатовимірну задачу лінійного програмування. Наведено математичну постановку задачі з визначенням суб’єктів розкладу, цільової функції і системи узгоджених обмежень. Метод і алгоритм розв’язання задачі полягають у приведенні її до стандартної одновимірної задачі лінійного програмування. Обговорено проблеми цілочисельності розв’язку і використання оперативної пам’яті.

The problem of educational timetable is considered as a multidimensional linear programming problem. The mathematical statement of the problem including definitions of timetable subjects, goal function, and systems of concerted restrictions is given. The method and algorithm for solving the problem, consisting in its reduction to a standard one-dimensional linear programming problem, are proposed. The issues of integer solution and main memory usage are discussed.