Abstract
This paper re-examines the classical problem of minimizing maximum lateness which is defined as follows: given a collection of n jobs with processing times and due dates, in what order should they be processed on a single machine to minimize maximum lateness? The lateness of a job is defined as its completion time minus its due date. This problem can be solved easily by ordering the jobs in non-decreasing due date order. We now consider the following question: which subset of k jobs should we reject to reduce the maximum lateness by the largest amount? While this problem can be solved optimally in polynomial time, we show the following surprising result: there is a fixed permutation of the jobs, such that for all k, if we reject the first k jobs from this permutation, we derive an optimal solution for the problem in which we are allowed to reject k jobs. This allows for an incremental solution in which we can keep incrementally rejecting jobs if we need a solution with lower maximum lateness value. Moreover, we also develop an optimal O(n logn) time algorithm to find this permutation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM J. Discrete Math. 13(1), 64–78 (2000)
Chrobak, M., Kenyon, C., Noga, J., Young, N.E.: Oblivious medians via online bidding. In: Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 311–322 (2006)
Engels, D.W., Karger, D.R., Kolliopoulos, S.G., Sengupta, S., Uma, R.N., Wein, J.: Techniques for scheduling with rejection. J. Algorithms 49(1), 175–191 (2003)
Epstein, L., Noga, J., Woeginger, G.J.: On-line scheduling of unit time jobs with rejection: minimizing the total completion time. Operations Research Letters 30(6), 415–420 (2002)
Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoretical Computer Science 38, 293–306 (1985)
Hall, L.A.: Approximation Algorithms for NP-Hard Problems, ch. 2. PWS Publishing Company (1997)
Hoogeveen, H., Skutella, M., Woeginger, G.J.: Preemptive scheduling with rejection. Mathematical Programming 94(2-3), 361–374 (2003)
Lin, G., Nagarajan, C., Rajaraman, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1147–1156 (2006)
Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM Journal on Computing 32(3), 816–832 (2003)
Seiden, S.S.: Preemptive multiprocessor scheduling with rejection. Theor. Comput. Sci. 262(1), 437–458 (2001)
Sengupta, S.: Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. In: Proceedings of the 15th International Workshop on Algorithms and Data Structures, pp. 79–90 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khuller, S., Mestre, J. (2008). An Optimal Incremental Algorithm for Minimizing Lateness with Rejection. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_50
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)