EFFICIENT ALGORITHMS FOR THE MULTI-STAGE FLEXIBLE FLOW SHOP SCHEDULING PROBLEM WITH TRANSPORTATION AND UNLOADING TIMES

Improving efficiency in multi-stage flexible flowshop operations is essential for modern industrial systems. Optimizing total completion time while simultaneously considering the unloading and transportation times is vital for enhanced productivity and cost-effectiveness. This study delves into the intricate realm of flexible flow shop scheduling, particularly focusing on scenarios prevalent in modern manufacturing processes such as sand casting. Despite limited exploration in prior literature for particular cases, the significance of this problem underscores the pressing need for efficient algorithms and the exploration of new problem properties. Notably, we unveil the symmetry inherent in the problem, where scheduling from the initial stage to the final one, or vice versa, yields identical optimal solutions, thereby augmenting solution quality. Given the strongly NP- Hard nature of the problem, approximate solutions are preferred, especially for medium to large-scale instances. To address this challenge, we propose a novel two-phase heuristic approach, encompassing both a constructive phase and an improvement phase. Leveraging an existing efficient heuristic tailored for parallel machine scheduling, our method extends to efficiently incorporate considerations for unloading and transportation times. The efficacy of the two-phase heuristic lies in its ability to consistently generate high-quality schedules at each stage. Furthermore, we introduce efficient lower bounds derived from estimating the minimum idle time within each stage, drawing from insights in polynomial parallel machine scheduling with a focus on flow time minimization in preceding stages. These lower bounds serve as critical benchmarks for evaluating the performance of the two-phase heuristic against the relative gap performance measure. Extensive experimentation on benchmark test problems underscores the effectiveness of our proposed algorithms, with results demonstrating an average computation time of 9.48 seconds and a mean relative gap of only 2.42% across varying job and stage quantities up to 200 jobs and 10 stages.