Scheduling jobs under an aging effect

In this paper a scheduling problem that takes into consideration a phenomenon called ‘aging effect’ with reference to Computer Numerical Control drilling or cutting machines is investigated. In the aftermath of this effect an execution of jobs leads to a deterioration of a machine; thus processing times of jobs increase and the production facility becomes less efficient. However, it is highly desirable to minimize the negative influence of this effect. In general, it can be done by formulating such a problem in the scheduling context and optimizing an order of jobs to minimize the given criterion. Therefore, on this basis a makespan minimization problem on a single machine with release dates and the aging effect is formulated, where the job processing times are described by non-decreasing functions dependent on fatigue (wear) of machine. It is proved that even the special cases of the problem are NP-hard. Moreover, some problems equivalences are shown and polynomially solvable cases are also provided.