  Managing delivery deadlines in automated warehouses and factories is crucial
for maintaining customer satisfaction and ensuring seamless production. This
study introduces the problem of online multi-agent pickup and delivery with
task deadlines (MAPD-D), which is an advanced variant of the online MAPD
problem incorporating delivery deadlines. MAPD-D presents a dynamic
deadline-driven approach that includes task deadlines, with tasks being added
at any time (online), thus challenging conventional MAPD frameworks. To tackle
MAPD-D, we propose a novel algorithm named deadline-aware token passing (D-TP).
The D-TP algorithm is designed to calculate pickup deadlines and assign tasks
while balancing execution cost and deadline proximity. Additionally, we
introduce the D-TP with task swaps (D-TPTS) method to further reduce task
tardiness, enhancing flexibility and efficiency via task-swapping strategies.
Numerical experiments were conducted in simulated warehouse environments to
showcase the effectiveness of the proposed methods. Both D-TP and D-TPTS
demonstrate significant reductions in task tardiness compared to existing
methods, thereby contributing to efficient operations in automated warehouses
and factories with delivery deadlines.
