Wyniki wyszukiwania - BazTech

1

Multi-criteria human resources planning optimisation using genetic algorithms enhanced with MCDA

Jurczak Marcin, Miebs Grzegorz, Bachorz Rafał A.

Operations Research and Decisions

|

2022

|

Vol. 32, No. 4

57--74

EN

The main objective of this paper is to present an example of the IT system implementation with advanced mathematical optimisation for job scheduling. The proposed genetic procedure leads to the Pareto front, and the application of the multiple criteria decision aiding (MCDA) approach allows extraction of the final solution. Definition of the key performance indicator (KPI), reflecting relevant features of the solutions, and the efficiency of the genetic procedure provide the Pareto front comprising the representative set of feasible solutions. The application of chosen MCDA, namely elimination et choix traduisant la réalité (ELECTRE) method, allows for the elicitation of the decision maker (DM) preferences and subsequently leads to the final solution. This solution fulfils all of the DM expectations and constitutes the best trade-off between considered KPIs. The proposed method is an efficient combination of genetic optimisation and the MCDA method.

2

Równoległa meta2heurystyka dla problemu gniazdowego z równoległymi maszynami

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

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

|

2009

|

T. 13, z. 2

207-213

PL

W pracy rozpatrywany jest ogólny problem kolejnościowy z równoległymi maszynami (flexible job shop problem), w którym dany jest zbiór zadań oraz zbiór maszyn. Maszyny tego samego typu (rodzaju), tj. o tych samych własnościach funkcjonalnych (które jednak mogą mieć różne parametry techniczne, takie jak na przykład wydajność) tworzą gniazdo. Do rozwiązania problemu proponujemy podejście dwupoziomowe - meta2heurystykę. Algorytm równoległy testowany jest na 128-procesorowej karcie GPU.

EN

We consider a double-level metaheuristic optimization algorithm in this paper. The algorithm proposed here includes two major modules: the machine selection module, which is executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, so we call this method meta2heuristics. We carry out computational experiment using 128-processors Graphics Processing Unit (GPU).

3

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.

4

Pewne modyfikacje algorytmu TSAB dla problemu gniazdowego

Nowicki E.

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

|

2001

|

T. 5, z. 1/2

439-447

PL

W pracy rozważa się problem minimalizacji terminu zakończenia wykonywania wszystkich zadań w gniazdowym problemie szeregowania. Przedstawiono szybki i łatwo implementowalny algorytm przybliżony do rozwiązania postawionego problemu. Algorytm ten stanowi modyfikację algorytmu TSAB, otrzymaną przez wykorzystanie oryginalnego przyspieszacza przeglądania sąsiedztwa oraz nowej techniki skoku powrotnego na trajektorii poszukiwań. Algorytm jest oparty na technice tabu z wykorzystaniem sąsiedztwa bazującego na blokach operacji ze ścieżki krytycznej. Przeprowadzone eksperymenty obliczeniowe (do 600 operacji) pokazują, że proponowany algorytm znajduje lepsze rozwiązania niż najlepsze znane do tej pory algorytmy w krótszym czasie, na komputerach o porównywalnej mocy obliczeniowej.

EN

The paper deals with the problem of finding a minimum makespan in a job shop. A fast and easily implemented approximation algorithm for this problem is presented. The proposed algorithm is a modification of algorithm TSAB, obtained by using original search accelerator and new technique of back jumps on the search trajectory. The algorithm is based on a tabu search technique with a specific neighborhood definition. A neighborhood is defined using blocks of operations on a critical path. Computational experiments (up to 600 operations) show that the algorithm not only finds shorter makespan than the best known up to now algorithms but also runs in shorter time.

5

Krajobraz przestrzeni rozwiązań problemu gniazdowego

Nowicki E., Makuchowski M.

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

|

2001

|

T. 5, z. 1/2

449-456

PL

W pracy bada się krajobraz przestrzeni rozwiązań problemu gniazdowego. Przedstawia się dwa typy ruchów (zamień i wstaw) oraz odpowiadające im miary odległości. Następnie dla różnych instancji problemu gniazdowego testuje się korelacje pomiędzy wartością funkcji celu lokalnego minimum, a jego średnią odległością od wszystkich innych badanych lokalnych minimów (lub odległością do najlepszego minimum lokalnego). Otrzymane rezultaty potwierdzają hipotezę, że zbiór lokalnych minimów ma strukturę "dużej doliny" oraz że jest umiejscowiony w obszarze stanowiącym bardzo niewielką część przestrzeni rozwiązań.

EN

The paper deals with the landscape of the solution space of the job shop problem. Two types of moves (swap and insert) are defined and the resulting distance metrics examined. Next, for instances of the job shop problem, the correlation between the cost of a local minimum and its average distance to all other local minima (as well as its distance to the best-found local minimum) is tested. Obtained results confirm hypothesis that the set of local minima has a "big valley" structure and is confined to a tiny portion of the solution space.