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

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

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)402-412
JournalINFORMS Journal on Computing
Volume8
Issue number4
DOIs
Publication statusPublished - 1996

Fingerprint

Scheduling
Branch and bound algorithm
Tardiness
Single machine
Lower bounds

Cite this

Hoogeveen, J.A. ; Velde, van de, S.L. / A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. In: INFORMS Journal on Computing. 1996 ; Vol. 8, No. 4. pp. 402-412.
@article{88d0b14bd2d849c284c9160a88c417df,
title = "A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time",
abstract = "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 {\ss} times total earliness with {\ss} > , 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.",
author = "J.A. Hoogeveen and {Velde, van de}, S.L.",
year = "1996",
doi = "10.1287/ijoc.8.4.402",
language = "English",
volume = "8",
pages = "402--412",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "4",

}

A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. / Hoogeveen, J.A.; Velde, van de, S.L.

In: INFORMS Journal on Computing, Vol. 8, No. 4, 1996, p. 402-412.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Hoogeveen, J.A.

AU - Velde, van de, S.L.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

U2 - 10.1287/ijoc.8.4.402

DO - 10.1287/ijoc.8.4.402

M3 - Article

VL - 8

SP - 402

EP - 412

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 4

ER -