Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints 2: Near the Optimal Ratio, a Maximum-Weight Initial Set Is ρ-MaximalResearch Paper
The single-machine sequencing problem with precedence constraints, written , asks for an order of jobs on one machine that respects a given acyclic digraph of precedences and minimizes the weighted sum of completion times. It is NP-hard in general (Lawler 1978; Lenstra and Rinnooy Kan 1978), and much of its structural…