single Machine Preemptive Scheduling With Special Cost Functions1

What is it about?

We consider a single machine scheduling problem, where for each job a release date, a processing time and a cost function are given and the maximum cost is to be minimized. Preemption is allowed and precedence constraints among the jobs are given. For this problem, a polynomial algorithm with quadratic complexity in the number of jobs is known from the literature. We consider cost functions with a special order relation: for any two jobs the cost of one job is not greater than the cost for the other job during the whole scheduling period. Many objective functions usually considered in scheduling theory have this property. For those problems we propose an algorithm with reduced complexity for the case of tree-like precedence constraints. Moreover, we give a parallel algorithm for this class of problems.

Featured Image