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

N. A. Dunichkina ; D. I. Kogan ; Yu. S. Fedosenko

Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 3, pp. 356-371.

Résumé

We consider the mathematical model in which an operating processor serves the set of the stationary objects positioned in a one-dimensional working zone. The processor performs two voyages between the uttermost points of the zone: the forward or direct one, where certain objects are served, and the return one, where remaining objects are served. Servicing of the object cannot start earlier than its ready date. The individual penalty function is assigned to every object, the function depending on the servicing completion time. Minimized criteria of schedule quality are assumed to be total service duration and total penalty. We formulate and study optimization problems with one and two criteria. Proposed algorithms are based on dynamic programming and Pareto principle, the implementations of these algorithms are demonstrated on numerical examples. We show that the algorithm for the problem of processing time minimization is polynomial, and that the problem of total penalty minimization is $NP$-hard. Correspondingly, the bi-criteria problem with the mentioned evaluation criteria is fundamentally intractable, computational complexity of the schedule structure algorithm is exponential. The model describes the fuel supply processes to the diesel-electrical dredgers which extract non-metallic building materials (sand, gravel) in large-scale areas of inland waterways. Similar models and optimization problems are important, for example, in applications like the control of satellite group refueling and regular civil aircraft refueling. The article is published in the author's wording.

Détail

Keywords: scheduling, dynamic programming, $NP$-complexity, multicriteria optimization.
Mots-clés : Pareto concept

Bibliographie

[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) | MR | Zbl

[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 | MR | Zbl

[5] Brucker P., Scheduling Algorithms, Springer, 2007 | Zbl

[6] Pinedo M., Scheduling: Theory, Algorithms, and Systems, Springer, 2008 | MR | Zbl

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

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

[9] Yu P., Multiple Criteria Decision Making: Concepts, Techniques and Extensions, Plenum Press, NY, 1985 | MR | Zbl

[10] Steuer R. E., Multiple Criteria Optimization: Theory, Computation and Application, J. Wiley Sons Inc., NY–Chichester–Brisbane–Toronto–Singapore, 1986 | MR | Zbl

[11] Ehrgott M., Multicriteria Optimization, second ed., Springer, 2005 | MR | Zbl

[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 University Press, 1962 | MR | Zbl

[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 NP-completeness, W.H. Freeman Co., 1979 | MR | Zbl

[16] Arora S., Barak B., Computational Complexity: A Modern Approach, Princeton University Press, 2009 | MR

[17] Lipton R. J., The P=NP Question and Gödel's Lost Letter, Springer Science+Business Media, 2010 | MR

[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 | MR

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

[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”, XII vserossiyskoe soveshchanie po problemam upravleniya, VSPU-2014, Trudy (Moskva, 16–19 iyunya 2014 g.), Institut Problem Upravleniya im. V. A. Trapeznikova RAN, M., 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 | MR | Zbl

[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., AI 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”, Information Technology in modern life, Proceedings of the 3th International IT Conference, Abstracts of presentations, Bonn-Rhein-Sieg University of Applied Sciences, 2008, 4