Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

• Autorzy: Tarapata Z.

Warianty tytułu

EN

Models of scheduling synchronized movement of many objects

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono problem wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów, wykorzystywany w zagadnieniach: routingu w sieciach komputerowych, planowania przemieszczania mobilnych robotów, przetwarzania zadań w systemach równoległych (rozproszonych), sterowania ramionami wielu niezależnych robotów, planowania i synchronizacji przemieszczania wielu obiektów w symulacyjnych grach komputerowych (systemy typu CGF i SAF). Omówiono szereg modeli harmonogramowania przemieszczania. Zdefiniowano dwie grupy kryteriów istotnych z punktu widzenia oceny harmonogramu: kryteria związane z szybkością przemieszczania obiektów oraz z „równoległością” ich przemieszczania (w sensie położenia i czasu osiągnięcia pewnych punktów pośrednich). Skupiono się na sformułowaniu nieliniowego zadania harmonogramowania przemieszczania obiektów w celu minimalizacji sumy opóźnień w tzw. punktach wyrównania, przy pewnych dodatkowych ograniczeniach. Przedstawiono również dwa równorzędne sformułowania problemu w postaci dwukryterialnych zadań programowania matematycznego. Wykazano, że macierz współczynników ograniczeń w tych zadaniach jest całkowicie unimodularna, co umożliwia zastosowanie efektywnych algorytmów rozwiązywania zadań programowania liniowego, przy poszukiwaniu leksykograficznego rozwiązania problemu dwukryterialnego. Omówiono podobieństwa i różnice między sformułowanym problemem harmonogramowania, a klasycznym problemem szeregowania zadań przed liniami krytycznymi w celu minimalizacji maksymalnego opóźnienia zadań. Zdefiniowano wiele rozszerzeń omawianego problemu. Jako jedno z nich opisano problem planowania przemieszczania wielu obiektów zgodnie z pewnym wzorcem ugrupowania. Zarysowano sposoby rozwiązywania sformułowanych problemów harmonogramowania.

EN

The paper deals with the problem of determining movement schedule of many objects, used in many domains such as: routing in computer networks, movement planning of mobile robots, tasks processing in parallel or distributed computing systems, arms control of independent robots, planning and synchronization of the movement of many objects in computer simulation games (e.g. in Computer Generated Forces (CGF) systems or Semi-Automated Forces (SAF) systems). A lot of movement scheduling models are discussed. Two groups of criteria which are essential from the point of view of schedule estimation are described: a group connected with movement time of all objects and a group connected with “parallelization” of their movement (in the sense of location and times of reaching specified checkpoints). A nonlinear movement scheduling problem in order to minimize the sum of delays of all objects at checkpoints with some additional constraints is defined. Two equivalent formulations of two-criteria mathematical programming problems are also presented. It is proved that constraint coefficient matrices for both problems are totally unimodular and we can use effective algorithms for solving linear programming problems to find lexicographic solution of two-criteria problems. Similarities and differences between the defined problem and classical tasks scheduling problem before critical lines on parallel processors are discussed. Some extensions of the problem are presented. One of which is the scheduling movement problem of many objects according to a group pattern. Methods of solving formulated problems are indicated.

Słowa kluczowe

PL

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

EN

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

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2007
• Tom: nr 2
• Strony: 83--1031
• Opis fizyczny: Bibliogr. 16 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] COFFMAN E. Jr. (red.), Teoria szeregowania zadań, WNT, Warszawa 1980.
• [3] EHRGOTT M., GANDIBLEUX X. (eds.), Multiple Criteria Optimization – state of the art annotated bibliographic surveys, Kluwer Academic Publishers, Boston 2002.
• [4] EPPSTEIN D., Finding the K shortest Paths, SIAM J. Computing, 28(2), 1999, s. 652–673.
• [5] IBARAKI T., Algorithms for obtaining shortest paths visiting specified nodes, SIAM Review, Vol. 15, No. 2, Part 1 (Apr. 1973), s. 309–317.
• [6] 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).
• [7] 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, s. 305–314.
• [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, s. 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., Combinatorial Optimization. Polyhedra and Efficiency, Springer-Verlag, Berlin–New York 2004.
• [11] SCHRIJVER A., SEYMOUR P., Disjoint paths in a planar graph – a general theorem, SIAM Journal of Discrete Mathematics, 5, 1992, s. 112–116.
• [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, s. 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, s. 93–99.
• [14] TARAPATA Z., Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów, Badania Operacyjne i Decyzje, 2007 (złożony do druku).
• [15] TARAPATA Z., Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms, International Journal of Applied Mathematics and Computer Science, 2007, Vol. 17, No. 2, s. 269–287.
• [16] WARBURTON A., Approximation of Pareto optima in multiple-objective, shortest-path problems, Operations Research, 35, 1987, s. 70–79.