Project Introduction | Task Assignment of Robots in Intelligent Warehouse
More details about this project can be found in this paper. Here is a brief introduction to the project. This project is part of my master's thesis. My master's thesis (Written in Chinese) can be downloaded here.
Abstract:
This paper studies a task scheduling problem in the context of the mobile robot fulfillment system (MRFS), a parts-to-picker storage system where mobile robots bring movable racks to workstations. It determines the assignment of tasks of transporting racks to a fleet of robots with the objective of makespan minimization. A mixed integer programming model is presented to describe the problem. Aimed at quickly finding good solutions to this NP-hard problem, two heuristic rules and an ant colony optimization algorithm are developed. Computational experiments are conducted to evaluate the performance of the proposed heuristic solution procedures. It shows that the ant colony optimization algorithm generally has the best performance.
Mathematical Models
A mixed integer programming model is presented to describe the problem as follows:
The model can use CPLEX to obtain the exact solution at a small scale, and use heuristic algorithms to find the good solution quickly when the scale is large. The CPLEX code is here. When there are 3 robots and 8 tasks, the model solving time for CPLEX is as follows:
Heuristic Solutions
The Longest Setup & Handling Time First Rule
The LSHT rule assigns at t = 0 the R largest tasks to the R robots. After that, whenever a robot is freed, the longest task among those not yet allocated is put on the robot. This heuristic rule attempts to put the shorter tasks towards the end of the schedule, where they can be used for workload balancing.
The Shortest Setup Time First Rule
Similar to the LSHT rule, the SST rule first assigns the R tasks requiring the shortest setup times to the R robots. Afterwards, whenever a robot is idle and available, the task among those not yet allocated requiring the smallest setup time is scheduled on the robot. This rule tries to reduce the total setup time (i.e., the total travel time without loads) of each robot.
Ant Colony Algorithm
For the multi-robot scheduling problem under discussion, a complete schedule can be constructed by iteratively dispatching a task unassigned to one of the robots. Thus, an ACO algorithm is proposed here to solve this problem. The algorithm generally follows the scheme of the any colony system (ACS) . The combined heuristic information for a dispatch and the pheromone updating rules can be found in the paper.
Numerical Experiments
This paper explicitly studies a multi-robot scheduling problem with the objective of makespan minimization in a MRFS environment for the first time. Two heuristic rules (LHST, SST) and an ACO algorithm are developed to solve the problem.
The results show that in most cases all the three proposed heuristics can result in feasible solutions within acceptable time durations, and ACO can generally produce the best schedules.