Szeregowanie zadań o znanej sekwencji z uwzględnieniem kosztów wyprzedzeń i opóźnień

• Autorzy: Bauman J. , Józefowska J.

Warianty tytułu

EN

Scheduling a sequence of jobs with earliness-tardiness costs

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

Abstrakty

PL

W pracy rozważa się problem szeregowania zadań, o dowolnych oczekiwanych terminach zakończenia, na jednej maszynie z kryterium minimalizacji kosztów nieterminowości wykonania zadań. Funkcje kosztów wyprzedzeń i opóźnień są liniowe, asymetryczne i indywidualne dla poszczególnych zadań. Zaprezentowano algorytm o złożoności O(nlogn) znajdujący optymalne uszeregowanie danej sekwencji zadań. Koncepcja polega na zastosowaniu funkcji określającej koszt modyfikacji uszeregowania, aktualizowanej po uszeregowaniu kolejnego zadania.

EN

We consider one-machine scheduling problem with individual due dates to minimize earliness-tardiness cost. The functions of the earliness-tardiness cost are linear, asymmetric and task dependent. We propose an 0(nlogn) algorithm to find an optimal schedule for a given sequence of jobs. A concept of a schedule modification cost function updated after adding each task is used.

Słowa kluczowe

PL

problem jednomaszynowy; szeregowanie zadań

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

Twórcy

autor

Bauman J.

autor

Józefowska J.

• Politechnika Poznańska, Poznań