1976/01/01 by Sartaj Sahni · 6 citations
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Search Problems #Distributed and Parallel Computing Systems
paper · pdf · doi:10.1145/321921.321934
openalex publication_date 1976/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/01
The following job sequencing problems are studied: (i) single processor job sequencing with deadlines, (ii) job sequencing on m -identical processors to minimize finish time and related problems, (iii) job sequencing on 2-identical processors to minimize weighted mean flow time. Dynamic programming type algorithms are presented to obtain optimal solutions to these problems, and three general techniques are presented to obtain approximate solutions for optimization problems solvable in this way. The techniques are applied to the problems above to obtain polynomial time algorithms that generate “good” approximate solutions.