Abstract

The online fulfilment problem consists of deciding from which fulfilment centre to supply incoming orders. In our setting, fulfilment centres carry an inventory of many items and have a maximum daily order processing capacity. This capacity is shared between items, such that computing the fulfilment function in parallel across items is not trivial. We develop an algorithm that does parallelize across items to evaluate exogenous fulfilment policies. We use an optimistic approach with a rollback to solve violations of the capacity constraint. We theoretically show that the number of rollbacks is tightly bound for a vast set of fulfilment rules, including greedy rules based on distance and inventory. Given that the number of fulfilment centres is usually small compared to the number of items, the potential for speed-ups is large. We empirically validate this by implementing our algorithm in JAX, a high-performance machine library in Python specifically developed for parallel GPU computing. We obtain orders of magnitude increases in speed-ups compared to a sequential benchmark. By adopting our parallel online fulfilment algorithm, firms may significantly reduce the computational time needed to optimize their fulfilment decisions. Our novel theoretical results may pave the way for future explorations at the intersection of parallel computing and operations management.