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 条
  • [1] Adaptive Memetic Algorithm for the Job Shop Scheduling Problem
    Nalepa, Jakub
    Cwiek, Marcin
    Kawulok, Michal
    2015 INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS (IJCNN), 2015,
  • [2] An efficient memetic algorithm for solving the job shop scheduling problem
    Gao, Liang
    Zhang, Guohui
    Zhang, Liping
    Li, Xinyu
    COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 60 (04) : 699 - 705
  • [3] Solving the Flexible Job Shop Scheduling Problem Based on Memetic Algorithm
    Zhang, Guohui
    ADVANCES IN PRODUCT DEVELOPMENT AND RELIABILITY III, 2012, 544 : 1 - 5
  • [4] A Multi-objective Memetic Algorithm for the Job-Shop Scheduling Problem
    Frutos, Mariano
    Tohme, Fernando
    OPERATIONAL RESEARCH, 2013, 13 (02) : 233 - 250
  • [5] A Memetic Algorithm for the Multi-Objective Flexible Job Shop Scheduling Problem
    Yuan, Yuan
    Xu, Hua
    GECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2013, : 559 - 566
  • [6] An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers
    Luo, Qiang
    Deng, Qianwang
    Gong, Guiliang
    Zhang, Like
    Han, Wenwu
    Li, Kexin
    EXPERT SYSTEMS WITH APPLICATIONS, 2020, 160
  • [7] A Self-Adaptive Memetic Algorithm for Distributed Job Shop Scheduling Problem
    Wang, Guangchen
    Wang, Peng
    Zhang, Honggang
    MATHEMATICS, 2024, 12 (05)
  • [8] An improved memetic algorithm for the flexible job shop scheduling problem with transportation times
    Zhang, Guohui
    Sun, Jinghe
    Lu, Xixi
    Zhang, Haijun
    MEASUREMENT & CONTROL, 2020, 53 (7-8): : 1518 - 1528
  • [9] A parallel memetic algorithm with explicit management of diversity for the job shop scheduling problem
    Oscar Hernández Constantino
    Carlos Segura
    Applied Intelligence, 2022, 52 : 141 - 153
  • [10] A parallel memetic algorithm with explicit management of diversity for the job shop scheduling problem
    Hernandez Constantino, Oscar
    Segura, Carlos
    APPLIED INTELLIGENCE, 2022, 52 (01) : 141 - 153
12345