Lateness minimization with Tabu search for job shop scheduling problem with sequence dependent setup times

被引:0
作者
Miguel A. González
Camino R. Vela
Inés González-Rodríguez
Ramiro Varela
机构
[1] University of Oviedo,Department of Computing, Computing Technologies Group, Artificial Intelligence Center
[2] University of Cantabria,Department of Mathematics, Statistics and Computing
来源
Journal of Intelligent Manufacturing | 2013年 / 24卷
关键词
Scheduling; Tabu search; Setup times; Lateness minimization; Computational experiments;
D O I
暂无
中图分类号
学科分类号
摘要
We tackle the job shop scheduling problem with sequence dependent setup times and maximum lateness minimization by means of a tabu search algorithm. We start by defining a disjunctive model for this problem, which allows us to study some properties of the problem. Using these properties we define a new local search neighborhood structure, which is then incorporated into the proposed tabu search algorithm. To assess the performance of this algorithm, we present the results of an extensive experimental study, including an analysis of the tabu search algorithm under different running conditions and a comparison with the state-of-the-art algorithms. The experiments are performed across two sets of conventional benchmarks with 960 and 17 instances respectively. The results demonstrate that the proposed tabu search algorithm is superior to the state-of-the-art methods both in quality and stability. In particular, our algorithm establishes new best solutions for 817 of the 960 instances of the first set and reaches the best known solutions in 16 of the 17 instances of the second set.
引用
收藏
页码:741 / 754
页数:13
相关论文
共 50 条
[41]   A tabu search method guided by shifting bottleneck for the job shop scheduling problem [J].
Pezzella, F ;
Merelli, E .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 120 (02) :297-310
[42]   A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem [J].
Zhang, ChaoYong ;
Li, PeiGen ;
Guan, ZaiLin ;
Rao, YunQing .
COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (11) :3229-3242
[43]   HEURISTICS IN FLOW-SHOP SCHEDULING WITH SEQUENCE DEPENDENT SETUP TIMES [J].
SIMONS, JV .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1992, 20 (02) :215-225
[44]   Integrating preventive maintenance activities to the no-wait flow shop scheduling problem with dependent-sequence setup times and makespan minimization [J].
Miyata, Hugo Hissashi ;
Nagano, Marcelo Seido ;
Gupta, Jatinder N. D. .
COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 135 :79-104
[45]   Flexible job shop scheduling with tabu search algorithms [J].
Mohammad Saidi-Mehrabad ;
Parviz Fattahi .
The International Journal of Advanced Manufacturing Technology, 2007, 32 :563-570
[46]   Single machine scheduling with major and minor setup times: A tabu search approach [J].
Nowicki, E ;
Zdrzalka, S .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1996, 47 (08) :1054-1064
[47]   Tabu search and lower bound for an industrial complex shop scheduling problem [J].
Prot, D. ;
Bellenguez-Morineau, O. .
COMPUTERS & INDUSTRIAL ENGINEERING, 2012, 62 (04) :1109-1118
[48]   Flexible job shop scheduling with tabu search algorithms [J].
Saidi-Mehrabad, Mohammad ;
Fattahi, Parviz .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2007, 32 (5-6) :563-570
[49]   Tabu Search Algorithm with Neural Tabu Mechanism for the Cyclic Job Shop Problem [J].
Bozejko, Wojciech ;
Gnatowski, Andrzej ;
Nizynski, Teodor ;
Wodecki, Mieczyslaw .
ARTIFICIAL INTELLIGENCE AND SOFT COMPUTING, (ICAISC 2016), PT II, 2016, 9693 :409-418
[50]   A comparison between ant colony and tabu search algorithms for job shop scheduling with sequence-dependent setups [J].
Department of Mechanical Engineering, Ferdowsi University of Mashhad, Mashhad, Iran .
WSEAS Trans. Syst., 2006, 12 (2819-2824)