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

Pierre L’Ecuyer, Marcel Mayrand, Moshe Dror

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)371-382
Number of pages12
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number4
StatePublished - Dec 1991

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Dynamic Scheduling Of A Robot Servicing Machines On A One-Dimensional Line'. Together they form a unique fingerprint.

Cite this