A memetic algorithm for the job-shop with time-lags

被引:44
作者
Caumond, Anthony [1 ]
Lacomme, Philippe [1 ]
TcherneVa, Nikolay [1 ,2 ]
机构
[1] LIMOS, UMR CNRS 6158, Lab Informat, F-63177 Clermont Ferrand, France
[2] Univ Auvergne, IUP, F-63008 Clermont Ferrand, France
关键词
scheduling; job-shop problem; time-lags;
D O I
10.1016/j.cor.2006.11.007
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The job-shop with time-lags (JS vertical bar t) is defined as a job-shop problem with minimal and maximal delays between starting times of operations. In this article, time-lags between successive operations of the same job (JS vertical bar t(i,si)) are studied. This problem is a generalization of the job-shop problem (null minimal time-lags and infinite maximal time-lags) and the no-wait job-shop problem (null minimal and maximal time-lags). This article introduced a framework based on a disjunctive graph to modelize the problem and on a memetic algorithm for job sequence generation on machines. Our aim is to provide, also a framework to cover both job-shop and flow-shop problem and to encompass both no-wait and classical instances. A benchmark has been carried out on medium scale instances proving that high quality solutions can be obtained in short computational time. The framework we introduce competes with some methods dedicated to the no-wait job-shop instances and flow-shop instances in terms of quality of results. (C) 2006 Elsevier Ltd. All rights reserved.
引用
收藏
页码:2331 / 2356
页数:26
相关论文
共 21 条
[11]   ON THE JOB-SHOP SCHEDULING PROBLEM [J].
MANNE, AS .
OPERATIONS RESEARCH, 1960, 8 (02) :219-223
[12]   Job-shop scheduling with blocking and no-wait constraints [J].
Mascis, A ;
Pacciarelli, D .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 143 (03) :498-517
[13]  
Rebaine D, 1999, J OPER RES SOC, V50, P756, DOI 10.1057/palgrave.jors.2600769
[14]  
Reddy US, 2003, LECT NOTES COMPUT SC, V2618, P223
[15]   A GENETIC ALGORITHM FOR FLOWSHOP SEQUENCING [J].
REEVES, CR .
COMPUTERS & OPERATIONS RESEARCH, 1995, 22 (01) :5-13
[16]   Time lag size in multiple operations flow shop scheduling heuristics [J].
Riezebos, J ;
Gaalman, GJC .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 105 (01) :72-90
[17]   Approximative procedures for no-wait job shop scheduling [J].
Schuster, CJ ;
Framinan, JM .
OPERATIONS RESEARCH LETTERS, 2003, 31 (04) :308-318
[18]   JOB SHOP SCHEDULING BY SIMULATED ANNEALING [J].
VANLAARHOVEN, PJM ;
AARTS, EHL ;
LENSTRA, JK .
OPERATIONS RESEARCH, 1992, 40 (01) :113-125
[19]   ONE-MACHINE GENERALIZED PRECEDENCE CONSTRAINED SCHEDULING PROBLEMS [J].
WIKUM, ED ;
LLEWELLYN, DC ;
NEMHAUSER, GL .
OPERATIONS RESEARCH LETTERS, 1994, 16 (02) :87-99
[20]   A 2-MACHINE FLOWSHOP SEQUENCING PROBLEM WITH LIMITED WAITING TIME CONSTRAINTS [J].
YANG, DL ;
CHERN, MS .
COMPUTERS & INDUSTRIAL ENGINEERING, 1995, 28 (01) :63-70