×

Due-date assignment and single machine scheduling with deteriorating jobs. (English) Zbl 1095.90036

Summary: We study a scheduling problem with deteriorating jobs, that is, jobs whose processing times are an increasing function of their start times. We consider the case of a single machine and linear job-independent deterioration. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of due-date, earliness and tardiness penalties. We give an \(\text{O}(n \log n)\) time algorithm to solve this problem.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI Link