Behind the Scenes of Deadline24: A Memetic Algorithm for the Modified Job Shop Scheduling Problem

被引：0
作者：
Nalepa, Jakub [1 ,2 ,3 ]
Cwiek, Marcin [2 ,3 ]
Zak, Lukasz [2 ,3 ]
机构：
[1] Silesian Tech Univ, Gliwice, Poland
[2] Deadline24, Gliwice, Poland
[3] Future Proc, Gliwice, Poland
来源：
MAN-MACHINE INTERACTIONS 5, ICMMI 2017 | 2018年 / 659卷
关键词：
Job shop sheduling problem; Memetic algorithm; Workflow modeling; Benchmark generation; SEARCH;
D O I：
10.1007/978-3-319-67792-7_49
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Job shop scheduling problem (JSSP) is an NP-hard optimization problem which has been widely studied in the literature due to its practical applicability. In this paper, we show how to model a workflow using a modified version of JSSP, in which a given operation may be executed on a number of different machines. Solving the instances of this modified JSSP, elaborated using our benchmark generation routine, constituted a qualifying task of the Deadline24 programming marathon. In the experimental study, we confront the results submitted by the participants with the solutions obtained using our memetic algorithms and other solvers. This analysis is backed up with the statistical tests.
引用
收藏
页码：502 / 512
页数：11
相关论文
共 50 条
[31]   Algorithm Based on Improved Genetic Algorithm for Job Shop Scheduling Problem [J].
Chen, Xiaohan ;
Zhang, Beike ;
Gao, Dong .
2019 IEEE INTERNATIONAL CONFERENCE ON MECHATRONICS AND AUTOMATION (ICMA), 2019, :951-956
[32]   Two-stage memetic algorithm for green flexible job shop scheduling problem considering machine deterioration and maintenance [J].
Zhu, Guoqiang ;
Liu, Jianfeng ;
Gong, Wenyin .
MEMETIC COMPUTING, 2025, 17 (02)
[33]   A DQN-based memetic algorithm for energy-efficient job shop scheduling problem with integrated limited AGVs [J].
Yao, Youjie ;
Li, Xinyu ;
Gao, Liang .
SWARM AND EVOLUTIONARY COMPUTATION, 2024, 87
[34]   A heuristic algorithm for solving flexible job shop scheduling problem [J].
Ziaee, Mohsen .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2014, 71 (1-4) :519-528
[35]   Adaptive multimeme algorithm for flexible job shop scheduling problem [J].
Zuo, Yi ;
Gong, Maoguo ;
Jiao, Licheng .
NATURAL COMPUTING, 2017, 16 (04) :677-698
[36]   A new hybrid genetic algorithm for job shop scheduling problem [J].
Ren Qing-dao-er-ji ;
Wang, Yuping .
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (10) :2291-2299
[37]   Genetic algorithm applications on Job Shop Scheduling Problem: A Review [J].
Bhatt, Nisha ;
Chauhan, Nathi Ram .
2015 INTERNATIONAL CONFERENCE ON SOFT COMPUTING TECHNIQUES AND IMPLEMENTATIONS (ICSCTI), 2015,
[38]   Adaptive multimeme algorithm for flexible job shop scheduling problem [J].
Yi Zuo ;
Maoguo Gong ;
Licheng Jiao .
Natural Computing, 2017, 16 :677-698
[39]   An improved memetic algorithm for multi-objective resource-constrained flexible job shop inverse scheduling problem: An application for machining workshop [J].
Wei, Shupeng ;
Tang, Hongtao ;
Li, Xixing ;
Lei, Deming ;
Wang, Xi Vincent .
JOURNAL OF MANUFACTURING SYSTEMS, 2024, 74 :264-290
[40]   Memetic algorithms for solving job-shop scheduling problems [J].
Hasan S.M.K. ;
Sarker R. ;
Essam D. ;
Cornforth D. .
Memetic Computing, 2009, 1 (1) :69-83
12345