Using lagrangean relaxation to minimize the (weighted) number of late jobs on a single machine
Abstract
This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed-integer linear programming formulation. By relaxing some constraints, it is possible to design a Lagrangean relaxation algorithm which gives both lower and upper bounds. The special case where jobs have equal weights is analyzed. Computational results are presented and, although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs.
Publisher
Norwegian School of Economics and Business Administration. Department of Finance and Management ScienceSeries
Discussion paper1999:8