Optimal robot scheduling to minimize the makespan in a three-machine flow-shop environment with job-independent processing times

• We study a non-cyclic three-machine robotic flow-shop scheduling problem.
• Jobs are identical and the objective is to minimize the makespan.
• A single robot is available for transferring jobs between machines.
• A set of lower bounds for the minimum objective value is provided.
• The problem is divided and an optimal schedule is provided for each subproblem.

We study a robotic three-machine flow-shop scheduling problem, in which n identical jobs are to be processed and the objective is to minimize the makespan. After the job’s completion on either the first or the second machine it is transferred by a robot to the next (consecutive) machine in the shop. A single robot is available for transferring the jobs. We show that the problem can be solved by decomposing it into a set of sub-problems, and by providing a robot schedule to each sub-problem that yields a makespan value which matches the lower bound value.