A Heuristic Algorithm for a Two-Machine Flowshop Scheduling Problem with a Bounded Intermediate Station

Abstract

In this paper we deal with a two-machine robotic unit of flowshop type, in which each of n jobs is processed on the first machine and later on the second machine. Transportation of the jobs in this flowshop is performed by robots. There is an intermediate station with its capacity bound Q (1?Q?∞) between the two machines for intermediate operations such as washing, chip disposal, cooling, drying and/or quenching. The bounded intermediate station can process at most Q jobs at a time. The permutaion scheduling problem of minimizing the makespan (i.e., the maximum completion time of all jobs) is NP-hard for any fixed Q, although it has been known that the problem can be solved in O (n2) time if the intermediate station is unbounded (i.e., Q=∞). In this paper, we propose a heuristic algorithm for the problem with the bounded intermediate station. The performance of the proposed heuristic is examined by means of numerical experiments, and the results are reported.