A note on scheduling jobs with equal processing times and inclusive processing set restrictions

Abstract

We consider the problem of scheduling n jobs on m parallel machines with inclusive processing set restrictions. Each job has a given release date, and all jobs have equal processing times. The objective is to minimize the makespan of the schedule. Li and Li (2015) have developed an O(n 2 +mn log n) time algorithm for this problem. In this note, we present a modified algorithm with an improved time complexity of O(min{m, log n} ⋅ n log n).