Parallel machine scheduling with maintenance activities

- Parallel machine scheduling with maintenance activity.
- Makespan, sum of completion times, maximum lateness and sum of lateness.
- For each scheduling measure, the problem is proved to be strongly NP-hard.
- Some restricted cases are also characterized for their complexities.

This paper considers a problem of scheduling on parallel machines where each machine requires maintenance activity once over a given time window. The objective is to find a coordinated schedule for jobs and maintenance activities to minimize the scheduling cost represented by either one of several objective measures including makespan, (weighted) sum of completion times, maximum lateness and sum of lateness. The problem is proved to be NP-hard in the strong sense in each case of the objective measures. Some restricted cases of the problem are also characterized for their complexities, for which the associated dynamic programming algorithms are derived.