1. ¹The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
2. ²Shanghai University, Shanghai, China

Correspondence: TCE Cheng, Department of Logistics, The Hong Kong Polytechnic University, 11 Yuk Choi Road, Hung Hom, Kowloon, Hong Kong. E-mail: lgtcheng@polyu.edu.hk

Received October 2005; Accepted March 2006; Published online 5 July 2006.

Abstract

In this paper we study the problem of scheduling n deteriorating jobs on m identical parallel machines. Each job's processing time is a nondecreasing function of its start time. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of the due-date, earliness and tardiness penalties. We show that this problem is NP-hard, and we present a heuristic algorithm to find near-optimal solutions for the problem. When the due-date penalty is 0, we present a polynomial time algorithm to solve it.