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 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 using twin robots instead of a single one.
| Original language | English |
|---|---|
| Pages (from-to) | 518-542 |
| Number of pages | 25 |
| Journal | International Journal of Production Research |
| Volume | 56 |
| Issue number | 1-2 |
| Early online date | 20 Nov 2017 |
| DOIs | |
| Publication status | Published - 2018 |
Fingerprint
Keywords
- genetic algorithms
- makespan
- mixed integer linear programming
- palletising
- scheduling
ASJC Scopus subject areas
- Strategy and Management
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
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 journal › Article
}
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 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 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 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 using twin robots instead of a single one.
KW - genetic algorithms
KW - makespan
KW - mixed integer linear programming
KW - palletising
KW - scheduling
UR - http://www.scopus.com/inward/record.url?scp=85041292210&partnerID=8YFLogxK
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
JF - International Journal of Production Research
SN - 0020-7543
IS - 1-2
ER -