Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: time-dependent scheduling

Sortuj według:

Ogranicz wyniki do:

Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych

Ocetkiewicz K. M., Kubale M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2011

T. 15, z. 2

375-380

Niniejszy artykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. Model matematyczny, który tutaj zastosowano, to szeregowanie zadań uwarunkowanych czasowo. Przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. Pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie.

The article is devoted to scheduling jobs of fire fighting squads dealing with forest fire. Time-dependent scheduling is employed as a mathematical model. The complexity of two optimization criteria was discussed: the makespan and the total completion time. It is shown that, in general case, there are no ideal schedules that guarantee minimization of both of these goals simultaneously.

Algorytm branch-and-bound dla pewnego problemu szeregowania zadań uwarunkowanych czasowo

Ocetkiewicz K. M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2009

T. 13, z. 2

521-529

W pracy przedstawiono algorytm branch-and-bound dla problemu szeregowania zadań uwarunkowanych czasowo 1 | pi = 1 + atst | XQ, a także wyniki eksperymentów komputerowych prezentujących wydajność algorytmu. Zastosowanie przedstawionego algorytmu umożliwia powiększenie "obliczalnych" rozmiarów instancji o 6-10 zadań w stosunku do algorytmu pełnego przeszukiwania.

The article presents a branch-and-bound algorithm for a following time-dependent scheduling problem: 1 \pt: = 1 + atst | XC,. The computational experiments were conducted to examine the efficiency of the algorithm. Application of the presented algorithm allows us to increase the size of input instances that can be solved to optimality in reasonable time by 6-10 jobs, compared to the exhaustive-search algorithm.

Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania

Ocetkiewicz K.M.

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

2007

T. 12

145-152

W pracy rozważany jest następujący, jednoprocesorowy problem szeregowania zadań czasowo-zależnych. Danych jest n+ 1 zadań o czasach wykonywania postaci p; = a + bis;, gdzie s; oznacza czas rozpoczęcia wykonywania i-tego zadania, a > O, b; > O, i = O, 1, ..., n. Wszystkie zadania są niepodzielne i dostępne w chwili to = O. Należy znaleźć harmonogram minimalizujący łączny czas zakończenia. W pracy przedstawiono algorytm, który, o ile kolejne wartości bi rosną dostatecznie szybko, znajduje optymalny harmonogram. Następnie zaproponowano dwie nowe heurystyki, oraz porównano rozwiązania zwracane przez te, oraz inne znane heurystyki dla danych wejściowych o znanym rozwiązaniu optymalnym.

In this paper a single machine time-dependent scheduling problem is considered. The processing time of the i-th job is given by Pi = a + biSi, where a > 0, bi > 0, i = 0, 1, ..., n. All tasks are available at t0 = 0, and the goal is to minimize the total completion time. An algorithm, which gives optimal solution, provided that the values of bi coefficients grow sufficiently fast, was presented. Two new heuristics were introduced. Their's, and other known heuristics' results were compared to optimal solutions.