RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2015, том 22, номер 3, страницы 356–371 (Mi mais446)  

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

[Построение расписаний обслуживания стационарных объектов перемещающимся в одномерной зоне процессором]

N. A. Dunichkinaa, D. I. Koganb, Yu. S. Fedosenkoa

a Volga State University of Water Transport, Nesterova str., 5a, Nizhny Novgorod, 603005, Russia
b Moscow State University of Instrument Engineering and Informatics, Stromynka str., 20, Moscow, 107996, Russia

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

Ключевые слова: теория расписаний, динамическое программирование, принцип Парето, $NP$-трудность, многокритериальная оптимизация.

DOI: https://doi.org/10.18255/1818-1015-2015-3-356-371

Полный текст: PDF файл (527 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.987
Поступила в редакцию: 25.03.2015
Язык публикации: английский

Образец цитирования: N. A. Dunichkina, D. I. Kogan, Yu. S. Fedosenko, “Scheduling problems of stationary objects with the processor in one-dimensional zone”, Модел. и анализ информ. систем, 22:3 (2015), 356–371

Цитирование в формате AMSBIB
\RBibitem{DunKogFed15}
\by N.~A.~Dunichkina, D.~I.~Kogan, Yu.~S.~Fedosenko
\paper Scheduling problems of stationary objects with the processor in one-dimensional zone
\jour Модел. и анализ информ. систем
\yr 2015
\vol 22
\issue 3
\pages 356--371
\mathnet{http://mi.mathnet.ru/mais446}
\crossref{https://doi.org/10.18255/1818-1015-2015-3-356-371}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3417967}
\elib{http://elibrary.ru/item.asp?id=23884404}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais446
  • http://mi.mathnet.ru/rus/mais/v22/i3/p356

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:87
    Полный текст:24
    Литература:14

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019