Single-machine scheduling with release dates, due dates and family setup times

J.M.J. Schutten, S.L. van de Velde, W.H.M. Zijm

Research output: Contribution to journalArticleAcademicpeer-review

35 Citations (Scopus)
57 Downloads (Pure)

Abstract

We address the NP-hard problem of scheduling n independent jobs with release dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery performance, between maximizing machine utilization by batching similar jobs and maximizing customers' satisfaction by completing jobs before their due dates. We develop a branch-and-bound algorithm, and our computational results show that it solves almost all instances with up to about 40 jobs to optimality. The main algorithmic contribution is our lower bounding strategy to deal with family setup times. The key idea is to see a setup time as a setup job with a specific processing time, release date, due date, and precedence relations. We develop several sufficient conditions to derive setup jobs. We specify their parameters and precedence relations such that the optimal solution value of the modified problem obtained by ignoring the setup times, not the setup jobs, is no larger than the optimal solution value of the original problem. One lower bound for the modified problem proceeds by allowing preemption. Due to the agreeable precedence structure, the preemptive problem is solvable in O(n log n) time.
Original languageEnglish
Pages (from-to)1165-1174
JournalManagement science
Volume42
Issue number8
DOIs
Publication statusPublished - 1996

Fingerprint

Setup times
Single machine scheduling
Release dates
Due dates
Optimal solution
Manufacturing
Delivery performance
Batching
Single machine
Customer satisfaction
Optimality
Preemption
Branch and bound algorithm
NP-hard
Maximum lateness
Lower bounds

Keywords

  • Scheduling
  • Maximum
  • Lateness
  • Family setup times
  • Branch-and-bounde
  • Setup jobs
  • Preemption

Cite this

@article{0439280594384c959982c4acfeea75c6,
title = "Single-machine scheduling with release dates, due dates and family setup times",
abstract = "We address the NP-hard problem of scheduling n independent jobs with release dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery performance, between maximizing machine utilization by batching similar jobs and maximizing customers' satisfaction by completing jobs before their due dates. We develop a branch-and-bound algorithm, and our computational results show that it solves almost all instances with up to about 40 jobs to optimality. The main algorithmic contribution is our lower bounding strategy to deal with family setup times. The key idea is to see a setup time as a setup job with a specific processing time, release date, due date, and precedence relations. We develop several sufficient conditions to derive setup jobs. We specify their parameters and precedence relations such that the optimal solution value of the modified problem obtained by ignoring the setup times, not the setup jobs, is no larger than the optimal solution value of the original problem. One lower bound for the modified problem proceeds by allowing preemption. Due to the agreeable precedence structure, the preemptive problem is solvable in O(n log n) time.",
keywords = "Scheduling, Maximum, Lateness, Family setup times, Branch-and-bounde, Setup jobs, Preemption",
author = "J.M.J. Schutten and {van de Velde}, S.L. and W.H.M. Zijm",
year = "1996",
doi = "10.1287/mnsc.42.8.1165",
language = "English",
volume = "42",
pages = "1165--1174",
journal = "Management science",
issn = "0025-1909",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "8",

}

Single-machine scheduling with release dates, due dates and family setup times. / Schutten, J.M.J.; van de Velde, S.L.; Zijm, W.H.M.

In: Management science, Vol. 42, No. 8, 1996, p. 1165-1174.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Single-machine scheduling with release dates, due dates and family setup times

AU - Schutten, J.M.J.

AU - van de Velde, S.L.

AU - Zijm, W.H.M.

PY - 1996

Y1 - 1996

N2 - We address the NP-hard problem of scheduling n independent jobs with release dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery performance, between maximizing machine utilization by batching similar jobs and maximizing customers' satisfaction by completing jobs before their due dates. We develop a branch-and-bound algorithm, and our computational results show that it solves almost all instances with up to about 40 jobs to optimality. The main algorithmic contribution is our lower bounding strategy to deal with family setup times. The key idea is to see a setup time as a setup job with a specific processing time, release date, due date, and precedence relations. We develop several sufficient conditions to derive setup jobs. We specify their parameters and precedence relations such that the optimal solution value of the modified problem obtained by ignoring the setup times, not the setup jobs, is no larger than the optimal solution value of the original problem. One lower bound for the modified problem proceeds by allowing preemption. Due to the agreeable precedence structure, the preemptive problem is solvable in O(n log n) time.

AB - We address the NP-hard problem of scheduling n independent jobs with release dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery performance, between maximizing machine utilization by batching similar jobs and maximizing customers' satisfaction by completing jobs before their due dates. We develop a branch-and-bound algorithm, and our computational results show that it solves almost all instances with up to about 40 jobs to optimality. The main algorithmic contribution is our lower bounding strategy to deal with family setup times. The key idea is to see a setup time as a setup job with a specific processing time, release date, due date, and precedence relations. We develop several sufficient conditions to derive setup jobs. We specify their parameters and precedence relations such that the optimal solution value of the modified problem obtained by ignoring the setup times, not the setup jobs, is no larger than the optimal solution value of the original problem. One lower bound for the modified problem proceeds by allowing preemption. Due to the agreeable precedence structure, the preemptive problem is solvable in O(n log n) time.

KW - Scheduling

KW - Maximum

KW - Lateness

KW - Family setup times

KW - Branch-and-bounde

KW - Setup jobs

KW - Preemption

U2 - 10.1287/mnsc.42.8.1165

DO - 10.1287/mnsc.42.8.1165

M3 - Article

VL - 42

SP - 1165

EP - 1174

JO - Management science

JF - Management science

SN - 0025-1909

IS - 8

ER -