Scheduling multiple factory cranes on a common track

• We develop a heuristic algorithm for scheduling multiple factory cranes.
• Jobs are assigned to cranes, and crane movements scheduled to avoid interference.
• Each job consists of two or more tasks executed in sequence by the same crane.
• We obtain provably optimal, or near-optimal solutions on realistic problems.

A heuristic algorithm is presented for scheduling the movement of multiple factory cranes mounted on a common track. The cranes must complete a sequence of tasks at locations along the track without crossing paths, while adhering as closely as possible to a factory production schedule. The algorithm creates a decision tree of possible states of the crane system, which evolves over time as tasks are assigned and sequenced. By identifying and removing inferior states from the tree, the algorithm efficiently generates provably optimal or near-optimal crane schedules, depending on the complexity of the problem instance.