A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting. (July 2023) - Tutumlu, Busra; Saraç, Tugba
Highlights: The Flexible Job-shop Scheduling Problem with job-splitting in a way to decide each job will be split into how many sub-lots and what the size of each sub-lot is (FJSS-JS) is considered. The an integrated MIP model is proposed for FJSS-JS. A hybrid genetic algorithm is developed to solve large-sized problems. Abstract: In the scheduling literature, it is generally assumed that jobs are not split into sub-lots, or that the number and size of sub-lots are limited or predetermined. These assumptions make the problem more manageable. However, they may prevent more successful schedules. For many businesses, considering the splitting of jobs while scheduling them can create significant improvement opportunities. This study addresses the Flexible Job-Shop Scheduling Problem (FJSP) with job-splitting, determining how many sub-lots each job should be split into and the size of each sub-lot. A MIP model is proposed for the considered problem. In the model, the size and number of sub-lots of a job are not predefined or bounded. The objective function of the model is to minimize the makespan. Feasible solutions could not be found for large-sized problems by the mathematical model. So, a Hybrid Genetic Algorithm (HGA) is also proposed. In the proposed HGA, a Local Search Algorithm (LSA) that determines the size of sub-lots has been included in the GA to improve the efficiency. To show the success of the proposed HGA, its performance is compared with the classical GA.