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, logn} . n log n).