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 reserved