Задачи диспетчеризации обслуживания стационарных объектов в одномерной рабочей зоне процессора

Рассматривается система, в которой обслуживание совокупности стационарных объектов, рассредоточенных в пределах одномерной зоны, осуществляет перемещающийся процессор. Однократное обслуживание каждого объекта должно быть выполнено в процессе реализации двух рейсов процессора – прямого и обратного. Обслуживание любого объекта нельзя начать ранее предписанного ему срока; с каждым объектом ассоциирован индивидуальный штраф, являющийся монотонно возрастающей функцией от момента завершения обслуживания. Для формулируемых оптимизационных задач предлагаются реализующие принцип динамического программирования алгоритмы решения, приводятся примеры их реализации и результаты численных экспериментов; исследуется вычислительная сложность решающих алгоритмов и поставленных задач.

Статья представлена к публикации членом редколлегии: А. А. Лазарев