Szeregowanie zadań na procesorach dedykowanych bez przestojów

• Autorzy: Giaro K.

Warianty tytułu

EN

Scheduling on dedicated processors without waiting periods

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

Abstrakty

PL

W praktycznym szeregowaniu zadań dość często spotykamy się z koniecznością zapewnienia nieprzerwanej pracy poszczególnym podmiotom naszego systemu. Szeregowanie takie nazywa się szeregowaniem bez przestojów. Zadaniem tej pracy jest zasygnalizowanie skali trudności obliczeniowej, jaką wymusza powyższe założenie. Wykażemy, że szereg podstawowych problemów decyzyjnych i optymalizacyjnych dotyczących istnienia lub najprostszych parametrów harmonogramu w szeregowaniu bez przestojów staje się NP-trudny, nawet dla systemów o grafach szeregowannia tak prostych jak ścieżka i cykl. Rozważania nasze będą dotyczyć modeli open show, flow shop oraz systemu zadań dwuprocesorowych.

EN

In practical task scheduling it is sometimes required that the elements of a system perform consecutively. Such a scheduling is called scheduling without waiting periods or no-wait and/or no-idle. In this article we study the complexity of some simplified scheduling problems of this kind. In particular, we show that many trivial questions about scheduling become NP-hard, even if the scheduling graph of a system is path, or a cycle. Our consideration concern the following models: open shop, flow shop and 2-procesor tasks system.

Słowa kluczowe

PL

szeregowanie zadań; szeregowanie bez przestojów; kolorowanie grafów; problem NP-trudny

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

Twórcy

autor

Giaro K.

• Politechnika Gdańska