Resolution of a Job-Shop problem with transportation constraints: a master/slave approach

The aim of this paper is to solve the job-shop scheduling problems with transportation constraints in a flexible manufacturing system. This variant is a generalization of the job-shop where the jobs have to be transported between the machines by a fleet of homogenous vehicles with unit capacity. We propose a framework based on an alternate resolution of the scheduling problem (master) modeled on a disjunctive graph by introducing a time lag (i.e., a delay between operations), and of the routing problem (slave). The objective of this study is to validate the approach as a promising method in solving such type of problems. Computational results are presented for the job-shop Laurence's instances and two set of instances dedicated to the job-shop with transportation constraints form the literature. The results show that our approach cannot in general compete with dedicated methods but provides anyway good quality results, and could be easily adapted to more general variants with capacitated vehicles or when jobs need to be transported between distant machines/sites.