Wsadowe szeregowanie zadań jednostkowych na pojedynczym procesorze

• Autorzy: Furmańczyk H. , Żyliński P.

Warianty tytułu

EN

Scheduling unit time jobs on a single batch processing machine

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

Problem wsadowego szeregowania zadań jednostkowych na jednej maszynie polega na przydzieleniu zadań kompatybilnych do wsadów, które będą wykonywane w oddzielnych chwilach czasu. W pracy zajmiemy się przypadkiem, w którym graf modelujący problem jest grafem porównywalnym, split grafem albo kografem, a wielkość wsadu jest ograniczona przez stałą p. Naszym celem jest takie uszeregowanie zadań, aby łączny czas ich wykonywania był jak najmniejszy. Na koniec omówimy zastosowanie heurystyki wyżarzania symulowanego dla rozważanego problemu w przypadku ogólnym.

EN

Problem of scheduling on a single batch processing machine reduces to attaching compatible jobs to batches. At most one batch can be treated at a time. In this paper we consider cases which are modeled by a graph which is a comparability graph, split graph or a cograph and the capacity of a batch is bounded by a constant p. Our aim is to schedule the jobs in such way that the makespan is as small as possible. In the last section we attemp to solve this problem in general case with the simulated annealing algorithm.

Słowa kluczowe

PL

szeregowanie zadań; szeregowanie wsadowe; problem jednomaszynowy; wyżarzanie symulowane

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 127--137
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Furmańczyk H.

autor

Żyliński P.

• Uniwersytet Gdański, Gdańsk