Fixed sequence integrated production and routing problems

International audienceThe problem considered in this paper can be described as follows. A set of n jobs must be produced by a single machine and then delivered by a single vehicle.. Each job j requires a certain processing time pj on a the machine, and must be delivered after its completion to the location j. We denote by t ij the transportation time from destination i to destination j. We use M to denote the depot (manufacturer) and we assume that transportation times are symmetric and satisfy the triangle inequality. The set of jobs delivered during a single round trip constitutes a batch. The vehicle has a capacity c which is the maximum number of jobs it can load and hence deliver in a round trip. These models for coordinating production and delivery schedules have been largely analyzed and reviewed by Chen [2], who proposed a detailed classifcation scheme. In this paper the production sequence is fixed and the jobs must be delivered in the order in which they are released, hence a production sequence also specifes the sequence in which the customers have to be reached. Since the production sequence is given, the problem consists in determining a partition of all jobs into batches, and each batch will then be routed according to the manufacturing sequence. We study the complexity of the problem and of special case