W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo

• Autorzy: Ocetkiewicz K.M.

Warianty tytułu

EN

A fully polynomial time scheme for a certain time-dependent scheduling problem

• Języki publikacji: PL

Abstrakty

PL

W artykule tym rozważany jest następujący problem szeregowania zadań: dany jest jeden procesor, zbiór zadań j1...,jn, czas przetwarzania zadania i wynosi Pi = a + bisi, zaś celem jest minimalizacja całkowitego czasu wykonywania zadań. Przedstawiony został pełny wielomianowy schemat aproksymacyjny, który, o ile wszystkie współczynniki wydłużania zadań (bi) w instancji problemu są różne i większe od pewnej, ustalonej liczby u, pozwala znaleźć rozwiązanie l+epsilon przybliżone w czasie będącym wielomianem rozmiaru danych oraz odwrotności epsilonu.

EN

In this article a following time-dependent scheduling problem is considered: there is given one processor, a set of j1,...,jn, the processing time of the ith job is given by pi = a + bisi and our goal is to minimize total completion time. A fully polynomial time approximation scheme is proposed, that, providing all deterioration rates are greater than a certain constant u, allows us to find a solution that is not more than 1+epsilon times greater than the optimal one. The running time of this algorithm is expressed by a polynomial of the size of the input and a reciprocal of epsilon.

Słowa kluczowe

PL

szeregowanie zadań; szeregowanie zadań uwarunkowanych czasowo

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2008
• Tom: T. 16
• Strony: 433--438
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Ocetkiewicz K.M.

• Politechnika Gdańska, Katedra Algorytmów i Modelowania Systemów

Bibliografia

• [1] Cheng T.C.E, Ding Q., Lin B.M.T.: A concise survey of scheduling with time-dependent processing limes, W: European Journal of Operational Research 152, s.: 1-13, 2004.
• [2] Gawiejnowicz S., Lai T-C., Chiang M-H.: Polynomially solvable cases of scheduling deteriorating jobs to minimize total completion time, W: Brucker P. et al. (eds.): 7th Workshop on Project Management and Scheduling, Osnabrück, 2000, s. 131-134, 2000.
• [3] Mosheiov G.: V-shaped policies for sheduling deteriorating jobs, w: Operations Research 39, s. 979-991, 1991.
• [4] Gawiejnowicz S., Kurc W., Pankowska L: A greedy approach for a time-dependent scheduling problem. W: Lecture Notes on Computer Science 2328, s.79-86, 2002.
• [5] Gawiejnowicz S., Kurc W., Pankowska L: Minimalizacja łącznego czasu zakończenia zbioru zadań czasowo-zależnych metodą kolejnych ulepszeń. W: Sterowanie procesami dyskretnymi, zarządzanie i inżynieria produkcji, s.47-54, WNT 2004.