Szeregowanie zadań w systemach z ograniczoną dostępnością maszyn

• Autorzy: Błażewicz J. , Drozdowski M. , Formanowicz P. , Kubiak W.

Warianty tytułu

EN

Scheduling tasks in systems with limited machine availability

• Konferencja: XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych; Zakopane 24-27.09.1998
• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono wybrane problemy szeregowania zadań na maszynach z okresami niedostępności. Rozważane są zagadnienia dotyczące maszyn równoległych identycznych i dowolnych, a także przepływowego systemu obsługi. W przypadku maszyn równoległych omawiane problemy dotyczą zadań podzielnych bez ograniczeń kolejnościowych oraz z takimi ograniczeniami i kryterium Cmax oraz Lmax. Przedstawione są wyniki dotyczące złożoności obliczeniowej oraz algorytmy oparte na programowaniu liniowym. Dla problemów szeregowania w przepływowym systemie obsługi określono złożoność obliczeniową problemu szeregowania na dwóch maszynach z kryterium Cmax. Ponadto przedstawiono własność tego problemu przydatną przy konstrukcji algorytmu podziału i ograniczeń oraz wyniki eksperymentu obliczeniowego.

EN

The selected problems of scheduling tasks on machines with a limited availability are presented. Problems concerning parallel identical and unrelated machines and flow shop system are considered. In the case of parallel machines the problems presented are concerned with preemptive tasks with and without precedence constraints and Cmax and Lmax criteria. Computational complexity results and algorithms based on linear programming are presented. In the case of flow shop the computational complesity for two-machine problem with Cmax criterion is analysed. Moreover, a property of this problem is presented which is useful for constructing a branch and bound algorithm, and results of computational experiment are presented.

Słowa kluczowe

PL

szeregowanie zadań; maszyny okresowo niedostępne; macierz grafu; macierz sąsiedztwa

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 1998
• Tom: z. 123
• Strony: 55--63
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Błażewicz J.

autor

Drozdowski M.

autor

Formanowicz P.

autor

Kubiak W.

• Instytut Informatyki Politechniki Poznańskiej, 60-965 Poznań, ul. Piotrowo 3a, tel. [phone]