A Problem of Scheduling Jobs with Non-Monotonic Stepwise Values

作者：Janiak Adam^*; Krysiak Tomasz; Trela Radoslaw

来源：Informatica, 2014, 25(1): 37-53.

DOI：10.15388/informatica.2014.03

• scheduling
• parallel processors
• non-monotonic job value
• pseudo-polynomial algorithm
• heuristic

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.

• 出版日期2014