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

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.