The no-wait cyclic scheduling of delivery traffic in the grid distribution network. (December 2022)

• Record Type: Journal Article
• Authors: Wójcik, Robert; Pempera, Jarosław; Bocewicz, Grzegorz; Banaszak, Zbigniew
• Is Part Of: ISA transactions. Volume 131(2022)
• Page Start: 282
• Page End: 298
• Publication Date: 2022-12
• Subjects: Repetitive delivery networks -- Grid-like transportation network -- VRP -- Job shop cyclic scheduling problem with no-buffer and no-wait constraints; Engineering instruments -- Periodicals; Engineering instruments; Periodicals; Electronic journals; 629.805
• DOI: 10.1016/j.isatra.2022.05.031
• Languages: English
• ISSNs: 0019-0578

Abstract

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. Highlights: Considered problem is no-wait cyclic schedules for a Grid-like Material Transportation Network. Cyclic scheduling problem with no-wait constraints, is NP-hard especially for grid-like systems. The contribution is a method of grid-like system decomposition into subsystems. The novelty of the method lies in its implementation as a linear-complexity procedure. The method was verified of the examples of the practical grid-like systems.