Adaptive large neighborhood search for scheduling of mobile robots

Quang-Vinh Dang, Hana Rudová, Cong Thanh Nguyen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

Our work addresses the scheduling of mobile robots for transportation and processing of operations on machines in a flexible manufacturing system. Both mobile robots and automated guided vehicles (AGVs) can transport components among machines in the working space. Nevertheless, the difference is that mobile robots considered in this work can process specific value-added operations, which is not possible for AGVs. This new feature increases complexity as well as computational demands. To summarize, we need to compute a sequence of operations on machines, the robot assignments for transportation, and the robot assignments for processing. The main contribution is the proposal of an adaptive large neighborhood search algorithm with the sets of exploration and exploitation heuristics to solve the problem considering makespan minimization. Experimental evaluation is presented on the existing benchmarks. The quality of our solutions is compared to a heuristic based on genetic algorithm and mixed-integer programming proposed recently. The comparison shows that our approach can achieve comparable results in real time which is in order of magnitude faster than the earlier heuristic.
Original languageEnglish
Title of host publicationGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages224-232
Number of pages9
ISBN (Print)978-1-4503-6111-8
DOIs
Publication statusPublished - 13 Jul 2019
Event2019 Genetic and Evolutionary Computation Conference, GECCO 2019: The Genetic and Evolutionary Computation Conference - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019

Conference

Conference2019 Genetic and Evolutionary Computation Conference, GECCO 2019
CountryCzech Republic
CityPrague
Period13/07/1917/07/19

Fingerprint

Mobile robots
Scheduling
Robots
Flexible manufacturing systems
Machine components
Integer programming
Processing
Computational complexity
Genetic algorithms

Keywords

  • Adaptive Large Neighborhood Search
  • Flexible Manufacturing Systems
  • Mobile robots
  • Scheduling

Cite this

Dang, Q-V., Rudová, H., & Nguyen, C. T. (2019). Adaptive large neighborhood search for scheduling of mobile robots. In GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference (pp. 224-232). New York: Association for Computing Machinery, Inc. https://doi.org/10.1145/3321707.3321764
Dang, Quang-Vinh ; Rudová, Hana ; Nguyen, Cong Thanh. / Adaptive large neighborhood search for scheduling of mobile robots. GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference. New York : Association for Computing Machinery, Inc, 2019. pp. 224-232
@inproceedings{6ba2d7cf56ff43c7bf480e9a8eeceae3,
title = "Adaptive large neighborhood search for scheduling of mobile robots",
abstract = "Our work addresses the scheduling of mobile robots for transportation and processing of operations on machines in a flexible manufacturing system. Both mobile robots and automated guided vehicles (AGVs) can transport components among machines in the working space. Nevertheless, the difference is that mobile robots considered in this work can process specific value-added operations, which is not possible for AGVs. This new feature increases complexity as well as computational demands. To summarize, we need to compute a sequence of operations on machines, the robot assignments for transportation, and the robot assignments for processing. The main contribution is the proposal of an adaptive large neighborhood search algorithm with the sets of exploration and exploitation heuristics to solve the problem considering makespan minimization. Experimental evaluation is presented on the existing benchmarks. The quality of our solutions is compared to a heuristic based on genetic algorithm and mixed-integer programming proposed recently. The comparison shows that our approach can achieve comparable results in real time which is in order of magnitude faster than the earlier heuristic.",
keywords = "Adaptive Large Neighborhood Search, Flexible Manufacturing Systems, Mobile robots, Scheduling",
author = "Quang-Vinh Dang and Hana Rudov{\'a} and Nguyen, {Cong Thanh}",
year = "2019",
month = "7",
day = "13",
doi = "10.1145/3321707.3321764",
language = "English",
isbn = "978-1-4503-6111-8",
pages = "224--232",
booktitle = "GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

Dang, Q-V, Rudová, H & Nguyen, CT 2019, Adaptive large neighborhood search for scheduling of mobile robots. in GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, New York, pp. 224-232, 2019 Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, 13/07/19. https://doi.org/10.1145/3321707.3321764

Adaptive large neighborhood search for scheduling of mobile robots. / Dang, Quang-Vinh; Rudová, Hana; Nguyen, Cong Thanh.

GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference. New York : Association for Computing Machinery, Inc, 2019. p. 224-232.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Adaptive large neighborhood search for scheduling of mobile robots

AU - Dang, Quang-Vinh

AU - Rudová, Hana

AU - Nguyen, Cong Thanh

PY - 2019/7/13

Y1 - 2019/7/13

N2 - Our work addresses the scheduling of mobile robots for transportation and processing of operations on machines in a flexible manufacturing system. Both mobile robots and automated guided vehicles (AGVs) can transport components among machines in the working space. Nevertheless, the difference is that mobile robots considered in this work can process specific value-added operations, which is not possible for AGVs. This new feature increases complexity as well as computational demands. To summarize, we need to compute a sequence of operations on machines, the robot assignments for transportation, and the robot assignments for processing. The main contribution is the proposal of an adaptive large neighborhood search algorithm with the sets of exploration and exploitation heuristics to solve the problem considering makespan minimization. Experimental evaluation is presented on the existing benchmarks. The quality of our solutions is compared to a heuristic based on genetic algorithm and mixed-integer programming proposed recently. The comparison shows that our approach can achieve comparable results in real time which is in order of magnitude faster than the earlier heuristic.

AB - Our work addresses the scheduling of mobile robots for transportation and processing of operations on machines in a flexible manufacturing system. Both mobile robots and automated guided vehicles (AGVs) can transport components among machines in the working space. Nevertheless, the difference is that mobile robots considered in this work can process specific value-added operations, which is not possible for AGVs. This new feature increases complexity as well as computational demands. To summarize, we need to compute a sequence of operations on machines, the robot assignments for transportation, and the robot assignments for processing. The main contribution is the proposal of an adaptive large neighborhood search algorithm with the sets of exploration and exploitation heuristics to solve the problem considering makespan minimization. Experimental evaluation is presented on the existing benchmarks. The quality of our solutions is compared to a heuristic based on genetic algorithm and mixed-integer programming proposed recently. The comparison shows that our approach can achieve comparable results in real time which is in order of magnitude faster than the earlier heuristic.

KW - Adaptive Large Neighborhood Search

KW - Flexible Manufacturing Systems

KW - Mobile robots

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85072339714&partnerID=8YFLogxK

U2 - 10.1145/3321707.3321764

DO - 10.1145/3321707.3321764

M3 - Conference contribution

AN - SCOPUS:85072339714

SN - 978-1-4503-6111-8

SP - 224

EP - 232

BT - GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Dang Q-V, Rudová H, Nguyen CT. Adaptive large neighborhood search for scheduling of mobile robots. In GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference. New York: Association for Computing Machinery, Inc. 2019. p. 224-232 https://doi.org/10.1145/3321707.3321764