A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting

Tutumlu B., SARAÇ T.

Computers and Operations Research, vol.155, 2023 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 155
  • Publication Date: 2023
  • Doi Number: 10.1016/j.cor.2023.106222
  • Journal Name: Computers and Operations Research
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, PASCAL, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Keywords: Flexible Job Shop Scheduling Problem, Hybrid Genetic Algorithm, Job-Splitting, Local Search Algorithm, Mixed Integer Programming
  • Eskisehir Osmangazi University Affiliated: Yes


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.