Abstract
We study inherent structural properties of a strongly NP-hard problem of scheduling \(n\) jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial-time algorithms. The first algorithm with the time complexity \(O(n^3\log n)\) solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is \(O(n^2\log n)\), which is an improvement over the earlier known algorithm with the time complexity \(O(n^5)\).
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
Brucker, P., & Knust S. Complexity results for scheduling problems (web page). http://www.mathematik.uniosnabrueck.de/research/OR/class/. Accessed 20 June 2012.
Carlier, J. (1981). Problèmes d’ordonnancement à durées égales. QUESTIO, 5, 219–228.
Chrobak, M., Durr, C., Jawor, W., Kowalik, L., & Kurowski, M. (2006). A note on scheduling equal-length jobs to maximize throughput. Journal of Scheduling, 9, 71–73.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman.
Garey, M. R., Johnson, D. S., Simons, B. B., & Tarjan, R. E. (1981). Scheduling unit-time tasks with arbitrary release times and deadlines. SIAM Journal on Computing, 10, 256–269.
Kravchenko, S., & Werner, F. (2011). Parallel machine problems with equal processing times: A survey. Journal of Scheduling, 14, 435–444.
Lawler, E. L. (1994). Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the tower of sets property. Mathematical Computer Modelling, 20, 91–106.
Moore, J. M. (1968). An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.
Vakhania, N. (2003). A better algorithm for sequencing with release and delivery times on identical processors. Journal of Algorithms, 48, 273–293.
Vakhania, N. (2008). Fast algorithms for preemptive scheduling of equal-length jobs on a single and identical processors to minimize the number of late jobs. International Journal of Mathematics and Computers in Simulation, 1, 95–100.
Vakhania, N. (2012). Branch less, cut more and minimize the number of late equal-length jobs on identical machines. Theoretical Computer Science, 465, 49–60.
Acknowledgments
This work was partially supported by CONACyT Grant 48433. Part of it was done when the author was visiting Laboratoire de Recherche en Informatique, Iniversité Paris-Sud, France and the author is grateful to Christoph Durr for his attention and comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has appeared in the proceedings of the 4th Multidisciplinary International Scheduling Conference (MISTA) 2009 (earlier, in a preliminary form, the result was reported on the workshop of Models and Algorithms for Planning and Scheduling Problems (MAPSP) 2005)
Rights and permissions
About this article
Cite this article
Vakhania, N. A study of single-machine scheduling problem to maximize throughput. J Sched 16, 395–403 (2013). https://doi.org/10.1007/s10951-012-0307-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-012-0307-8