Scheduling Jobs with a Stepwise Function of Change of Their Values

The paper deals with a single processor scheduling problem in which the sum of values of all the jobs is maximized. The job value is characterized by a stepwise non-increasing function with one or more moments at which a change of job value occur. Establishing an order of processing of datagrams which are sent by router is a practical example of application of this problem. It is proved in the paper, that a special case of the considered problem — with a single common moment of job value change and zero value of jobs after this moment — is NP-hard. Therefore, a pseudo-polynomial time algorithm for the case with common moments of job value change is constructed. It is also constructed and experimentally tested a number of heuristic algorithms which solve the general version of the problem.