Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 81, Issue -, Pages 90-101Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2016.12.007
Keywords
Scheduling; Parallel processors; Learning effect; Aging effect; Dynamic programming; FPTAS
Categories
Funding
- Polish National Science Centre [DEC-2012/05/D/HS4/01129]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available