Skema > Faculty and Research > Publication-details





Exact algorithms for a single-machine scheduling problem with time windows and precedence constraints.
Erik Demeulemeester
Roel Leus
Fabrice Talla Nobibon
2016, Journal of Scheduling, 19, pp.309-334
Single-machine scheduling
Branch and bound
Mixed-integer programming
We study a single-machine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unit-time delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branch-and-bound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving medium-sized instances, and that it compares favorably with existing methods for special cases of the problem.

Why choose SKEMA?
At the top of French and international rankings SEE RANKINGS
A global business school SEE SKEMA NEWS
A wide range of programmes COMPARE