Matheuristic Approaches for a Practical Flow Shop Scheduling Problem

Among existing shop scheduling systems, flow shop scheduling is one of the most widely used types of schedules, and it has widespread application areas including production and information services. For this reason, the Flow Shop Scheduling Problem (FSSP) remains an active research area of complex optimization problems. While in the classical FSSP often simplified factors are considered, real-world applications frequently involve more complex factors including flexible flow shop structure with multiple parallel machines per stage, unrelated machines, machines dedicated to multiple stages, machine-job compatibilities, sequence-dependent setup times, and job due dates. Thus, it is more challenging to manage real-life FSSP with the classical methods proposed in the literature. In this thesis, a practical FSSP based on a real-world industrial case study possessing the aforementioned complexities is studied. Based on the proposed formal definition and the classification of the practical FSSP, a Mixed Integer Linear Programming (MILP) model capable of representing the problem's intricate features is proposed with the objective criterion of average tardiness minimization. To mitigate the computational complexity of the problem and to construct schedules for large instances, a matheuristic method is proposed in which a novel job prioritization approach is utilized, and two different versions of the proposed MILP model with the objective criteria of average tardiness minimization and total completion time minimization, respectively are solved iteratively. To evaluate the performance of the proposed matheuristic method, comprehensive computational experiments are performed for test instances under various classifications. It is observed that satisfactory results are attained in terms of the capability of constructing schedules for test instances under various classifications and small average tardiness values obtained in the constructed schedules.