TY - JOUR

T1 - Local search heuristics for the identical parallel machine scheduling with transport robots

AU - Yuskov, Alexander

AU - Kochetov, Yury

N1 - This work was supported by Russian Science Foundation grant 21-41-09017. A server of Sobolev Institute of Mathematics, Omsk Branch was used for computing.

PY - 2023

Y1 - 2023

N2 - We consider a new scheduling problem originating from order picking at an automatic warehouse. We have a finite set of orders. Each order consists of a set of items. All orders should process through the picking stage, where items are extracted from pallets and packed in boxes for customers. We have some identical parallel picking machines and some parking slots for pallets. Each machine can use the pallets from all parking slots. Each pallet should be brought from the automatic warehouse to the parking slot and re-turned by a transport robot. The fleet of robots is limited. Our goal is to process all orders with minimal makespan. To tackle the problem, we design a mathematical model and three local search heuristics based on the order permutations. A fast decoder procedure creates an active schedule for parallel machines under the robot fleet constraint. Computational ex-periments for semi-synthetic test instances with up to 345 orders, 30 robots, and 16 parallel machines indicate the high efficiency of the approach.

AB - We consider a new scheduling problem originating from order picking at an automatic warehouse. We have a finite set of orders. Each order consists of a set of items. All orders should process through the picking stage, where items are extracted from pallets and packed in boxes for customers. We have some identical parallel picking machines and some parking slots for pallets. Each machine can use the pallets from all parking slots. Each pallet should be brought from the automatic warehouse to the parking slot and re-turned by a transport robot. The fleet of robots is limited. Our goal is to process all orders with minimal makespan. To tackle the problem, we design a mathematical model and three local search heuristics based on the order permutations. A fast decoder procedure creates an active schedule for parallel machines under the robot fleet constraint. Computational ex-periments for semi-synthetic test instances with up to 345 orders, 30 robots, and 16 parallel machines indicate the high efficiency of the approach.

KW - local search

KW - machine scheduling

KW - order picking

KW - transport robot

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85153275695&origin=inward&txGid=b34b3ffc6fcc7e690af4f3efe9a50197

UR - https://www.mendeley.com/catalogue/de0e140a-93b6-3df2-b6ca-1afc932ac921/

M3 - Article

VL - 21

SP - 130

EP - 149

JO - International Journal of Artificial Intelligence

JF - International Journal of Artificial Intelligence

SN - 0974-0635

IS - 2 Special Issue

ER -