A Batch Scheduling Model for a Three-stage Hybrid Flowshop Producing Products with Hierarchical Assembly Structures

This paper addresses a batch scheduling problem for a three-stage hybrid flowshop consisting of a machining stage processing common and unique components on unrelated parallel machines, an assembly stage combining the components into assembled products with complex assembly structures, and a differentiation stage processing the assembled products on dedicated machines to produce different product types. The common components are the same for all products and are processed in batches, while the unique components are dedicated to respective given product types and are processed individually (one-by-one component). The goal is to schedule all the products with different assembly structures to minimize total actual flow time (TAFT) defined as total time interval of components to be processed from their arrival times to their common due date. A non-linear programming model is proposed, where small size problems can be solved optimally using the LINGO software, and large size problems is to be solved using a heuristic algorithm. The proposed algorithm consists of two sub-algorithms. The first one is constructed using a shortest processing time (SPT) based heuristic to get a job sequence as an initial solution and the second one is to improve the initial solution using the variable neighbourhood descent (VND) method with neighbourhood insert and swap move operators. In solving the problem with the algorithm, two scenarios arise, e.g., the same and the different sequences for all stages. A set of hypothetical data is generated for different hierarchical assembly structures to test the model and the algorithm, and the results show that the different sequences for all stages obtain solutions with better performances than the same ones.