L’ordonnancement sur une machine avec des contraintes de delai

Abstract

In this paper we deal with a one-machine scheduling problem to minimize the weighted sum of completion times, subject to deadline constraints. The aim of this study is to present the problem as a mixed integer problem, soluble by a mathematical programming system. Special attention has been paid to finding a formulation of which the linear relaxation is offering a tower bound close to the optimal value, which is the essential difficulty with that kind of problems. A lower bounding procedure using dominance properties and valid inequalities is used in a branch and bound algorithm. The algorithm is tested on problems with up to 30 jobs.