Целочисленная модель с условиями оптимальности для задачи минимизации суммарного взвешенного времени обслуживания требований одним прибором

В работе рассматривается следующая задача теории расписаний. Требования обслуживаются одним прибором. Для каждого требования определены положительный вес и момент ожидания, до которого включительно оно недоступно для обработки. Длительности обслуживания одинаковы. В обслуживании разрешены прерывания. Время предполагается дискретным. Необходимо найти расписание обслуживания требований, минимизирующее взвешенную сумму моментов окончания обработки требований. Сложностной статус задачи на сегодня не известен. В работе представлена новая модель булева линейного программирования для данной задачи, включающая в себя некоторые необходимые условия оптимальности расписаний. Эти условия представлены в виде линейных неравенств. В результате проведённого вычислительного эксперимента замечено, что модель выдаёт целочисленное решение даже без наложения условий целочисленности на переменные. Табл. 3, ил. 2, библиогр. 10.