Abstract
Consider a set of n unit time jobs, each one having a release date, a due date, both nonnegative integers, and a weight, a positive real number. Given a set of m parallel machines, we describe an algorithm for finding schedules with minimum weighted number of tardy jobs. The complexity of the proposed algorithm is \(O(n^{2}\frac{(1+\log m)}{m})\) . The best previous algorithm for this problem has complexity O(mn 3) and employs network flow techniques. Our method is based on a characterization for schedules of this type and employs graph theoretic tools.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baptiste, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine when processing times are equal. Journal of Scheduling, 2, 245–252.
Baptiste, P., Brucker, P., Knust, S., & Timbkovsky, V. (2004). Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time. Quaterly Journal of the Belgian, French and Italian Operations Research Societies 4OR, 2, 111–127.
Brucker, P. (2004). Scheduling algorithms (4rd ed.). New York: Springer.
Brucker, P., & Knust, S. (2007). Complexity results for scheduling problems. http://www.mathematik.uni-osnabrueck.de/research/OR/class.
Brucker, P., & Kravchenko, S. (2006). Scheduling equal processing time jobs to minimize the weighted number of late jobs. Journal of Mathematical Modelling and Algorithms, 2, 245–252.
Brucker, P., Heitmann, S., & Hurink, J. (2003). How useful are preemptive schedules. Operational Research Letters, 31, 129–136.
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.
Graham, R., Lawler, E., Lenstra, J., & Rinnooy-Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326.
Lawler, E., & Moore, J. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16, 77–84.
Leung, J. (ed.) (2004). Handbook of scheduling: algorithms, models, and performance analysis. Computer and Information science series. London: Chapman& Hall.
Moore, J. (1968). A n job, one machine sequencing algorithm for minimizing the mumber of late jobs. Management Science, 15, 102–109.
Author information
Authors and Affiliations
Corresponding author
Additional information
R.F. Rodrigues was partially supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior—CAPES, Brazil.
J.L. Szwarcfiter was partially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico—CNPq, and Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro—FAPERJ, Brazil.
Rights and permissions
About this article
Cite this article
Dourado, M.C., Rodrigues, R.d.F. & Szwarcfiter, J.L. Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs. Ann Oper Res 169, 81–91 (2009). https://doi.org/10.1007/s10479-008-0479-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0479-y