Structural Decomposition Approach to Design of No-Wait Cyclic Schedules for Repeatedly Operating Transport System Dedicated to Supply Loops

摘要

The paper presents a method allowing to construct no-wait cyclical schedules for repetitive transport systems (e.g. the milk-run) servicing cyclic material supply loops in the production system using selected means of transport (e.g. AGVs). The transport means are following established routes and given arrival times. The routes are composed of sectors linking workstations. Transport trolleys may share specific sectors of the route in mutual exclusion mode and must wait in a given sector to enter the next sector of the route when another trolley occupies it. The job-shop repetitive transportation system is a system of cyclic processes with a fixed structure that are executing sequences of operations (routes) using shared resources (sectors). The work aims to find a no-wait cyclic schedule that guarantees the required delivery dates or establish that such a schedule does not exist. It considers cyclic process systems for which each resource can be used by at most two operations, and the deadlock state cannot occur as a result of waiting processes on shared resources. For specified initial operations of cyclic processes and their start times (the initial system state), the problem of determining no-wait cyclical schedules decomposes into subproblems. Each subproblem consists of the verification of necessary and sufficient conditions for the existence of solutions for each of 2-process subsystems composed of one shared resource and two processes using this resource. The method aims of prototyping various variants of process starting times for which the conditions guaranteeing no-wait property of the system hold simultaneously for each of the 2-process subsystems. It allows designing cyclic schedules for complex systems composed of 2-process subsystems that are structurally deadlock-free. The class of cyclical processes considered in this article is broader than the class of cascade-like (chain-like, sequential) process systems analysed so far in the literature. In this context, the results obtained are an extension of the existing ones.