×

A special case of the single-machine total tardiness problem is NP-hard. (English) Zbl 1260.93116

J. Comput. Syst. Sci. Int. 45, No. 3, 450-458 (2006); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upr. 2006, No. 3, 120-128 (2006).
Summary: In this paper, it is shown that the special case B-1 of the single-machine total tardiness problem \(1\| \sum T_j\) is NP-hard in the ordinary sense. For this case, there exists a pseudo-polynomial algorithm with run time \(\mathcal{O}\left(n\cdot\sum p_j\right)\).

MSC:

93C83 Control/observation systems involving computers (process control, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. R. Garey and D. S. Johnson, Computers and Intractability: The Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982). · Zbl 0411.68039
[2] J. Du and J. Y. Leung, ”T. Minimizing Total Tardiness on One Processor is NP-Hard,” Math. Oper. Res, No. 15 (1990). · Zbl 0714.90052
[3] E. L. Lawler, ”A Pseudopolynomial Algorithm for Sequencing Jobs To Minimize Total Tardiness,” Ann. Discrete Math, No. 1 (1977). · Zbl 0353.68071
[4] W. Szwarc, F. Della Croce, and A. Grosso, ”Solution of the Single Machine Total Tardiness Problem,” J. Scheduling, No. 2 (1999). · Zbl 0963.90029
[5] W. Szwarc, A. Grosso, and F. Della Croce, ”Algorithmic Paradoxes of the Single-Machine Total Tardiness Problem,” J. Scheduling, No. 4 (2001). · Zbl 0994.90076
[6] C. N. Potts and L. N. Van Wassenhove, ”A Decomposition Algorithm for the Single-Machine Total Tardiness Problem,” Oper. Res. Lett, No. 1 (1982). · Zbl 0508.90045
[7] Croce F. Della, A. Grosso, and V. Paschos, ”Lower Bounds on the Approximation Ratios of Leading Heuristics for the Single-Machine Total Tardiness Problem,” J. of Scheduling, No. 7 (2004). · Zbl 1306.90048
[8] A. Lazarev, A. Kvaratskhelia, and A. Tchernykh, ”Solution Algorithms for the Total Tardiness Scheduling Problem on a Single Machine,” in Workshop Proceedings of the ENC’04 International Conference, Colima, Mexico, 2004, pp. 474–480.
[9] S. Chang, Q. Lu, G. Tang, and W. Yu, ”On Decomposition of Total Tardiness Problem,” Oper. Res. Lett, 17, 221–229 (1995). · Zbl 0858.90072 · doi:10.1016/0167-6377(95)00027-H
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.