Scheduling on parallel processors with varying processing times
Radosław Rudek
Abstract
In this paper, we construct the pseudopolynomial dynamic programming algorithm that optimally solves the parallel identical processor scheduling problem to minimize the maximum job completion times (makespan) under varying processing times. They can be described by an arbitrary monotonic function dependent on the number of previously processed jobs, which can model learning or aging effects. Beside the canonical dynamic programming algorithm, we provide its efficient parallel fast version, which solves moderate problem instances of the problem within reasonable time and memory usage. Additionally, on the basis of the constructed algorithm, a fully polynomial time approximation scheme for the considered problem is provided. (C) 2016 Elsevier Ltd. All rights reservedAuthor | |||||
Journal series | Computers and Operations Research, ISSN 0305-0548, (A 35 pkt) | ||||
Issue year | 2017 | ||||
Vol | 81 | ||||
Pages | 90-101 | ||||
Publication size in sheets | 0.55 | ||||
Keywords in English | scheduling parallel processors, learning effect, aging effect, dynamic program ming, FPTAS | ||||
ASJC Classification | ; ; | ||||
DOI | DOI:10.1016/j.cor.2016.12.007 | ||||
URL | http://ac.els-cdn.com/S0305054816303069/1-s2.0-S0305054816303069-main.pdf?_tid=38731af4-1b6e-11e7-907f-00000aab0f6b&acdnat=1491554766_10a0c8eea8ab61dfaa472921bdc44d5b | ||||
Language | en angielski | ||||
File |
| ||||
Score (nominal) | 35 | ||||
Score | = 35.0, 20-08-2019, ArticleFromJournal | ||||
Publication indicators | = 2; : 2016 = 2.151; : 2017 = 2.962 (2) - 2017=3.174 (5) | ||||
Citation count* | 6 (2019-12-10) |
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back