We address a real-world problem of scheduling mobile robots in continuous production environment in which robots travel around to provide services, such as transporting material to manufacturing machines. As the production process is continuous, the robots need to make multiple trips and the planning horizon for scheduling will thus be long. In addition, the tasks requested by machines have their own strict time windows for robots to finish. In this paper, we propose a novel approach for scheduling robots in such environment, which consists of two parts: the first is the framework called Short-Planning-Window to split the long horizon problem into multiple small problems; the second is a new two-index mixed integer programming (MIP) model for scheduling robots in small or middle length of planning horizon. Our numerical results show the two-index MIP model can obtain optimal solutions in seconds for the small/middle planning horizon problems, for which existing three-index MIP model in the literature need hours or even cannot get optimal solutions. For long planning horizon problems, our method is also better than the Genetic Algorithm proposed in the literature. In summary, our approach provides a scalable and effective solution for large-scale practical problems.
This research was supported by A*STAR Industrial Internet of Things Research Program, Singapore.