Makespan Minimisation in Hybrid Flexible Flowshops with Buffers and Machine-Dependent Transportation Times

Overview & Synopsis

Hybrid Flexible Flowshop Scheduling (HFFS) is the problem where a set of jobs must be processed in a given sequence of stages and each stage has a set of (typically identical) parallel machines. The flexibility of HFFS allows a job to skip some stages. Modern production environments, e.g., assembly lines, exhibit additional structure, namely limited-capacity buffers and transportation times between subsequent stages, while the layout also imposes that such times are machine-to-machine dependent. We propose two formal models, namely a Mixed-Integer Linear Program (MILP) that incorporates transportation times but not buffers and a Constraint Program (CP) that handles both, given a sequence of all jobs per machine. This sequence is provided by the MILP or constructive heuristics or a Genetic Algorithm (GA). The scalability and performance of all methods is evaluated computationally on large-scale real-life instances of about 500 jobs on 15 stages with up to 5 machines per stage and 30 machines in total.