Informatica

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.