A GA-based heuristic algorithm for non-permutation two-machine robotic flow-shop scheduling problem of minimizing total weighted completion time

Abstract

We discuss a scheduling problem for a two-machine robotic flow-shop with a bounded intermediate station and robots which is realistic in FMCs (flexible manufacturing cells). The problem asks to minimize the total weighted completion time. It is NP-hard. In this paper, we propose a heuristic algorithm based on GA (Genetic Algorithm) which is applicable to the problem, and which allows not only permutation, but also non-permutation schedules, because the latter has possibility to improve the former for this objective function. It is shown by numerical experiment that the proposed method is more effective than existing heuristics, and that there are some situations where the non-permutation scheduling is better than the permutation one.