Distributed permutation flowshop scheduling problems

This thesis investigates three complex scheduling problems encountered in distributed manufacturing systems, each characterized by no-wait constraints, sequence-dependent setup times, and multi-factory job assignments. These features significantly increase computational complexity beyond that of classical flowshop models. To address these challenges, each chapter proposes specialized mathematical formulations and metaheuristic algorithms, validated through extensive computational experiments using standard benchmark datasets. The first part of the thesis focuses on the distributed no-wait flowshop scheduling problem with sequence-dependent setup times (SDST-DNWFSP), where the objective is to minimize a linear combination of total completion time and maximum tardiness. The problem is modeled using an enhanced ATSP-based formulation incorporating valid inequalities to improve model efficiency. A hybrid Branch-and-Cut integrated with Variable Neighborhood Descent (BC/VND) algorithm is proposed to solve small-sized instances effectively, outperforming an existing MILP model. For larger-scale problems, a standalone VND/NL heuristic demonstrates superior scalability and solution quality. The second part addresses the distributed no-idle permutation flowshop scheduling problem (DNIPFSP), a generalized form of both DPFSP and NIPFSP. To bridge the gap in the literature, the study introduces three MILP models—one being an improved position-based model (IV_PBM)—and a GRASP metaheuristic featuring LS3-based local search. The heuristic solutions are used to derive upper bounds that restrict the feasible space of IV_PBM, forming a tighter model variant (RIV_PBM). Both classical and hybrid Bender's decomposition algorithms are applied to solve these models, with the hybrid approach achieving superior convergence and solution accuracy. The final part introduces GRASP_VND, a novel hybrid metaheuristic for solving DNWFSP. The method integrates a time-adaptive greedy randomized construction phase, a destroy-and-repair mechanism, and LS3-based Variable Neighborhood Descent to balance diversification and intensification. Critical parameters such as greediness (αt) and destruction size (dt) are adaptively tuned using Bayesian Optimization (BO), enabling robust performance across varying instance types. Tests on 660 benchmark problems show that GRASP_VND achieves the lowest ARPD and the highest number of near-optimal solutions among state-of-the-art heuristics. With its structural flexibility and minimal parameter tuning requirements, GRASP_VND offers a scalable and practical tool for solving large-scale and complex scheduling problems.