Parallel machine scheduling with release dates, due dates and family setup times

Johannes M.J. Schutten, R.A.M. Leussink

Research output: Contribution to journalArticleAcademicpeer-review

52 Citations (Scopus)
99 Downloads (Pure)

Abstract

In manufacturing, there is a fundamental conflict between efficient production and delivery performance. Maximizing machine utilization by batching similar jobs may lead to poor delivery performance. Minimizing customers' dissatisfaction may lead to an inefficient use of the machines. In this paper, we consider the problem of scheduling n independent jobs with release dates, due dates, and family setup times on m parallel machines. The objective is to minimize the maximum lateness of any job. We present a branch-and-bound algorithm to solve this problem. This algorithm exploits the fact that an optimal schedule is contained in a specific subset of all feasible schedules. For lower bounding purposes, we see setup times as setup jobs with release dates, due dates and processing times. We present two lower bounds for the problem with setup jobs, one of which proceeds by allowing preemption.
Original languageUndefined
Pages (from-to)119-126
JournalInternational journal of production economics
Volume46-47
DOIs
Publication statusPublished - 1996

Keywords

  • METIS-144442
  • IR-32192
  • Branch-and-bound
  • Family setup times
  • Maximum lateness
  • Scheduling
  • Parallel machines

Cite this

@article{4fca00699488423e869101bfdc049445,
title = "Parallel machine scheduling with release dates, due dates and family setup times",
abstract = "In manufacturing, there is a fundamental conflict between efficient production and delivery performance. Maximizing machine utilization by batching similar jobs may lead to poor delivery performance. Minimizing customers' dissatisfaction may lead to an inefficient use of the machines. In this paper, we consider the problem of scheduling n independent jobs with release dates, due dates, and family setup times on m parallel machines. The objective is to minimize the maximum lateness of any job. We present a branch-and-bound algorithm to solve this problem. This algorithm exploits the fact that an optimal schedule is contained in a specific subset of all feasible schedules. For lower bounding purposes, we see setup times as setup jobs with release dates, due dates and processing times. We present two lower bounds for the problem with setup jobs, one of which proceeds by allowing preemption.",
keywords = "METIS-144442, IR-32192, Branch-and-bound, Family setup times, Maximum lateness, Scheduling, Parallel machines",
author = "Schutten, {Johannes M.J.} and R.A.M. Leussink",
year = "1996",
doi = "10.1016/0925-5273(95)00086-0",
language = "Undefined",
volume = "46-47",
pages = "119--126",
journal = "International journal of production economics",
issn = "0925-5273",
publisher = "Elsevier",

}

Parallel machine scheduling with release dates, due dates and family setup times. / Schutten, Johannes M.J.; Leussink, R.A.M.

In: International journal of production economics, Vol. 46-47, 1996, p. 119-126.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Schutten, Johannes M.J.

AU - Leussink, R.A.M.

PY - 1996

Y1 - 1996

N2 - In manufacturing, there is a fundamental conflict between efficient production and delivery performance. Maximizing machine utilization by batching similar jobs may lead to poor delivery performance. Minimizing customers' dissatisfaction may lead to an inefficient use of the machines. In this paper, we consider the problem of scheduling n independent jobs with release dates, due dates, and family setup times on m parallel machines. The objective is to minimize the maximum lateness of any job. We present a branch-and-bound algorithm to solve this problem. This algorithm exploits the fact that an optimal schedule is contained in a specific subset of all feasible schedules. For lower bounding purposes, we see setup times as setup jobs with release dates, due dates and processing times. We present two lower bounds for the problem with setup jobs, one of which proceeds by allowing preemption.

AB - In manufacturing, there is a fundamental conflict between efficient production and delivery performance. Maximizing machine utilization by batching similar jobs may lead to poor delivery performance. Minimizing customers' dissatisfaction may lead to an inefficient use of the machines. In this paper, we consider the problem of scheduling n independent jobs with release dates, due dates, and family setup times on m parallel machines. The objective is to minimize the maximum lateness of any job. We present a branch-and-bound algorithm to solve this problem. This algorithm exploits the fact that an optimal schedule is contained in a specific subset of all feasible schedules. For lower bounding purposes, we see setup times as setup jobs with release dates, due dates and processing times. We present two lower bounds for the problem with setup jobs, one of which proceeds by allowing preemption.

KW - METIS-144442

KW - IR-32192

KW - Branch-and-bound

KW - Family setup times

KW - Maximum lateness

KW - Scheduling

KW - Parallel machines

U2 - 10.1016/0925-5273(95)00086-0

DO - 10.1016/0925-5273(95)00086-0

M3 - Article

VL - 46-47

SP - 119

EP - 126

JO - International journal of production economics

JF - International journal of production economics

SN - 0925-5273

ER -