Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

• Autorzy: Tarapata Z.

Warianty tytułu

EN

Scheduling algorithms of synchronized movement of many objects

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono algorytmy wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów. Zdefiniowano problem harmonogramowania przemieszczania w postaci dwukryterialnego nieliniowego zadania optymalizacji. Omówiono sposób rozwiązania sformułowanego problemu dwukryterialnego poprzez poszukiwanie rozwiązania leksykograficznego. Podano dwa algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów oraz opisano ich własności. Szczegółowo omówiono konieczne i wystarczające warunki umożliwiające otrzymanie rozwiązania optymalnego. Oszacowano złożoności obliczeniowe prezentowanych algorytmów oraz przedyskutowano ich własności. Zasadę działania algorytmów zilustrowano przykładami.

EN

The paper presents algorithms of determining a synchronized movement schedule of many objects. The author defines movement scheduling as a bicriterion nonlinear optimization problem. He also presents a method of solving the bicriterion problem which is based on finding a lexicographic solution. Two scheduling algorithms of synchronized movement and their properties are given. The first algorithm is based on the dynamic programming, the second one is based on the cost-profit analysis. The necessary and sufficient conditions for obtaining optimal solutions from the algorithms are discussed in detail. The author describes computational complexity and some properties of the algorithms. The idea of the algorithms is presented with a few examples.

Słowa kluczowe

PL

harmonogramowanie i synchronizacja przemieszczania; drogi najkrótsze; drogi rozłączne; wielokryterialne problemy dróg najkrótszych; algorytmy harmonogramowania

EN

movement scheduling and synchronization; shortest paths; disjoint paths; multicriteria shortest paths problems; scheduling analysis

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2008
• Tom: nr 4
• Strony: 107--132
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Tarapata Z.

• Zakład Badań Operacyjnych i Wspomagania Decyzji, Instytut Systemów Informatycznych, Wydział Cybernetyki, Wojskowa Akademia Techniczna, ul. Kaliskiego 2, 00-908 Warszawa,

Bibliografia

• [1] BLAZEWICZ J., ECKER K.H., PESCH E., SCHMIDT G., WEGLARZ J., Scheduling Computer and Manufacturing Processes, Springer-Verlag, Heidelberg–Berlin-New York 2001.
• [2] BUCHLI J. (ed.), Mobile Robotics Moving Intelligence, ISBN 3-86611-284-X, Pro Literatur Verlag,Germany, 2006.
• [3] EPPSTEIN D., Finding the K shortest Paths, SIAM J. Computing, 1999, 28(2), 652–673.
• [4] IBARAKI T., Algorithms for obtaining shortest paths visiting specified nodes, SIAM Review, 1973,Vol. 15, No. 2, Part 1, 309–317.
• [5] LOGAN B., Route planning with ordered constraints, Proceedings of the 16th Workshop of the UK Planning and Scheduling Special Interest Group, December, Durham (UK), 1997.
• [6] LONGTIN M., MEGHERBI D., Concealed routes in ModSAF [in:] Proceedings of the 5th Conference on Computer Generated Forces and Behavioural Representation, Technical Report, Institute for Simulation and Training, 1995, 305–314.
• [7] LEUNG J.Y.-T. (ed.), Handbook of Scheduling: Algorithms, Models and Performance Analysis,Chapman & Hall/CRC, Boca Raton–London–New York–Washington 2004.
• [8] PETTY M.D., Computer generated forces in Distributed Interactive Simulation, Proceedings of the Conference on Distributed Interactive Simulation Systems for Simulation and Training in the Aerospace Environment, 19–20 April, Orlando (USA) (1995), 251–280.
• [9] RAJPUT S., KARR C., Unit Route Planning, Technical Report IST-TR-94-42, Institute for Simulation and Training, Orlando (USA), 1994.
• [10] SCHRIJVER A., SEYMOUR P., Disjoint paths in a planar graph – a general theorem, SIAM Journal of Discrete Mathematics, 1992, 5, 112–116.
• [11] SCHRIJVER A., Combinatorial Optimization. Polyhedra and Efficiency, Springer-Verlag, Berlin–New York 2004.
• [12] TARAPATA Z., Modelling, optimisation and simulation of groups movement according to group pattern in multiresolution terrain-based grid network, Proceedings of the 3rd NATO Regional Conference on Military Communication and Information Systems, 10–12 October, Zegrze (Poland),2001, Vol. I, 241–251.
• [13] TARAPATA Z., Synchronization method of many objects movement in Computer Generated Forces systems, Proceedings of the 7th NATO Regional Conference on Military Communication and Information Systems, 04–05 October, Zegrze (Poland), 2005, 93–99.
• [14] TARAPATA Z., Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów,Badania Operacyjne i Decyzje, 2007, nr 2, 83–103.