ПОСТРОЕНИЕ РАСПИСАНИЙ ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ ОБЪЕКТОВ ПЕРЕМЕЩАЮЩИМСЯ В ОДНОМЕРНОЙ ЗОНЕ ПРОЦЕССОРОМ

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

Статья публикуется в авторской редакции.

1. Kogan D. I., Fedosenko Yu. S., “Zadacha dispetcherizatsii: analiz vychislitel’noy slozhnosti i polinomial’no razreshimye podklassy”, Diskretnaya matematika RAN, 8:3 (1996), 135– 147, [in Russian].

2. Tanaev V. S., Gordon V. S., Shafransky Y. N., Scheduling Theory, Single-Stage Systems, Springer Science+Business Media, 1994.

3. T’kindt V., Billaut J., Multicriteria scheduling: models and algorithms, Springer, 2006.

4. Brucker P., Knust S., Complex scheduling, Springer, 2006.

5. Brucker P., Scheduling Algorithms, Springer, 2007.

6. Pinedo M., Scheduling: Theory, Algorithms, and Systems, Springer, 2008.

7. Shen H., Optimal Scheduling for Satellite Refueling in Circular Orbits, PhD thesis, School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, Georgia, 2003.

8. Klimin A. V., Poedinok V. M., “Dozapravka v polete grazhdanskikh samoletov: perspektivy i problemy”, TsAGI, http://www.tsagi.ru/cgibin/jet/viewnews.cgi?id=20101230080777618957, [in Russian].

9. Yu P., Multiple Criteria Decision Making: Concepts, Techniques and Extensions, Plenum Press, NY, 1985.

10. Steuer R. E., Multiple Criteria Optimization: Theory, Computation and Application, J.Wiley&Sons Inc., NY-Chichester-Brisbane-Toronto-Singapore, 1986.

11. Ehrgott M., Multicriteria Optimization, second ed., Springer, 2005.

12. Podinovskiy V. V., Nogin V. D., Pareto-optimal’nye resheniya mnogokriterial’nykh zadach, Fizmatlit, 2007, [in Russian].

13. Bellman R., Dreyfus S. E., Applied dynamic programming, Princeton, 1962.

14. Sigal I. X., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel’nye algoritmy, Fizmatlit, 2007, [in Russian].

15. Garey M. R., Johnson D. S., Computers and intractability: A guide to the theory of NPcompleteness, W.H. Freeman & Co., 1979.

16. Arora S., Barak B., Computational Complexity: A Modern Approach, Princeton, 2009.

17. Lipton R. J., The P=NP Question and G¨odel’s Lost Letter, Springer Science+Business Media, 2010.

18. Villareal B., Karwan M., “Multicriteria Dynamic Programming with an Application to the Integer Case”, Journal of optimization theory and applications, 38:1 (1982), 43–69.

19. Kogan D. I., Dinamicheskoe programmirovanie i diskretnaya mnogokriterial’naya optimizatsiya, Izd-vo NNGU, N. Novgorod, 2004, [in Russian].

20. Dunichkina N. A., Kogan D. I., Pushkin A. M., Fedosenko Yu. S., “Ob odnoy modeli obsluzhivaniya statsionarnykh ob”ektov peremeshchayushchimsya v odnomernoy rabochey zone protsessorom”, Trudy, XII vserossiyskoe soveshchanie po problemam upravleniya VSPU-2014 (Moskva, 16-19 iyunya 2014g.), Institut Problem Upravleniya im. V.A.Trapeznikova RAN, 2014, 5044–5052, [in Russian].

21. Kogan D. I., Fedosenko Yu. S., “Optimal servicing strategy design problems for stationary objects in a one-dimensional working zone of a processor”, Automation and remote control, 71:10 (2010), 2058–2069.

22. Dorigo M., Optimization, Learning and Natural Algorithms, PhD thesis, Dipartamento di Elettronica, Politecnico di Milano, 1992.

23. Blum C., Roli A., “Metaheuristics in combinatorial optimization: Overview and conceptual comparison”, ACM Computing Surveys, 35(3) (2003), 268–308.

24. Jones M. T., Al Application Programming, Charles river media, Inc., Hingham, Massachusetts, 2003.

25. Dunichkina N., “Algorithms for bi-criteria single-machine scheduling problem of servicing a spaced group of objects”, Proceedings of the 3th International IT Conference “Information Technology in modern life”, in: Abstracts of presentations, Bonn-Rhein-Sieg University of Applied Sciences, 2008, 4.