Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959063 | Computers & Operations Research | 2017 | 30 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
RadosÅaw Rudek,