Lawler, E. L. Sequencing to minimize the weighted number of tardy jobs. (English) Zbl 0333.68044 Rev. Franc. Automat. Inform. Rech. Operat., Suppl. to 10, B-2, 27-33 (1976). Suppose \( n \) jobs are to be processed by a single machine. A fixed processing time \( p_{j} \), a deadline \( d_{j} \) and a weight \( w_{j} \) are associated with each job \( j \). The problem is to find a sequence which minimizes the sum of the weights of tardy jobs. It is shown that if the weighting of the jobs is ”agreeable”, in the sense that \( p_{1}<p_{j} \) implies \( w_{1} \geq w_{j} \), then an optimal sequence can be constructed by an algorithm with \( O(n \log n) \) running time. This provides a common generalization of the case in which all weights are equal, previously solved by J. M. M \( \circ \circ \mathrm{r} e \) [Management Sci., Theory 15, 102-109 (1968; Zbl. 164, 200)] and the case in which all processing times are equal, which is solvable as an assignment problem. The problem of optimally scheduling jobs with equal processing times on \( \mathrm{m} \) identical parallel processors can also be solved by a variant of the same algorithm in \( O(n \log n) \) running time. This review text is based on a scanned copy of the printed version. It was converted to LaTeX using MathPix and a specifically developed LLM to assign the text parts to the metadata. It may contain errors, misassignments, or gaps; in particular, the reviewer signature has not yet been extracted reliably in general. If you notice any errors, please report them directly to our editorial team via the Contact Form. Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 22 Documents MSC: 68Q45 Formal languages and automata 68W99 Algorithms in computer science 68Q25 Analysis of algorithms and problem complexity × Cite Format Result Cite Review PDF