Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

• Autorzy: Zbigniew Tarapata

Warianty tytułu

Models of scheduling synchronized movement of many objects

• Języki publikacji: PL

Abstrakty

W pracy przedstawiono problem wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów. 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. Skoncentrowano się na sformułowaniu nieliniowego zadania harmonogramowania przemieszczania obiektów. 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 np. łeksykograficznego 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 szereg rozszerzeń omawianego problemu. (abstrakt oryginalny)

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

Słowa kluczowe

PL

Harmonogram; Badania operacyjne; Przemysł

EN

Schedule; Operations research; Industry

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2007
• Numer: nr 2
• Strony: 86--103

Twórcy

autor

Zbigniew Tarapata

Bibliografia

• [1] BLAZEWICZ J., ECKER K.H., PESCH E., SCHMIDT G., WĘGLARZ 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 16lh 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 5lh 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 3ld 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.