Scheduling flexible flow lines with no in-process buffers

An heuristic algorithm is proposed for scheduling a flexible flow line with no intermediate buffers. The line is made up of several processing stages in series, where each stage has one or more identical parallel machines. In the line different part types can be manufactured simultaneously, each of which is processed by at most one machine in every stage. Intermediate queues of parts waiting between the stages for their next operations are not allowed. The problem objective is to minimize the makespan of the schedule for a set of part types selected for processing. The algorithm proposed is a part-by-part heuristic, in which during every iteration a complete processing schedule is determined for one part type selected for loading into the line. The selection of the part type and its complete schedule are based on the cumulative partial schedule obtained for all parts selected so far. The decisions in every iteration are made using a local optimization procedure aimed at minimizing total blocking and waiting time of the machines along the route of the selected part type. The efficiency of the algorithm is tested on several groups of random test problems.