Using lagrangean relaxation to minimize the weighted number of late jobs

International audienceThis 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. By relaxing some constraints, it is possible to propose a Lagrangean relaxation algorithm which gives both a lower and upper bound. Although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs, and some computational results are presented