Warehouse and industrial applications

Why this matters

The factory wants the stock count finished before the morning shift starts. If jobs are split badly, one drone works far longer than the others and everyone waits for the slowest. And if a drone flies into an aisle while a forklift is working there, an accident may follow. This module brings everything in the course together into a real operating system for the factory warehouse.

Splitting jobs with the LPT rule

Splitting jobs of different lengths among $m$ identical machines to finish as early as possible (minimum makespan) is a hard problem. The LPT (longest processing time first) rule sorts jobs from longest to shortest and gives each next job to the machine that becomes free first. Graham (1969) proved that this rule is never worse than $\left(\frac{4}{3}-\frac{1}{3m}\right)$ times the optimum.

from itertools import product

aisles = [14, 12, 11, 9, 8, 7, 6, 5]
M = 3

loads, plan = [0] * M, [[] for _ in range(M)]
for idx, t in sorted(enumerate(aisles, 1), key=lambda x: -x[1]):
    k = loads.index(min(loads))
    loads[k] += t
    plan[k].append(f"A{idx}")
lpt = max(loads)

best = min(max(sum(t for t, a in zip(aisles, asg) if a == k) for k in range(M))
           for asg in product(range(M), repeat=len(aisles)))
lower = max(sum(aisles) / M, max(aisles))
for k in range(M):
    print(f"D{k + 1}: {plan[k]} = {loads[k]} min")
print(f"LPT makespan {lpt} min, optimum {best} min, lower bound {lower:.1f} min")
print(f"LPT / optimum = {lpt / best:.3f} (Graham bound {4 / 3 - 1 / (3 * M):.3f})")

D1: ['A1', 'A6'] = 21 min
D2: ['A2', 'A5', 'A7'] = 26 min
D3: ['A3', 'A4', 'A8'] = 25 min
LPT makespan 26 min, optimum 25 min, lower bound 24.0 min
LPT / optimum = 1.040 (Graham bound 1.222)

Separating drones from forklifts and people

The safest approach is separation in time and space: drones fly an aisle only when it is free of forklifts and people. The warehouse management system knows when forklifts will enter which aisle, so it can be used to check the schedule before flight.

drone_slots = {"A1": (0, 14), "A2": (0, 12), "A3": (0, 11), "A4": (11, 20), "A5": (12, 20)}
forklift = [("A4", 18, 25), ("A2", 30, 40), ("A5", 5, 10)]       # aisle, start, end (min)
BUFFER = 2                                                        # buffer minutes between jobs

for aisle, f0, f1 in forklift:
    d0, d1 = drone_slots.get(aisle, (None, None))
    if d0 is None:
        continue
    clash = d0 < f1 + BUFFER and f0 < d1 + BUFFER
    print(f"{aisle}: drone {d0}-{d1} min, forklift {f0}-{f1} min -> {'CONFLICT' if clash else 'ok'}")

A4: drone 11-20 min, forklift 18-25 min -> CONFLICT
A2: drone 0-12 min, forklift 30-40 min -> ok
A5: drone 12-20 min, forklift 5-10 min -> ok

Safety and requirements

• Flight-controller systems: enable Collision Prevention (Module 3), set a geofence for the room, and set the behaviour on loss of position, for example landing immediately instead of returning to base, which needs a position.
• Charging docks: place them in a separate area away from combustible materials, and size their number to the flight cycle (Module 1 of UAT 364).
• Risk assessment: use a likelihood-severity matrix following the ICAO SMS guidance (UAT 362), considering effects on workers, goods and the fire-suppression system.
• Indoor flight rules: we found no CAAT announcement that states clearly whether flight inside a closed building falls under its requirements. Teams should ask CAAT through the UAS Portal and always follow the factory’s own safety rules.

The ETH Zurich report (Wawrla et al., 2019) identifies battery safety and integration with existing systems as key challenges for warehouse drones, so a well-designed system must address both from the start.

Module lab

Common mistakes

Summary

• The LPT rule splits jobs close to optimally, with Graham’s guaranteed bound.
• Separate drones from forklifts and people in time and space, and check the schedule with a buffer before flight.
• The system needs avoidance, a geofence, loss-of-position behaviour and safe charging docks.
• Ask CAAT about indoor flight and follow the factory’s requirements.

Check your understanding

1. Jobs of 10, 8, 6 and 4 minutes with 2 drones: what makespan does LPT give?
2. What is Graham’s bound for 2 drones?
3. Total work 60 minutes, longest job 15 minutes, 3 drones: what is the lower bound on completion time?
4. A drone at 10–20 minutes and a forklift at 21–30 minutes with a 2-minute buffer: do they overlap?
5. Why is automatic return to base unsuitable when position is lost indoors?