Scheduling Twin Robots in a Palletising Problem

Research output: Contribution to journalArticle

  • 1 Citations

Abstract

This paper introduces the Twin Robot Palletising Problem (TRPP) in which two robots must be scheduled and routed to pick up and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another. The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRPP, as well as two mixed integer linear programming models. Local search operators are introduced, before an iterated local search and a genetic algorithm are developed, in which a linear-time scheduling algorithm and dynamic programming are utilised to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the metaheuristics, and the savings obtained by using twin robots instead of a single one.
LanguageEnglish
Pages518-542
Number of pages25
JournalInternational Journal of Production Research
Volume56
Issue number1-2
Early online date20 Nov 2017
DOIs
StatusPublished - 2018

Fingerprint

Scheduling
Robots
Rails
Scheduling algorithms
Dynamic programming
Linear programming
Robot
Mathematical operators
Genetic algorithms
Hardness
Mathematical models
Local search (optimization)
Rail

Cite this

Scheduling Twin Robots in a Palletising Problem. / Thomasson, Oliver; Battarra, Maria; Erdoğan, Güneş; Laporte, Gilbert.

In: International Journal of Production Research, Vol. 56, No. 1-2, 2018, p. 518-542.

Research output: Contribution to journalArticle

@article{f15cdb93bcbb44d8a91bbcc08f9766d2,
title = "Scheduling Twin Robots in a Palletising Problem",
abstract = "This paper introduces the Twin Robot Palletising Problem (TRPP) in which two robots must be scheduled and routed to pick up and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another. The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRPP, as well as two mixed integer linear programming models. Local search operators are introduced, before an iterated local search and a genetic algorithm are developed, in which a linear-time scheduling algorithm and dynamic programming are utilised to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the metaheuristics, and the savings obtained by using twin robots instead of a single one.",
author = "Oliver Thomasson and Maria Battarra and G{\"u}neş Erdoğan and Gilbert Laporte",
year = "2018",
doi = "10.1080/00207543.2017.1401249",
language = "English",
volume = "56",
pages = "518--542",
journal = "International Journal of Production Research",
issn = "0020-7543",
publisher = "Taylor & Francis",
number = "1-2",

}

TY - JOUR

T1 - Scheduling Twin Robots in a Palletising Problem

AU - Thomasson, Oliver

AU - Battarra, Maria

AU - Erdoğan, Güneş

AU - Laporte, Gilbert

PY - 2018

Y1 - 2018

N2 - This paper introduces the Twin Robot Palletising Problem (TRPP) in which two robots must be scheduled and routed to pick up and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another. The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRPP, as well as two mixed integer linear programming models. Local search operators are introduced, before an iterated local search and a genetic algorithm are developed, in which a linear-time scheduling algorithm and dynamic programming are utilised to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the metaheuristics, and the savings obtained by using twin robots instead of a single one.

AB - This paper introduces the Twin Robot Palletising Problem (TRPP) in which two robots must be scheduled and routed to pick up and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another. The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRPP, as well as two mixed integer linear programming models. Local search operators are introduced, before an iterated local search and a genetic algorithm are developed, in which a linear-time scheduling algorithm and dynamic programming are utilised to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the metaheuristics, and the savings obtained by using twin robots instead of a single one.

U2 - 10.1080/00207543.2017.1401249

DO - 10.1080/00207543.2017.1401249

M3 - Article

VL - 56

SP - 518

EP - 542

JO - International Journal of Production Research

T2 - International Journal of Production Research

JF - International Journal of Production Research

SN - 0020-7543

IS - 1-2

ER -