Dynamic Scheduling Of A Robot Servicing Machines On A One-Dimensional Line

We examine the operation of a single robot servicing a finite set of machines lined up in succession. Each machine operates for a random time, gets blocked (or fails), waits for the robot, waits for the repair duration, starts operating again, and so on. We seek a dynamic decision rule which at any time, depending on the state of the whole system, will decide what action the robot should take: to repair the machine in front of it, or to move left or right, or to stop and wait. The objective is to maximize the average number of operating machines, over an infinite horizon. This problem arises in the practical context of a textile winding process. We model this system as a Markov Renewal Decision Process, and present a computational approach, based on dynamic programming, to approximate an optimal decision policy, under the assumption of exponential times to failure. We consider the case in which the robot can stop and change direction anywhere, and the case where the robot can stop or change direction only in front of a machine. Since the optimal policies turn out to be very complex, we examine simpler suboptimal rules, and compare them to the optimal policy and to other previously proposed or commonly used decision rules. For the numerical examples that we have examined, our best suboptimal rules almost always take the optimal decision, and their costs differ from the optimum by a negligible amount. For the case where the robot can stop or change direction anywhere, we used computer simulation to compare the suboptimal rules and conclude that our proposed rules are in general better than those previously proposed or commonly used.