¹Shenyang Institute of Aeronautical Engineering, Shenyang, People's Republic of China

Correspondence: J-B Wang, Department of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People's Republic of China. E-mail: wangjibo75@yahoo.com.cn

Received January 2007; Accepted January 2008; Published online 14 May 2008.

Abstract

The paper deals with the single machine scheduling problems with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the processing time of a job is defined by function of its starting time and total normal processing time of jobs in front of it in the sequence. It is shown that even with the introduction of a time-dependent learning effect and deteriorating jobs to job processing times, the single machine makespan minimization problem remain polynomially solvable. But for the total completion time minimization problem, the classical shortest processing time first rule or largest processing time first rule cannot give an optimal solution.