Scheduling on parallel processors with varying processing times |
| |
| Affiliation: | 1. Department of Industrial Engineering, Universidad de Talca, Curicó, Chile;2. Department of Engineering and Sciences, Universidad Adolfo Ibáñez, Viña del Mar, Chile;1. Institut Mines-Télécom, Télécom Bretagne, Technopôle Brest Iroise, CS 83818, Brest Cedex 3 29238, France;2. UMR CNRS 6285 Lab-STICC, France;3. Chair of Naval Cyber Defense, Ecole navale – CC 600, Brest Cedex 9 F29240, France;1. Division of Mathematical Science for Social Systems, Department of Systems Innovation, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka city, Osaka 560-8531, Japan;2. Advanced Technology R&D Center, Mitsubishi Electric Corporation, 8-1-1 Tsukaguchi-honmachi, Amagasaki, Hyogo, 661-8661, Japan |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
