1. ¹Indian Institute of Technology, Kanpur, India
2. ²University of Alabama in Huntsville, Huntsville, AL, USA

Correspondence: JND Gupta, College of Administrative Science, University of Alabama in Huntsville, Huntsville, AL 35899, USA. E-mail: guptaj@uah.edu

Received February 2006; Accepted June 2006; Published online 1 November 2006.

Abstract

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. Results of the empirical evaluation of the relative performance of the proposed heuristics on critical parameters are reported.