Abstract
This paper deals with a particular scheduling problem. We consider unit-time jobs and in-tree precedence constraints while minimizing the mean flow time. This problem is observed as \(P|p_{j}=1,\text {in-tree}|\sum C_{j}\) with the use of the 3-filed notation. To the best of our knowledge, its complexity is still open. Through a reduction from 3-Partition, we show that this problem is strongly \( \mathcal {NP} \)-hard.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Baptiste, P., & Timkovsky, V. G. (2001). On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Operations Research Letters, 28(5), 205–212.
Baptiste, P., Brucker, P., Knust, S., & Timkovsky, V. G. (2004). Ten notes on equal-processing-time scheduling. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2(2), 111–127.
Brucker, P., Hurink, J., & Knust, S. (2003). A polynomial algorithm for \({P}|p_j=1, r_j, outtree|\sum {C}_j\). Mathematical Methods of Operations Research, 56(3), 407–412.
Garey, M., Johnson, D., Tarjan, R., & Yannakakis, M. (1983). Scheduling opposing forests. SIAM Journal on Algebraic Discrete Methods, 4(1), 72–93.
Garey, M. R., & Johnson, D. S. (2002). Computers and intractability (Vol. 29). New York: W. H. Freeman.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.
Hu, T. C. (1961). Parallel sequencing and assembly line problems. Operations Research, 9(6), 841–848.
Huo, Y., & Leung, J. Y.-T. (2006). Minimizing mean flow time for UET tasks. ACM Transactions on Algorithms (TALG), 2(2), 244–262.
Prot, D., & Bellenguez-Morineau, O. (2018). A survey on how the structure of precedence constraints may change the complexity class of scheduling problems. Journal of Scheduling, 21(1), 3–16.
Sigrid, K., & Peter, B. (2009). Complexity results for scheduling problems. http://www2.informatik.uni-osnabrueck.de/knust/class/. Accessed 15 May 2017.
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (4th ed., p. 22). Springer.
Acknowledgements
This work was supported by the China Scholarship Council [grant numbers 201404490037].
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Wang, T., Bellenguez-Morineau, O. A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time. J Sched 22, 709–714 (2019). https://doi.org/10.1007/s10951-019-00602-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-019-00602-0