Evaluation of the expected makespan of a set of non-resumable jobs on parallel machines with stochastic failures

• Simultaneous maintenance and production scheduling.
• Exact computation of the expected makespan for non-resumable jobs in case of stochastic machine failures.
• Reveal the complexity of the problem and the objective function.
• Derivation of two approximations of the objective function with excellent performance.

In this paper we consider a production process at operative level on mm identical parallel machines, which are subject to stochastic machine failures. To avoid long downtime of the machines, caused by unexpected failures, preventive maintenance activities are planned and conducted, but if a failure could not be averted a corrective maintenance has to be performed. Both maintenance activities are assumed to restore the machine to be “as good as new”. The maintenance activities, the number of jobs and their allocation to machines as well as their sequence have a large impact on the performance of the production process and the delivery dates.We study an order of nn jobs, scheduled for a frozen period on the machines. It is assumed that jobs, interrupted by machine failure, have to get repeated right after the corrective maintenance is finished (non-resumable case). We first derive an exact formula for the expected makespan. Since the exact evaluation of a schedule is highly complex, we propose two approximations for the expected makespan. The excellent performance of the approximations is illustrated in a numerical study.