Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: deteriorating jobs

Sortuj według:

Ogranicz wyniki do:

Elimination of dominated partial schedules in scheduling deteriorating jobs

Ocetkiewicz K.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

2010

T. 18

339-344

In the article we consider a problem of scheduling deteriorating jobs that can be described by 1 | pi = a + bisi | ?Ci. We introduce the concept of dominated partial schedules and present a non-polynomial algorithm for the problem, that is based on elimination of dominated partial schedules. We present the results of computational experiments comparing the efficiency of given algorithm to other exact algorithms for the problem (exhaustive-search, branch-and-bound). Finally, we investigate the usefulness of the given algorithm as an approximate algorithm for problems 1 | pi = a + bisi | ?wiCi, 1 | pi = ai + bisi | ?Ci and 1 | pi = ai + bisi | ?wiCi.

W artykule rozważany jest problem szeregowania zadań uwarunkowanych czasowo, w notacji trójpolowej opisywany przez 1 | pi = a + bisi | ?Ci. Wprowadzona jest koncepcja zdominowanych częściowych harmonogramów oraz przedstawiony jest niewielomianowy algorytm dla problemu, który bazuje na eliminacji zdominowanych częściowych harmonogramów. Przedstawione są wyniki eksperymentów obliczeniowych, porównujących zaprezentowany algorytm oraz inne algorytmy dokładne dla problemu 1 | pi = a + bisi | ?Ci (pełne przeszukiwanie, branch-and-bound). Na koniec sprawdzona jest skuteczność algorytmu jako algorytmu przybliżonego dla problemów 1 | pi = a + bisi | ?wiCi, 1 | pi = ai + bisi | ?Ci oraz 1 | pi = ai + bisi | ?wiCi.

A new optimal algorithm for a time-dependent scheduling problem

Kubale M., Ocetkiewicz K. M.

Control and Cybernetics

2009

Vol. 38, no 3

713-721

In this article a single machine time-dependent scheduling problem with total completion time criterion is considered. There are n given jobs, j1,...,jn, and the processing time pi of the i-th job is given by pi = 1 + biSi, where si is the starting time of the i-th job, i = 1,...n. If all jobs have different and non-zero deterioration rates and bi [wzór], where bmin = min{bi}, then an optimal schedule can be found in O(n log n) time. The conducted computational experiments show that the presented algorithm performs very well even on data not satisfying the assumed constraints.