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 条
[21]   An effective two-stage memetic algorithm for the dynamic flexible job-shop scheduling problem with job inspection [J].
Peng, Ningtao ;
Zhu, Kaikai ;
Tang, Jiuqiang ;
Zheng, Yu ;
Gong, Guiliang ;
Li, Xiaobin ;
Huang, Dan ;
Liu, Gonggang .
ENGINEERING OPTIMIZATION, 2024,
[22]   An effective memetic algorithm for distributed flexible job shop scheduling problem considering integrated sequencing flexibility [J].
Tang, Jiuqiang ;
Gong, Guiliang ;
Peng, Ningtao ;
Zhu, Kaikai ;
Huang, Dan ;
Luo, Qiang .
EXPERT SYSTEMS WITH APPLICATIONS, 2024, 242
[23]   Hybrid Memetic Algorithm to Solve Multiobjective Distributed Fuzzy Flexible Job Shop Scheduling Problem with Transfer [J].
Yang, Jinfeng ;
Xu, Hua .
PROCESSES, 2022, 10 (08)
[24]   An effective reformative memetic algorithm for distributed flexible job-shop scheduling problem with order cancellation [J].
Zhu, Nan ;
Gong, Guiliang ;
Lu, Dian ;
Huang, Dan ;
Peng, Ningtao ;
Qi, Hao .
EXPERT SYSTEMS WITH APPLICATIONS, 2024, 237
[25]   A distributed flexible job shop scheduling problem considering worker arrangement using an improved memetic algorithm [J].
Luo, Qiang ;
Deng, Qianwang ;
Gong, Guiliang ;
Guo, Xin ;
Liu, Xiahui .
EXPERT SYSTEMS WITH APPLICATIONS, 2022, 207
[26]   Low carbon flexible job shop scheduling problem considering worker learning using a memetic algorithm [J].
Huan Zhu ;
Qianwang Deng ;
Like Zhang ;
Xiang Hu ;
Wenhui Lin .
Optimization and Engineering, 2020, 21 :1691-1716
[27]   An effective memetic algorithm for multi-objective job-shop scheduling [J].
Gong, Guiliang ;
Deng, Qianwang ;
Chiong, Raymond ;
Gong, Xuran ;
Huang, Hezhiyuan .
KNOWLEDGE-BASED SYSTEMS, 2019, 182
[28]   Solving the energy-aware flexible job shop problem using a memetic algorithm [J].
Afsar, Sezin ;
Puente, Jorge ;
Palacios, Juan Jose ;
Gonzalez-Rodriguez, Ines ;
Vela, Camino R. .
INTEGRATED COMPUTER-AIDED ENGINEERING, 2025,
[29]   A multi-disjunctive-graph model-based memetic algorithm for the distributed job shop scheduling problem [J].
Wang, Sihan ;
Li, Xinyu ;
Gao, Liang ;
Li, Jiahang .
ADVANCED ENGINEERING INFORMATICS, 2024, 60
[30]   A three-stage adaptive memetic algorithm for multi-objective optimization of flexible assembly job-shop scheduling problem [J].
Zhang, Chenlu ;
Feng, Jiamei ;
Zhang, Mingchuan ;
Yang, Lei ;
Zhang, Lei ;
Wang, Lin ;
Zhu, Junlong ;
Wu, Qingtao .
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2025, 144
12345