PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 7

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available KOALA Graph Theory Internet Service
Goluch T., Ocetkiewicz K. M., Giaro K.
TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
|
2015
|
Vol. 19, No 4
455--470
EN
KOALA has been created with the idea of C++ library templates, implementing a broad set of procedures in the fields of algorithmic graph theory and network problems in discrete optimization. During the C2 NIWA project, a library has been greatly extended, the code refactored and enclosed with the internet service available in the public repository of the project. Today it contains interconnected educational materials in the form of Wikibook, documentation and sample codes, a multifunctional web-based application for edition of graphs, a collection of over 100 web services which offers a library of selected procedures to be run on the BeesyCluster system.
2
Content available 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
PL
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.
EN
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.
3
Content available remote 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
EN
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.
4
Content available 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
PL
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.
EN
The article presents a branch-and-bound algorithm for a follo­wing 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.
5
W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo
Ocetkiewicz K.M.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2008
|
T. 16
433-438
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.
6
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.
7
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
PL
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.
EN
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.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.