Problem szeregowania zadań wykonywanych na jednej maszynie z dynamicznym modelem terminów ich dostępności

• Autorzy: Janiak A. , Słoniński P.

Warianty tytułu

EN

A scheduling problem with jobs processed on a single machine with dynamic model of their release dates

• Konferencja: Automatyzacja procesów dyskretnych/krajowa konferencja (XII ; 13-16.09.2000 ; Zakopane)
• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy zaprezentowano rozwiązanie problemu minimalizacji czasu zakończenia wykonywania zbioru n zadań o dynamicznych modelach terminów dostępności na pojedynczej maszynie krytycznej. Dane jest ograniczenie na ilość zasobu dostępną do rozdysponowania w danej chwili. Wykazano szereg istotnych własności tego problemu, a na ich podstawie skonstruowano algorytm optymalnego rozdziału zasobu dla zadań w ustalonej permutacji oraz algorytm aproksymacyjny szeregowania zadań.

EN

The aim of this contribution is to present the solution of the problem of minimizing the time of processing a set of n jobs with dynamical (differential) models of job release dates on a single critical machine. The amount of resource available at each moment is known a priori. Many important properties of this problem have been proven. They are the base for construction of optimal resource allocation algorithm for jobs processed in a given permutation. There is also presented the approximation algorithm for the scheduling problem.

Słowa kluczowe

PL

szeregowanie zadań; problem jednomaszynowy; algorytm optymalny; algorytm aproksymacyjny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2000
• Tom: z. 129
• Strony: 167--177
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Janiak A.

autor

Słoniński P.

• Instytut Cybernetyki Technicznej Politechnika Wrocławska, 50-372 Wrocław, ul. Janiszewskiego 11/17, tel. [phone],