Title: Minimising maximum lateness in a single machine scheduling problem with processing time-based aging effects
Authors: Radosław Rudek
Addresses: Wrocław University of Economics, Komandorska 118/120, 53-345 Wrocław, Poland
Abstract: 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]
Keywords: single machine scheduling; deterioration; aging effects; computational complexity; branch and bound; B&B; metaheuristics; maximum lateness.
European Journal of Industrial Engineering, 2013 Vol.7 No.2, pp.206 - 223
Published online: 12 Mar 2013 *Full-text access for editors Access for subscribers Purchase this article Comment on this article