TSP-based scheduling in a batch-wise automated Hybrid Flow-Shop

摘要

The problem presented extends the Hybrid Flow-Shop (HFS) scheduling problem class by considering the case in which production jobs are grouped in batches and, within each batch, sequentially machined. We consider a two stage system, in which the first stage is parallel and includes two identical machines, while the second one is a bottleneck stage, including a single machine. The performance objective is to minimize the makespan. Moreover, each job is assigned to a predefined batch and the job working sequence within each batch is known and assigned. A variant of the Traveling Salesman Problem (TSP) is used to model the problem and to develop an effective heuristics. Unlike standard TSP, no pre-defined cost matrix can be provided. The proposed approach has been tested on industrial cases provided by a manufacturing firm. Computational results have been benchmarked with results achieved with several possible alternative approaches to the problem, proving the effectiveness of the proposed heuristics.