Risk-conscious scheduling of robotic cells with bounded work-in-process in stochastic environment

This study addresses cyclic scheduling in robotic cells with bounded work-in-process levels in stochastic environment, where operations durations are randomly distributed in given intervals. The objective is two-fold: first, to find a schedule for completing all the operations with minimum cycle time (or, equivalently, maximizing the cell throughput), and second, to assess the probability (the risk) that the cycle time will exceed a prescribed due date. We first present new low-degree polynomial algorithms minimizing the cycle time for deterministic input data. We reformulate the original scheduling problem in graph terms and establish relationship between the minimum cycle time and a critical path length in an induced graph. Then we develop the Monte Carlo simulation of operation durations which, in combination with the developed algorithm for finding the cyclic critical path, permits us to assess the expected risk.