Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs

Management Science · 1988 · Volume 34 · Issue 7

Abstract

This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O ( n log n ) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given.

Keywords

scheduling, reduction, dynamic programming, branch and bound

Enable JavaScript for citation tools and additional paper interactions.