Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

• Autorzy: Zbigniew Tarapata

Warianty tytułu

Scheduling algorithms of synchronized movement of many objects

• Języki publikacji: PL

Abstrakty

W pracy przedstawiono algorytmy wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów. Zdefiniowano problem harmonogramowania przemieszczania w postaci dwu-kryterialnego 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. (abstrakt oryginalny)

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. (original abstract)

Słowa kluczowe

PL

Algorytmy; Harmonogram; Badania operacyjne

EN

Algorithms; Schedule; Operations research

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2008
• Numer: nr 4
• Strony: 107--132

Twórcy

autor

Zbigniew Tarapata

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-8661 l-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 l, 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. 1,241-251.
• [13] TARAPATA Z., Synchronization method of many objects movement in Computer Generated Forces systems, Proceedings of the 7lh NATO Regional Conference on Military Communication and Information Systems, 04-05 October, Zegrze (Poland), 2005, 93-99.
• [l4] TARAPATA Z., Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów, Badania Operacyjne i Decyzje, 2007, nr 2, 83-103.