Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Badania Operacyjne i Decyzje

2 Tarapata Z.

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: wielokryterialne problemy dróg najkrótszych

Sortuj według:

Ogranicz wyniki do:

Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

Tarapata Z.

Badania Operacyjne i Decyzje

2008

nr 4

107-132

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.

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.

Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

Tarapata Z.

Badania Operacyjne i Decyzje

2007

nr 2

83-1031

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.

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.