×

Minimizing the number of tardy job units under release time constraints. (English) Zbl 0707.90049

Two single-machine scheduling problems are considered: minimizing the weighted and unweighted number of tardy units, when release times are present. Fast strongly polynomial algorithms are given for both problems: for problems with n jobs, algorithms which require O(n log n) and \(O(n^ 2)\) steps, for the unweighted and weighted problems are given, respectively. These results imply an extension of the family of very efficiently solvable transportation problems, as well as of those which are greedily solvable using the “Monge sequence” idea.
Reviewer: R.Slowinski

MSC:

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Cosares, S.; Hochbaum, D.; Shamir, R., An algorithm for the detection and construction of Monge sequences, Linear Algebra Appl., 114/115, 669-680 (1989) · Zbl 0666.65044
[2] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[3] Dietrich, B. L., Monge sequences, antimatroids, and the transportation problem with forbidden arcs, Rept. (1989), IBM T.J. Watson Research Center · Zbl 0703.90063
[4] Gabow, H. N.; Tarjan, R. E., A linear-time algorithm for a special case of disjoint set union, J. Comput. System Sci., 30, 209-221 (1985) · Zbl 0572.68058
[5] Hochbaum, D. S.; Shamir, R., Strongly polynomial algorithms for the high multiplicity scheduling problem, Rept. TR-100⧸88 (1988), Computer Science Institute, Tel Aviv University: Computer Science Institute, Tel Aviv University Tel Aviv, also: Oper. Res., to appear.
[6] Hoffman, A., On simple transportation problems, (Klee, V., Convexity, Proceedings of Symposia in Pure Mathematics, 7 (1963), Amer. Math. Soc: Amer. Math. Soc Providence, RI), 317-327
[7] A. Hoffman, Private communication.; A. Hoffman, Private communication.
[8] Orlin, J. B., A faster strongly polynomial miminum cost flow algorithm, Proceedings 20th ACM Symposium of the Theory of Computing, 377-387 (1988)
[9] Shamir, R., A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs, Rept. 136/89 (1989), Institute of Computer Science, Tel Aviv University: Institute of Computer Science, Tel Aviv University Tel Aviv, also: Discrete Math., to appear
[10] Tardos, E., A strongly polynomial minimum cost circulation algorithm, Combinatorica, 5, 247-255 (1985) · Zbl 0596.90030
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.