A combined robot selection and scheduling problem for flow-shops with no-wait restrictions

This paper addresses a bicriteria no-wait flow-shop scheduling problem with multiple robots transferring jobs between pairs of consecutive machines. The robots share an identical track positioned alongside the machine transfer line. Each robot is assigned to a portion of the tract from which it performs job transfers between all reachable machines. We assume that job processing times are both machine and job independent, that jobs are not allowed to wait between two consecutive machines and that machine idle times are not allowed. We define a combined robot selection and scheduling problem (RSSP) for a set of Q non-identical robots characterized by different costs and job transfer and empty movement times. A solution to the RSSP problem is defined by (i) selecting a set of robots, (ii) assigning each robot to a portion of the track, and (iii) scheduling the robot moves. We define a robot schedule as feasible if all the jobs satisfy the no-wait condition and there are no machine idle times. The quality of the solutions are measured by two criteria (performance measures): makespan and robot selection cost. We study four different variations of the RSSP,one which is shown to be solvable in polynomial time while the other three turn out to be NP-hard. For the NP-hard, we show that a pseudo-polynomial time algorithm and a fully polynomial approximation scheme exists, and derive three important special cases which are solvable in polynomial time. The RSSP has aspects of robot selection, machine-robot assignment and robot movement scheduling. We believe this is the first time that this type of problem has been treated in the literature, and addresses a very important problem in multiple robotic systems operation. Our contribution lies in the formulation, methodology, algorithms for solution and complexity results which jointly treats all aspects of the problem simultaneously without the need to defer to heuristic decomposition methods.