- Tytuł:
- Improving the TSAB algorithm through parallel computing
- Autorzy:
-
Rudy, Jarosław
Pempera, Jaroslaw
Smutnicki, Czesław - Powiązania:
- https://bibliotekanauki.pl/articles/229535.pdf
- Data publikacji:
- 2020
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Tematy:
-
job shop scheduling
parallel computing
operations research
taboo search
TSAB algorithm
coarse-grained parallelization - Opis:
- In this paper, a parallel multi-path variant of the well-known TSAB algorithm for the job shop scheduling problem is proposed. Coarse-grained parallelization method is employed, which allows for great scalability of the algorithm with accordance to Gustafon’s law. The resulting P-TSAB algorithm is tested using 162 well-known literature benchmarks. Results indicate that P-TSAB algorithm with a running time of one minute on a modern PC provides solutions comparable to the ones provided by the newest literature approaches to the job shop scheduling problem. Moreover, on average P-TSAB achieves two times smaller percentage relative deviation from the best known solutions than the standard variant of TSAB. The use of parallelization also relieves the user from having to fine-tune the algorithm. The P-TSAB algorithm can thus beused as module in real-life production planning systems or as a local search procedure in other algorithms. It can also provide the upper bound of minimal cycle time for certain problems of cyclic scheduling.
- Źródło:
-
Archives of Control Sciences; 2020, 30, 3; 411-435
1230-2384 - Pojawia się w:
- Archives of Control Sciences
- Dostawca treści:
- Biblioteka Nauki
Artykuł