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
Author Radosław Rudek (MISaF / IBI / DIT)
Radosław Rudek,,
- Department of Information Technologies
Journal seriesComputers and Operations Research, ISSN 0305-0548, (A 35 pkt)
Issue year2017
Vol81
Pages90-101
Publication size in sheets0.55
Keywords in Englishscheduling parallel processors, learning effect, aging effect, dynamic program ming, FPTAS
ASJC Classification1803 Management Science and Operations Research; 2611 Modelling and Simulation; 1700 General Computer Science
DOIDOI: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
Languageen angielski
File
Rudek_Scheduling_on_parellel2017.pdf 1,42 MB
Score (nominal)35
ScoreMinisterial score = 35.0, 20-08-2019, ArticleFromJournal
Publication indicators Scopus Citations = 2; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 2.151; WoS Impact Factor: 2017 = 2.962 (2) - 2017=3.174 (5)
Citation count*6 (2019-12-10)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back