| Autor: |
Elena Borisovna Misura, Alexander A. Pavlov, Iryna Mukha, Kateryna Lishchuk, Oleg Valentinovich Melnikov |
| 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_43 |
| Popis: |
We present an approximation algorithm to solve the NP-hard scheduling problem of minimizing the total tardiness on identical parallel machines with a common due date and release dates of jobs. The algorithm has an estimate of the maximum possible deviation of its approximate solution from the optimum for each individual problem instance. It is based on the PSC-algorithm for the problem with equal release dates of jobs. Sufficient signs of optimality of a feasible solution and the estimate of the deviation of the obtained functional value from the optimum are known for the PSC-algorithm. The functional value obtained by the PSC-algorithm is the lower bound of the deviation of the functional value obtained by the approximation algorithm from the optimum for each individual problem instance. We give the computational data for test instances with dimensions of up to 40,000 jobs and 30 machines. The research shows that the developed algorithm is a very efficient method for the problem solving which allows to solve problems of any practical dimension. The average frequency of an optimal solution obtaining was 29.7%, and the average deviation from the optimum was 6.12%. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
