A Problem of Scheduling Jobs with Non-Monotonic Stepwise Values

Article type: Research Article

Authors: Janiak, Adam^; | Krysiak, Tomasz | Trela, Radosław

Affiliations: Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Janiszewskiego 11/17, 50-372 Wrocław, Poland, e-mail: adam.antoni.janiak@gmail.com, tomasz.a.krysiak@gmail.com, radoslaw.trela@pwr.wroc.pl

Note: [] Corresponding author.

Abstract: The paper deals with a parallel processor scheduling problem with changeable job values. Contrary to other papers in this area, we assume that job values are characterized by a non-monotonic stepwise functions of job completion times (previously only non-increasing functions have been considered). We give examples of real-life systems that can be modelled in such a way, in order to show that the problem is interesting from practical point of view. The problem is shown to be NP-hard and a pseudo-polynomial time algorithm for its special case is constructed. Moreover, a number of heuristic algorithms is provided and experimentally tested.

Keywords: scheduling, parallel processors, non-monotonic job value, pseudo-polynomial algorithm, heuristic

Journal: Informatica, vol. 25, no. 1, pp. 37-53, 2014