George Karakostas
Abstract
Given a sequencing of jobs on a single machine, each one with a weight, processing time, and a due date, the tardiness of a job is the time needed for its completion beyond its due date. We present an FPTAS for the basic scheduling problem of minimizing the total weighted tardiness when the number of distinct due dates is fixed. Previously, an FPTAS was known only for the case where all jobs have a common due date.
- Abdul-Razaq, T. S., Potts, C. N., and Wassenhove, L. N. V. 1990. A survey of algorithms for the single machine total weighted tardiness scheduling problem. Disc. Appl. Math. 26, 235--253. Google Scholar
Digital Library
- Bansal, N. and Pruhs, K. 2010. The geometry of scheduling. In Proceeding of 51st Annual IEEE Symposium on Foundations of Computer Science, (FOCS). 407--414. Google ScholarDigital Library
- Cheng, T. C. E., Ng, C. T., J.Yuan, J., and Liu, Z. H. 2005. Single machine scheduling to minimize total weighted tardiness. Euro. J. Oper. Res. 165, 423--443.Google ScholarCross Ref
- Du, J. and Leung, J. Y.-T. 1990. Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. 15, 483--495. Google ScholarDigital Library
- Kacem, I. 2010. Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date. Dis. Appl. Math. 158, 9, 1035--1040. Google ScholarDigital Library
- Karakostas, G., Kolliopoulos, S. G., and Wang, J. 2009. An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates. In Proceedings of 15th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science,vol. 5609, Springer Verlag, 238--248. Google ScholarDigital Library
- Kellerer, H. and Strusevich, V. A. 2006. A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date. Theort. Comput. Sci. 369, 230--238. Google ScholarDigital Library
- Kolliopoulos, S. G. and Steiner, G. 2006. Approximation algorithms for minimizing the total weighted tardiness on a single machine. Theoret. Comput. Sci. 355, 3, 261--273. Google ScholarDigital Library
- Lawler, E. L. 1977. A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Ann. Disc. Math. 1, 331--342.Google ScholarCross Ref
- Lawler, E. L. 1982. A fully polynomial approximation scheme for the total tardiness problem. Oper. Res. Lett. 1, 207--208. Google ScholarDigital Library
- Lawler, E. L. and Moore, J. M. 1969. A functional equation and its application to resource allocation and sequencing problems. Manage. Sci. 16, 77--84.Google ScholarDigital Library
- Lenstra, J. K., Kan, A. H. G. R., and Brucker, P. 1977. Complexity of machine scheduling problems. Ann. Disc. Math. 1, 343--362.Google ScholarCross Ref
- McNaughton, R. 1959. Scheduling with due dates and loss functions. Manage. Scie. 6, 1--12.Google ScholarDigital Library
- Sen, T., Sulek, J. M., and Dileepan, P. 2003. Static scheduling research to minimize weighted and unweighted tardiness: a state-of-the-art survey. Int. J. Production Econom. 83, 1--12.Google ScholarCross Ref
- Yuan, J. 1992. The NP-hardness of the single machine common due date weighted tardiness problem. Syst. Sci. Math. Sci. 5, 328--333.Google Scholar
Index Terms
- An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates
Recommendations
Flow shop scheduling with two distinct job due dates
Highlights- Flow shop scheduling problems with two distinct job due dates.
- Solvability with ...
AbstractWe consider flow shop scheduling problems with two distinct job due dates. Motivated by the NP-hardness of these problems with arbitrary job processing times, we focus on their solvability with ordered or proportionate job processing ...
Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
This paper deals with the total weighted tardiness minimization with a common due date on a single machine. The best previous approximation algorithm for this problem was recently presented in [H. Kellerer, V.A. Strusevich, A fully polynomial ...
Approximation algorithms for minimizing the total weighted tardiness on a single machine
Given a single machine and a set of jobs with due dates, the classical NP-hard problem of scheduling to minimize total tardiness is a well-understood one. Lawler gave a fully polynomial-time approximation scheme (FPTAS) for it some 20 years ago. If the ...
Reviews
Soubhik Chakraborty
Imagine a single machine and several jobs to be completed sequentially on it, each job having a characteristic weight, processing time, and a prescribed due date of completion. Then, the tardiness of a job is defined as the time taken beyond its due date for the job to be completed. The authors present an interesting paper on this scheduling problem in which they provide a fully polynomial-time approximation scheme (FPTAS) that minimizes the total weighted tardiness. The newness of their algorithm stems from the revelation that it works even for separate or distinct (although fixed) due dates. Previous known FPTAS algorithms only worked for common due dates. The proposed pseudo-polynomial scheme has two broad steps. In the first step, dynamic programming is used to evaluate the completion times of different jobs in the schedule. In the authors' own words, "only a subset of the jobs is explicitly packed and the rest are left 'floating' from their completion time backwards," producing what the authors call "an abstract schedule." In the second step, the actual job lengths are distributed by means of a greedy algorithm. The authors' work is motivated by the work of Kellerer and Strusevich [1]. The authors propose extending their work to an arbitrary number of distinct due dates. I would add that since the time of an operation is itself the weight in some sense, one should regard the processing time as a weighted combination of the operations; hence, this can be combined with the other weight talked about in the paper. We may call the result a "g-weight," a generalized version of the weights. This puts the problem in its most general form. I recommend this paper for the target audience, which includes computing science graduates and researchers, especially those interested in algorithms. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments