A dynamic branch and bound approach for robotic rescheduling with randomly arriving jobs

This paper addresses a rescheduling problem in a robotic cell where a material handling robot is responsible to transport parts from one workstation to another and the different jobs (parts) arrive at the cell randomly. Our objective is to minimize the total completion time of all the jobs by dynamically changing the current schedule. Following a robotic rescheduling framework to find a new schedule, the problem is reduced to resolving a local deterministic robotic scheduling problem to minimize the total completion time. After that the local problem is formulated, according to the processing recipes of the jobs and the state of the robotic cell. We propose a branch and bound algorithm with a dynamic enumeration mechanism to solve the localized problem. Our proposed algorithm is evaluated by a numerical example.