Single machine scheduling with time deteriorating job values

This paper considers the problem of scheduling n jobs on a single machine where the job value deteriorates with its starting time. The objective of the problem is to maximize the cumulative value of all jobs. The problem is motivated from the real-life applications, such as movie scheduling, remanufacturing of high-technology products, Web object transmission, and banner advertising. Unrestricted, truncated, and capacity constrained job value functions are considered. Some special cases of the problem, such as the unrestricted linear job value function, are polynomially solvable. The general problem is shown to be unary NP-hard and is modelled as a time index integer program. For the NP-hard cases, several heuristics are proposed.