A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time

J.A. Hoogeveen, S.L. Velde, van de

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

We address the NP-hard single-machine problem of scheduling n independent jobs so as to minimize the sum of times total completion time and ß times total earliness with ß > , which can be rewritten as an earliness–tardiness problem. Postponing jobs by leaving the machine idle may then be advantageous. The allowance of machine idle time between the execution of jobs singles out our problem from most concurrent research on problems with earliness penalties. Solving the problem to optimality poses a computational challenge, since the possibility of leaving the machine idle has a major effect on designing a branch-and-bound algorithm in general, and on computing lower bounds in particular. We present a branch-and-bound algorithm which is based upon many dominance rules and various lower bound approaches, including relaxation of the machine capacity, data manipulation, and Lagrangian relaxation. The algorithm is shown to solve small instances with up to 20 jobs.
Originele taal-2Engels
Pagina's (van-tot)402-412
TijdschriftINFORMS Journal on Computing
Volume8
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 1996

Vingerafdruk

Duik in de onderzoeksthema's van 'A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time'. Samen vormen ze een unieke vingerafdruk.

Citeer dit