Minimising maximum lateness in a single machine scheduling problem with processing time-based aging effects

In this paper, we analyse the single machine maximum lateness minimisation scheduling problem with the aging effect, where the job processing times are described by non-decreasing functions dependent on the sum of the normal processing times of already processed jobs. We prove that the considered problem is at least NP-hard even if job processing times are described by linear functions. Moreover, we construct the branch and bound method and implement well known approximation algorithms for the general version of the problem and verify numerically their efficiency. [Received 18 February 2011; Revised 26 May 2011, 3 September 2011; Accepted 12 September 2011]