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

被引:22
作者
Tutumlu, Busra [1 ]
Sarac, Tugba [2 ]
机构
[1] Kutahya Dumlupinar Univ, Fac Engn, Dept Ind Engn, TR-43100 Kutahya, Turkiye
[2] Eskisehir Osmangazi Univ, Fac Engn & Architecture, Dept Ind Engn, TR-26480 Eskisehir, Turkiye
关键词
Flexible Job Shop Scheduling Problem; Job-Splitting; Mixed Integer Programming; Hybrid Genetic Algorithm; Local Search Algorithm; OPTIMIZATION;
D O I
10.1016/j.cor.2023.106222
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
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.
引用
收藏
页数:12
相关论文
共 37 条
[1]   Flexible Job Shop Scheduling Problem with Sequence Dependent Setup Time and Job Splitting: Hospital Catering Case Study [J].
Abderrabi, Fatima ;
Godichaud, Matthieu ;
Yalaoui, Alice ;
Yalaoui, Farouk ;
Amodeo, Lionel ;
Qerimi, Ardian ;
Thivet, Eric .
APPLIED SCIENCES-BASEL, 2021, 11 (04) :1-27
[2]   Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems [J].
Amjad, Muhammad Kamal ;
Butt, Shahid Ikramullah ;
Kousar, Rubeena ;
Ahmad, Riaz ;
Agha, Mujtaba Hassan ;
Zhang Faping ;
Anjum, Naveed ;
Asgher, Umer .
MATHEMATICAL PROBLEMS IN ENGINEERING, 2018, 2018
[3]   Flexible job shop scheduling with lot streaming and sublot size optimisation [J].
Bozek, Andrzej ;
Werner, Frank .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2018, 56 (19) :6391-6411
[4]   JOB-SHOP SCHEDULING WITH MULTIPURPOSE MACHINES [J].
BRUCKER, P ;
SCHLIE, R .
COMPUTING, 1990, 45 (04) :369-375
[5]   A research survey: review of flexible job shop scheduling techniques [J].
Chaudhry, Imran Ali ;
Khan, Abid Ali .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2016, 23 (03) :551-591
[6]   Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming [J].
Chen, Tzu-Li ;
Cheng, Chen-Yang ;
Chou, Yi-Han .
ANNALS OF OPERATIONS RESEARCH, 2020, 290 (1-2) :813-836
[7]   A review of lot streaming [J].
Cheng, M. ;
Mukherjee, N. J. ;
Sarin, S. C. .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2013, 51 (23-24) :7023-7046
[8]   Scheduling in a flexible job shop followed by some parallel assembly stations considering lot streaming [J].
Daneshamooz, Fatemeh ;
Fattahi, Parviz ;
Hosseini, Seyed Mohammad Hassan .
ENGINEERING OPTIMIZATION, 2022, 54 (04) :614-633
[9]   Jobshop lot streaming with routing flexibility, sequence-dependent setups, machine release dates and lag time [J].
Defersha, Fantahun M. ;
Chen, Mingyuan .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2012, 50 (08) :2331-2352
[10]   A matheuristic for flexible job shop scheduling problem with lot-streaming and machine reconfigurations [J].
Fan, Jiaxin ;
Zhang, Chunjiang ;
Shen, Weiming ;
Gao, Liang .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2023, 61 (19) :6565-6588