Issue: 2007/Vol.17/No.2, Pages 83-103
MODELS OF SCHEDULING SYNCHRONIZED MOVEMENT OF MANY OBJECTS
Zbigniew Tarapata
Cite as: Z. Tarapata. Models of scheduling synchronized movement of many objects. Operations Research and Decisions 2007: 17(2), 83-103.
Abstract
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. 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 szereg rozszerzeń omawianego problemu.
Keywords: harmonogramowanie i synchronizacja przemieszczania, drogi najkrótsze, drogi rozłączne, wielokryterialne problemy dróg najkrótszych
Received: Accepted: