Wyniki wyszukiwania - BazTech

1

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

EN

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.

PL

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.

2

Metaheurystyki w szeregowaniu zadań uwarunkowanych czasowo

Ocetkiewicz K.M.

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

|

2008

|

T. 16

391-396

PL

W artykule tym zbadano zastosowanie algorytmów metaheurystycznych w problemach szeregowania zadań uwarunkowanych czasowo. Porównano wyniki algorytmu genetycznego, ewolucji różnicowej oraz symulowanego wyżarzania, z reprezentacjami rozwiązania: permutacyjną, opartą o priorytety reguł i kodowaniem przedziałowym, osiągnięte w rozwiązywaniu NP-trudnego problemu 1 | Pi = ai + bisi | [suma]WiCi, Gdzie to możliwe, wyniki porównano z rozwiązaniami optymalnymi.

EN

This article investigates the usefulness of metaheuristics in scheduling deteriorating jobs. Results in solving the NP-hard problem 1 | Pi = ai + bisi | ?WiCi of genetic algorithm, differential evolution and simulated annealing for the following representations of solution: permutation-based encoding, priority rule-based encoding and subrange encoding were compared. Where applicable, results were also compared to the optimal solutions.

3

Szeregowanie zadań w systemach silnie uwarunkowanych czasowo metodą cyklicznego obciążenia

Nawrocki J. R., Czajka A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 123

169-179

PL

W artykule przedstawione są wyniki badań dotyczących zastosowania metody minimalizacji obciążeń cyklicznych do szeregowania zadań silnie uwarunkowanych czasowo o okresach tworzących postęp binarny. Pokazano, że problem taki jest silnie NP-trudny i w związku z tym algorytm o złożoności wielomianowej nie istnieje. W tej sytuacji zaproponowana została prosta heurystyka zachłanna, która - jak wynika z przeprowadzonych eksperymentów obliczeniowych - zachowuje się lepiej od innych tego typu znanych heurystyk. Zastosowana do szeregowania zadań w samolocie F-16 dała w bardzo krótkim czasie optymalne rozwiązanie.

EN

In the paper scheduling hard real-time by minimising periodic loading is studied. It is assumed that task periods belong to a binary geometrical progression. It is shown that such a problem is strongly NP-hard. Thus, a simple greedy heuristics is proposed, which - due some computational experiments - is pretty effective and better than other greedy heuristics for the periodic loading problem. Applied to scheduling tasks for F-16 the heuristics returned an optimal solution in a very short time.