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.

DOI: 10.1504/EJIE.2013.052575

European Journal of Industrial Engineering, 2013 Vol.7 No.2, pp.206 - 223

Published online: 28 Feb 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article