Robotic-cell scheduling with pick-up constraints and uncertain processing times

Daniel Tonke*, Martin Grunow, Renzo Akkerman

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Technological developments have propelled the deployment of robots in many applications, which has led to the trend to integrate an increasing number of uncertain processes into robotic and automated equipment. We contribute to this domain by considering the scheduling of a dual-gripper robotic cell. For systems with one potential bottleneck, we determine conditions under which the widely used swap sequence does not guarantee optimality or even feasibility and prove that optimal schedules can be derived under certain conditions when building on two types of slack we introduce. With the addition of a third type of slack and the concept of fixed partial schedules, we develop an offline-online scheduling approach that, in contrast with previous work, is able to deal with uncertainty in all process steps and robot handling tasks, even under pick-up constraints. The approach can deal with single- or multiple-bottleneck systems, and is the first approach that is not restricted to a single predefined sequence such as the swap sequence. Our approach is well suited for real-world applications, since it generates cyclic schedules and allows integration into commonly-used frameworks for robotic-cell scheduling and control. We demonstrate the applicability of our approach to cluster tools in semiconductor manufacturing, showing that our approach generates feasible results for all tested levels of uncertainty and optimal or near-optimal results for low levels of uncertainty. With additional symmetry-breaking constraints, the model can be efficiently applied to industrial-scale test instances. We show that reducing uncertainty to below 10% of the processing time would yield significantly improved cycle lengths and throughput. We also demonstrate that the widely used swap sequence only finds solutions for less than 1% of the instances when strict pick-up constraints are enforced and processing times are heterogeneous. As our approach finds feasible solutions to all of these instances, it enables the application of robotic cells to a significantly broader application environment.

Original languageEnglish
Pages (from-to)1217-1235
JournalIISE Transactions
Volume51
Issue number11
DOIs
Publication statusPublished - 6 Nov 2019

Fingerprint

Robotics
Scheduling
Processing
Robots
Grippers
Throughput
Semiconductor materials
Uncertainty

Keywords

  • automated manufacturing equipment
  • cyclic scheduling
  • optimization
  • Robotic-cell scheduling
  • uncertainty

Cite this

Tonke, Daniel ; Grunow, Martin ; Akkerman, Renzo. / Robotic-cell scheduling with pick-up constraints and uncertain processing times. In: IISE Transactions. 2019 ; Vol. 51, No. 11. pp. 1217-1235.
@article{0f1d44c7bb564bf8b57e3e9feb3d38a0,
title = "Robotic-cell scheduling with pick-up constraints and uncertain processing times",
abstract = "Technological developments have propelled the deployment of robots in many applications, which has led to the trend to integrate an increasing number of uncertain processes into robotic and automated equipment. We contribute to this domain by considering the scheduling of a dual-gripper robotic cell. For systems with one potential bottleneck, we determine conditions under which the widely used swap sequence does not guarantee optimality or even feasibility and prove that optimal schedules can be derived under certain conditions when building on two types of slack we introduce. With the addition of a third type of slack and the concept of fixed partial schedules, we develop an offline-online scheduling approach that, in contrast with previous work, is able to deal with uncertainty in all process steps and robot handling tasks, even under pick-up constraints. The approach can deal with single- or multiple-bottleneck systems, and is the first approach that is not restricted to a single predefined sequence such as the swap sequence. Our approach is well suited for real-world applications, since it generates cyclic schedules and allows integration into commonly-used frameworks for robotic-cell scheduling and control. We demonstrate the applicability of our approach to cluster tools in semiconductor manufacturing, showing that our approach generates feasible results for all tested levels of uncertainty and optimal or near-optimal results for low levels of uncertainty. With additional symmetry-breaking constraints, the model can be efficiently applied to industrial-scale test instances. We show that reducing uncertainty to below 10{\%} of the processing time would yield significantly improved cycle lengths and throughput. We also demonstrate that the widely used swap sequence only finds solutions for less than 1{\%} of the instances when strict pick-up constraints are enforced and processing times are heterogeneous. As our approach finds feasible solutions to all of these instances, it enables the application of robotic cells to a significantly broader application environment.",
keywords = "automated manufacturing equipment, cyclic scheduling, optimization, Robotic-cell scheduling, uncertainty",
author = "Daniel Tonke and Martin Grunow and Renzo Akkerman",
year = "2019",
month = "11",
day = "6",
doi = "10.1080/24725854.2018.1555727",
language = "English",
volume = "51",
pages = "1217--1235",
journal = "IISE Transactions",
issn = "2472-5854",
publisher = "Taylor and Francis Inc.",
number = "11",

}

Robotic-cell scheduling with pick-up constraints and uncertain processing times. / Tonke, Daniel; Grunow, Martin; Akkerman, Renzo.

In: IISE Transactions, Vol. 51, No. 11, 06.11.2019, p. 1217-1235.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Robotic-cell scheduling with pick-up constraints and uncertain processing times

AU - Tonke, Daniel

AU - Grunow, Martin

AU - Akkerman, Renzo

PY - 2019/11/6

Y1 - 2019/11/6

N2 - Technological developments have propelled the deployment of robots in many applications, which has led to the trend to integrate an increasing number of uncertain processes into robotic and automated equipment. We contribute to this domain by considering the scheduling of a dual-gripper robotic cell. For systems with one potential bottleneck, we determine conditions under which the widely used swap sequence does not guarantee optimality or even feasibility and prove that optimal schedules can be derived under certain conditions when building on two types of slack we introduce. With the addition of a third type of slack and the concept of fixed partial schedules, we develop an offline-online scheduling approach that, in contrast with previous work, is able to deal with uncertainty in all process steps and robot handling tasks, even under pick-up constraints. The approach can deal with single- or multiple-bottleneck systems, and is the first approach that is not restricted to a single predefined sequence such as the swap sequence. Our approach is well suited for real-world applications, since it generates cyclic schedules and allows integration into commonly-used frameworks for robotic-cell scheduling and control. We demonstrate the applicability of our approach to cluster tools in semiconductor manufacturing, showing that our approach generates feasible results for all tested levels of uncertainty and optimal or near-optimal results for low levels of uncertainty. With additional symmetry-breaking constraints, the model can be efficiently applied to industrial-scale test instances. We show that reducing uncertainty to below 10% of the processing time would yield significantly improved cycle lengths and throughput. We also demonstrate that the widely used swap sequence only finds solutions for less than 1% of the instances when strict pick-up constraints are enforced and processing times are heterogeneous. As our approach finds feasible solutions to all of these instances, it enables the application of robotic cells to a significantly broader application environment.

AB - Technological developments have propelled the deployment of robots in many applications, which has led to the trend to integrate an increasing number of uncertain processes into robotic and automated equipment. We contribute to this domain by considering the scheduling of a dual-gripper robotic cell. For systems with one potential bottleneck, we determine conditions under which the widely used swap sequence does not guarantee optimality or even feasibility and prove that optimal schedules can be derived under certain conditions when building on two types of slack we introduce. With the addition of a third type of slack and the concept of fixed partial schedules, we develop an offline-online scheduling approach that, in contrast with previous work, is able to deal with uncertainty in all process steps and robot handling tasks, even under pick-up constraints. The approach can deal with single- or multiple-bottleneck systems, and is the first approach that is not restricted to a single predefined sequence such as the swap sequence. Our approach is well suited for real-world applications, since it generates cyclic schedules and allows integration into commonly-used frameworks for robotic-cell scheduling and control. We demonstrate the applicability of our approach to cluster tools in semiconductor manufacturing, showing that our approach generates feasible results for all tested levels of uncertainty and optimal or near-optimal results for low levels of uncertainty. With additional symmetry-breaking constraints, the model can be efficiently applied to industrial-scale test instances. We show that reducing uncertainty to below 10% of the processing time would yield significantly improved cycle lengths and throughput. We also demonstrate that the widely used swap sequence only finds solutions for less than 1% of the instances when strict pick-up constraints are enforced and processing times are heterogeneous. As our approach finds feasible solutions to all of these instances, it enables the application of robotic cells to a significantly broader application environment.

KW - automated manufacturing equipment

KW - cyclic scheduling

KW - optimization

KW - Robotic-cell scheduling

KW - uncertainty

U2 - 10.1080/24725854.2018.1555727

DO - 10.1080/24725854.2018.1555727

M3 - Article

VL - 51

SP - 1217

EP - 1235

JO - IISE Transactions

JF - IISE Transactions

SN - 2472-5854

IS - 11

ER -