Adaptive Large Neighborhood Search for Scheduling of Mobile
Robots

D 2019

Adaptive Large Neighborhood Search for Scheduling of Mobile Robots

DANG, Vinh Quang, Hana RUDOVÁ and Cong Thanh NGUYEN

Basic information

Original name

Adaptive Large Neighborhood Search for Scheduling of Mobile Robots

Authors

DANG, Vinh Quang (704 Viet Nam, belonging to the institution), Hana RUDOVÁ (203 Czech Republic, guarantor, belonging to the institution) and Cong Thanh NGUYEN (704 Viet Nam)

Edition

New York, NY, USA, The Genetic and Evolutionary Computation Conference (GECCO), p. 224-232, 9 pp. 2019

Publisher

ACM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

DOI

RIV identification code

RIV/00216224:14330/19:00109329

Organization unit

Faculty of Informatics

ISBN

978-1-4503-6111-8

DOI

http://dx.doi.org/10.1145/3321707.3321764

UT WoS

000523218400029

Keywords in English

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

Abstract

V originále

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.

Citovat

DANG, Vinh Quang, Hana RUDOVÁ and Cong Thanh NGUYEN. Adaptive Large Neighborhood Search for Scheduling of Mobile Robots. Online. In The Genetic and Evolutionary Computation Conference (GECCO). New York, NY, USA: ACM, 2019, p. 224-232. ISBN 978-1-4503-6111-8. Available from: https://dx.doi.org/10.1145/3321707.3321764.

@inproceedings{1509617,
   author = {Dang, Vinh Quang and Rudová, Hana and Nguyen, Cong Thanh},
   address = {New York, NY, USA},
   booktitle = {The Genetic and Evolutionary Computation Conference (GECCO)},
   doi = {http://dx.doi.org/10.1145/3321707.3321764},
   keywords = {Scheduling; Mobile robots; Adaptive Large Neighborhood Search; Flexible Manufacturing Systems},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {New York, NY, USA},
   isbn = {978-1-4503-6111-8},
   pages = {224-232},
   publisher = {ACM},
   title = {Adaptive Large Neighborhood Search for Scheduling of Mobile Robots},
   url = {https://dl.acm.org/citation.cfm?doid=3321707.3321764},
   year = {2019}
}

TY  - JOUR
ID  - 1509617
AU  - Dang, Vinh Quang - Rudová, Hana - Nguyen, Cong Thanh
PY  - 2019
TI  - Adaptive Large Neighborhood Search for Scheduling of Mobile Robots
PB  - ACM
CY  - New York, NY, USA
SN  - 9781450361118
KW  - Scheduling
KW  - Mobile robots
KW  - Adaptive Large Neighborhood Search
KW  - Flexible Manufacturing Systems
UR  - https://dl.acm.org/citation.cfm?doid=3321707.3321764
L2  - https://dl.acm.org/citation.cfm?doid=3321707.3321764
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.
ER  -

DANG, Vinh Quang, Hana RUDOVÁ and Cong Thanh NGUYEN. Adaptive Large Neighborhood Search for Scheduling of Mobile Robots. Online. In \textit{The Genetic and Evolutionary Computation Conference (GECCO)}. New York, NY, USA: ACM, 2019, p.~224-232. ISBN~978-1-4503-6111-8. Available from: https://dx.doi.org/10.1145/3321707.3321764.

Detailed Information on Publication Record