PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2008 | nr 4 | 107-132
Tytuł artykułu

Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

Treść / Zawartość
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)
Rocznik
Numer
Strony
107-132
Opis fizyczny
Twórcy
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000161629189
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.