Sharif University of TechnologyScientia Iranica1026-309825120180201Single machine scheduling to minimize the maximum tardiness under piecewise linear deteriorating jobs370385440810.24200/sci.2017.4408ENAbbas-Ali JafariDepartment of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, IranM. M. LotfiDepartment of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, IranJournal Article20151209In many realistic production environments, jobs will take longer time if they begin later. This phenomenon is known as deteriorating jobs which have widely been studied. In this paper, the piecewise linear deterioration is discussed in a single machine scheduling problem of minimizing the maximum tardiness. After proving the <em>NP-hardness</em> of problem, a Branch and Bound and a heuristic algorithm with O(<em>n</em><sup>2</sup>) are proposed for solving the large scale problems to near optimal solutions. The heuristic approach is also used to determine an upper bound on the solution of B&B algorithm. The computational results for evaluating performance of the two algorithms confirm the excellent performance of B&B algorithm as it is able to solve the problems with at least 32 jobs within a reasonable time. Notably, the heuristic approach is quite accurate and efficient with an average error percentage of less than 0.3%.http://scientiairanica.sharif.edu/article_4408_ade9762f2cb7a30e00e16179d788070f.pdf