Scheduling proportionate flow shops with preventive machine maintenance

We examine machine scheduling problems that have been inspired by the production environment of semiconductor manufacturing. In semiconductor manufacturing a job processing machine is often enforced to go through a preventive maintenance operation with an objective of minimizing the wafer quality risk. In this research such periodic machine maintenance is considered for single machine and flow shop scheduling models. For the flow shop model we focus on an important special case with proportionate processing times. We first present that the maximum lateness and the total completion time in a single machine can be minimized by a monotone scheduling rule. For the maximum lateness it is shown that the scheduling rule of a single machine special case is also optimal for a proportionate flow shop. However, for the total completion time we observe that the scheduling algorithm of a single machine is not necessarily optimal for its extension to a proportionate flow shop. We prove that the total completion time in a proportionate flow shop is solvable by an O(n(2)) algorithm, and even the total weighted completion time is minimized with the same computational complexity. Lastly, we discuss how these results are further generalized when setup operations are additionally considered.

Automated summary

This research focuses on machine scheduling problems inspired by semiconductor manufacturing, considering periodic machine maintenance in single machine and flow shop scheduling models with proportionate processing times. The study shows that maximum lateness and total completion time in a single machine can be minimized using a monotone scheduling rule, and that the same rule is optimal for a proportionate flow shop in terms of maximum lateness. However, it is found that the scheduling algorithm for a single machine may not necessarily be optimal for a proportionate flow shop in terms of total completion time. It is proven that a proportionate flow shop can be solved with an O(n(2)) algorithm for total completion time, and even total weighted completion time can be minimized with the same computational complexity. Furthermore, the generalization of these results is discussed when considering additional setup operations.