Minimizing Weighted Completion Times with Deadlines

Abstract

We examine a one-machine scheduling problem whose objective is to minimize the weighted sum of completion times, subject to deadline constraints. We synthesize and extend current known theory, and derive precedence relations between jobs. These relationships, along with tight new bounding criteria, are incorporated in a branch and bound solution procedure.