The Hebrew University, Jerusalem, Israel

Correspondence: G. Mosheiov, School of Business Administration and Department of Statistics, The Hebrew University, Jerusalem, Israel

Received September 1995; Accepted February 1996.

Abstract

We study a problem of scheduling deteriorating jobs, i.e. jobs whose processing times are an increasing function of their starting times. We consider the case of a single machine and linear job-independent deterioration. The objective is to minimize the sum of weighted completion times, with weights proportional to the basic processing times. The optimal schedule is shown to be -shaped, i.e. the sequence of the basic processing times has a single local maximum. Moreover, we show that the problem is solved in O(N log N) time. In the last section we test heuristics for the case of general weights.