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

摘要

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.