Minimizing total completion time with linear deterioration: A new lower bound

We study scheduling problems in which the job processing times are linearly deteriorating. Each job has a constant (job-independent) basic processing time and a job-dependent deterioration rate. The objective function is minimum total completion time. The machine settings considered are: single machine and parallel identical machines. The complexity status of these problems has been an open question for the last three decades. We introduce a new lower bound on the optimal total completion time, which is shown numerically (through a comparison to the results obtained by a simple heuristic) to be extremely accurate for both problems.

Automated summary

This study focuses on scheduling problems with linearly deteriorating job processing times, introducing a new lower bound on optimal total completion time that proves to be highly accurate through numerical comparisons. The complexity status of single machine and parallel identical machine settings in these problems has been an open question for the last thirty years.