One-dimensional vehicle scheduling with a front-end depot and non-crossing constraints

This paper considers the scheduling problem of multiple vehicles executing a given set of jobs in parallel along a shared pathway. The job set consists of storage and retrieval tasks, transporting goods between a front-end depot and given storage locations on the line. Non-crossing constraints need to be applied to the vehicle movements. This problem setting is relevant when a train is loaded with containers by multiple straddle carriers on the landside of a container terminal. Other potential applications exist in multi-shuttle automated storage and retrieval systems and multistage production systems where items are transported by parallel hoists. We formalize the problem, analyze its computational complexity, and develop exact and heuristic solution procedures.