An exact algorithm and a heuristic for scheduling linearly deteriorating jobs with arbitrary precedence constraints and the maximum cost criterion

We consider the problem of scheduling linearly deteriorating jobs on a single machine. Between the jobs there are defined arbitrary precedence constraints and the objective is to minimize the maximum cost. For this problem we propose an exact algorithm and a heuristic. We also report preliminary results of computational experiments conducted in order to evaluate the quality of schedules generated by the heuristic.