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).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Knuth DE (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. 2nd edn Addison-Wesley: Reading, MA.
Leung JY-T and Li C-L (2008). Scheduling with processing set restrictions: A survey. International Journal of Production Economics 116 (2): 251–262.
Li C-L and Li Q (2015). Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions. Journal of the Operational Research Society 66 (3): 516–523.
Ou J, Zhong X and Li C-L (2015). Improved algorithms for single machine scheduling with release dates and rejection. Submitted for publication.
Acknowledgements
Chung-Lun Li was supported in part by The Hong Kong Polytechnic University under grant 1-BBZL. Kangbok Lee was supported in part by PSC CUNY (The City University of New York) Grant TRADA-46-477.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, CL., Lee, K. A note on scheduling jobs with equal processing times and inclusive processing set restrictions. J Oper Res Soc 67, 83–86 (2016). https://doi.org/10.1057/jors.2015.56
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2015.56