Scheduling problems of stationary objects with the processor in one-dimensional zone

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