Partial dominated schedules and minimizing the total completion time of deteriorating jobs

A problem of scheduling deteriorating jobs on a single processor is considered. The processing time pi of a job i is given by a function p(i) = a(i) + b(i)s(i), where s(i) is the starting time of the job, a(i) >= 0, b(i) >= 0, for i = 1, ... , n. Jobs are non-preemptive and independent and there are neither ready times nor deadlines. The goal is to minimize the total weighted completion time. We show how to employ the concept of non-dominated schedules to construct an exact algorithm for the problem. We also consider extending the algorithm to solve problems with precedence constraints and finding all Pareto-optimal solutions. Then we present how to use the concept to the problem 1(vertical bar)p(i) = a + b(i)s(i)vertical bar Sigma C-i. We use elimination of dominated partial schedules to improve the efficiency of a branch-and-bound algorithm and present another algorithm, based solely on the elimination of dominated partial schedules.