A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting. (July 2023)

• Record Type: Journal Article
• Authors: Tutumlu, Busra; Saraç, Tugba
• Is Part Of: Computers & operations research. Volume 155(2023)
• Publication Date: 2023-07
• Subjects: Flexible Job Shop Scheduling Problem -- Job-Splitting -- Mixed Integer Programming -- Hybrid Genetic Algorithm -- Local Search Algorithm; ABC Artificial Bee Colony Algorithm -- Cmax Minimization of makespan -- CP Constraint Programming -- DE Differential Evolution Algorithm -- GA Genetic Algorithm -- HHA Hyper-Heuristic Algorithm -- HS Heuristic Search Algorithm -- ICA Imperialist Competitive Algorithm -- ILS Iterated Local Search -- LSA Local Search Algorithm -- PSO Particle Swarm Optimization -- SAA Simulated Annealing Algorithm -- SLS Maximization of sub-lot sizes -- TEC Total energy cost -- TFT Minimization of total flow time -- TPC Minimization of total processing cost -- TWT Total weight tardiness -- TS Tabu Search -- VNS Variable Neighborhood Search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106222
• Languages: English
• ISSNs: 0305-0548

Abstract

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.