Scheduling jobs under an aging effect

In this paper a scheduling problem that takes into consideration a phenomenoncalled ‘aging effect’ with reference to Computer Numerical Controldrilling or cutting machines is investigated. In the aftermath of this effect anexecution of jobs leads to a deterioration of a machine; thus processing timesof jobs increase and the production facility becomes less efficient. However, itis highly desirable to minimize the negative influence of this effect. Ingeneral, it can be done by formulating such a problem in the scheduling contextand optimizing an order of jobs to minimize the given criterion. Therefore, onthis basis a makespan minimization problem on a single machine with releasedates and the aging effect is formulated, where the job processing times aredescribed by non-decreasing functions dependent on fatigue (wear) of machine. Itis proved that even the special cases of the problem are NP-hard. Moreover, someproblems equivalences are shown and polynomially solvable cases are alsoprovided.