УДК 519.112.71 ЗАДАЧА СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО ГРАФИКА РАБОТ М. Г. Землянухин, Г. Д. Чернышова Воронежский государственный университет Поступила в редакцию 07.12.2013 г. Аннотация. <...> В работе рассмотрена задача о равномерном назначении в случае, когда имеется общий график работ и, когда такового нет. <...> Показана возможность сведения задачи к модели открытого транспортного типа с ограничениями на пропускную способность. <...> Ключевые слова: дискретная оптимизация, задача о дополнительном назначении, многокритериальная задача. <...> ВВЕДЕНИЕ Рассматривается задача о дополнительном назначении n работников для выполнения заданного объёма работ в течение некоторого периода из m дней ([1], [2]). <...> Заметим, что возможен вариант такой, что S ,, , m 12 = ss s } – каждый человек выполняет в день одну работу; – матрица R возможностей каждого раДля корректности задачи очевидно должны быть выполнены условия достаточности числа работников на каждый день: ∑ ≥= i=1 n r s j m ij j , , 1, , . т.е. число работников, которые могут работать в определённый день должно быть не меньше числа запланированных работ на этот день. <...> Обязательные назначения часто фиксируют лишь часть выполненных работ, т.е. существует l : ∑ <= i=1 n a il s l m l , , 1, , . <...> Требуется осуществить дополнительные назначения так, чтобы все работы были выполнены. <...> При этом каждый работник желает иметь минимальное число дополнительных назначений. <...> В результате, получена многокритериальная задача с булевыми переменными. <...> Полученную многокритериальность предлагается реализовать с помощью известного принципа гарантированного результата. <...> Это находится в соответствии с пожеланием о равномерности назначений. <...> Ограничения задачи можно переписать µµ µ µ µ µ µ µ µ µ µ µ µ Задача составления оптимального графика работ где M = 1, ij ij +∞ ,, ij если иначе ra i =1, ,n,j m (1 ) 1 −= ij =1, , , т. е. M – фиксируют штрафы за назначения, противоречащие его возможностям. <...> Такая модель может <...>