Wyniki wyszukiwania - BazTech

1

Reinforcement Learning Algorithms for Online Single-Machine Scheduling

Li Yuanyuan, Fadda Edoardo, Manerba Daniele, Tadei Roberto, Terzo Olivier

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

277--283

EN

Online scheduling has been an attractive field of research for over three decades. Some recent developments suggest that Reinforcement Learning (RL) techniques have the potential to deal with online scheduling issues effectively. Driven by an industrial application, in this paper we apply four of the most important RL techniques, namely Q-learning, Sarsa, Watkins's Q(λ), and Sarsa(λ), to the online single-machine scheduling problem. Our main goal is to provide insights on how such techniques perform. The numerical results show that Watkins's Q(λ) performs best in minimizing the total tardiness of the scheduling process.

2

Problem dystrybucji z terminami dostaw

Bożejko W., Walczyński M., Wodecki M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 150

25-30

PL

W pracy przedstawiono algorytm oparty na metodzie przeszukiwania z tabu, rozwiązywania problemu dystrybucji z terminami dostaw. Jest on równoważny pewnemu jednomaszynowemu problemowi szeregowania, który w literaturze jest oznaczany przez 1|sij|ΣwiTi i należy do klasy problemów silnie NP-trudnych. Wykonano obliczenia na reprezentatywnej grupie danych, a otrzymane wyniki porównano z najlepszymi znanymi w literaturze.

EN

A tabu search algorithm is proposed in the paper to solve a distribution problem with due dates. It is equivalent to a single machine scheduling problem, which is described by 1|sij|ΣwiTi in the literature and it belongs to strongly NP-hard class. Calculations were done on representative group of test instances, obtained results were compared to the best known solutions from the literature.

3

Nowe wykorzystanie metody blokowej w konstrukcji algorytmów heurystycznych dla ogólnego problemu przepływowego

Grabowski J., Pempera J.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 150

45-50

PL

Własności blokowe są z powodzeniem stosowane do usuwania ruchów nierokujących poprawy dla wielu otoczeń stosowanych w algorytmach popraw dla problemów szeregowania. W pracy, dla ogólnego problemu przepływowego, zaproponowano nowy sposób przeglądania otoczenia, który pozwala na eliminację znacznie większego zbioru ruchów. W celu sprawdzenia efektywności metody przeprowadzono eksperyment komputerowy na instancjach Taillarda.

EN

The block properties are successfully applied to a priory eliminate non promising moves from the neighborhood for many local search algorithm of solving scheduling problems. In this paper, for the general flowshop problem, it presents new method of searching the neighborhood, which gives rise to eliminate highly greater set of moves. To validate efficiency of the proposed method, computational experiment have been executed on a well-known Taillard's benchmarks.

4

A new local search optimization algorithm for the job-shop problem

Grabowski J., Wodecki M.

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

|

2003

|

T. 7, z. 1-2

121-128

EN

This paper deals with a classic job-shop scheduling problem with makespan criterion. We present some new theoretical properties of the problem associated with the blocks, moves and neighbourhood structure, and algorithm based on a tabu search approach. Computational experiments are given and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed solves the job-shop instances with high accuracy in a very short time.

PL

W referacie przedstawimy algorytm tabu oparty na idei bloków z drogi krytycznej, dla rozwiązywania ogólnego problemu szeregowania (ang. job-shop problem). Szacowanie wartości funkcji celu rozwiązań z otoczenia (bez konieczności dokładnego ich liczenia), znacznie przyspiesza zbieżność i skraca czas działania algorytmu. Przedstawimy pewne metody (perturbacje) pozwalające na bardzo szybką zmianę badanych obszarów zbioru rozwiązań dopuszczalnych oraz nowy sposób realizacji listy tabu, który zapobiega powstawaniu cykli w algorytmie (generowaniu tych samych rozwiązań po pewnej liczbie kroków algorytmu). Przeprowdzone eksperymenty obliczeniowe wskazują jednoznacznie, że wyżej przedstawione idee znacznie przyspieszają oraz poprawiają wyniki algorytmu.