The no-wait cyclic scheduling of delivery traffic in the grid distribution network

Abstract

This paper presents a method for the fast prototyping of no-wait cyclic schedules for periodic material handling systems with a Grid-like Material Transportation Network (GMTN). A distribution network is modeled as a grid-like system of cyclic processes performing regular pick-up and delivery operations between workstations in separate grid modules. The considered problem boils down to a job shop cyclic scheduling problem with no-buffer and no-wait constraints, which is NP-hard. The main contribution of this research is a novel method of grid-like system decomposition into subsystems with two processes using one common resource and construction of the necessary and sufficient conditions for the existence of a no-wait cyclic schedule (N-WCS) of the system for given start times of the processes. The approach's novelty involves implementing a linear-complexity procedure, which allows quick testing of whether any N-WCS may exist. Due to the low computational complexity of the procedure, it is possible to determine the start times of processes initiation for delivery networks of the scale encountered in practice and calculate corresponding cyclic schedules. A set of initial states of no-wait cyclic schedules (N-WCSs) for the systems with a grid structure of arbitrary dimensions is determined based on computational examples.

Keywords: Grid-like transportation network; Job shop cyclic scheduling problem with no-buffer and no-wait constraints; Repetitive delivery networks; VRP.