| Autor: |
Oleg Valentinovich Melnikov, Kateryna Lishchuk, Elena Borisovna Misura, Alexander A. Pavlov, Iryna Mukha |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
Advances in Computer Science for Engineering and Education II ISBN: 9783030166205 |
| DOI: |
10.1007/978-3-030-16621-2_37 |
| Popis: |
We study the efficiency of polynomial approximation algorithms for solving NP-hard scheduling problems to minimize total tardiness and total weighted tardiness on one machine. The algorithms are based on PSC-algorithms for the considered problems given in [Zgurovsky & Pavlov, Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications, Springer, 2019]. They were developed by excluding procedures related to exponential enumeration. The approximation algorithms have a polynomial complexity and can solve problems of any practical dimension. We give a method for determining the maximum possible deviation of the approximate solution of the total tardiness problem from the optimum for each individual problem instance. We present experimental data on the solving time and the actual percentage of the deviation of the functional value from the optimum. The deviation was less than 5% after the execution of the approximate algorithm for the weighted tardiness problem and less than 2.4% for the total tardiness problem. This confirms the high efficiency of the approximation algorithms. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
