Azeddine Cheref

Christian Artigues

Jean-Charles Billaut

Sandra Ulrich

Sandra Ulrich Ngueveu
email: ngueveu@laas.frjean-charles.billaut@univ-tours.fr

hal

Keywords: Integrated production and distribution, Complexity, Column generation

HAL is

Integrated production scheduling and delivery routing: complexity results and column generation 1 Introduction

This paper considers an integrated model of scheduling and delivery, where jobs are scheduled on a single machine and finished products are delivered from the manufacturer to multiple customer locations. The relationship between production and distribution being strong, an increasing amount of research has been devoted to this field during the last years. The problem has been largely analysed and reviewed in [START_REF] Chen | Integrated Production and Outbound Distribution Scheduling: Review and Extensions[END_REF], where the author proposes a classification scheme for a variety of issues reflected by these models. In this paper, jobs are scheduled on a single machine and preemption is not allowed. Different processing times, sizes and delivery destinations are associated to the jobs. Distribution is performed by a single vehicle with a limited capacity and can be seen as a variant of the multitrip vehicle routing problem [START_REF] Lysgaard | A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem[END_REF], in which deliveries are ensured by a single vehicle and with a constrained batching phase. Delivery costs are not taken into account in this paper but the total time required to complete the production and the delivery of the products and the total delivery time are both meaningful indicators of the overall efficiency of the delivery process. Therefore, the objectives of the proposed problems are to find a coordinated production and delivery schedule that minimize the total completion time (makespan) or the sum of the delivery times of the products.

We review below a few relevant papers.

In [START_REF] Li | Machine scheduling with deliveries to multiple customer locations[END_REF], a similar model is considered but the size of jobs is not included and the authors propose a polynomial time algorithm in the case of a fixed number of distinct destinations. In [START_REF] Gao | Integrated batch production and distribution scheduling with limited vehicle capacity[END_REF], the authors consider the problem of minimizing the makespan on a single machine scheduling problem with a unique capacitated vehicle and a no wait constraint. No wait constraints implies that the batch must be delivered at its completion time. In [START_REF] Geismar | The Integrated Production and Transportation Scheduling Problem for a Product with a Short Lifespan[END_REF], an heuristic method is proposed for minimizing the makespan when lifespan constraints are introduced for the products. Most of the models presented in the literature explicitly take into account transportation times to reach the customer's location, but there are no proper routing decisions, since the number of distinct customers is typically very small. Hence, the focus of the analysis is often on scheduling and batching. In [START_REF] Hall | Scheduling with Fixed Delivery Dates[END_REF], the authors consider the problem in which the delivery dates are fixed in advance and in [START_REF] Chen | Logistics scheduling with batching and transportation[END_REF], there are various destinations but a batch must contain jobs of the same destination. Complexity results are given by [START_REF] Chang | Machine scheduling with job delivery coordination[END_REF] for the problem with a single vehicle, a storage area and one or two customers. In [START_REF] Li | Machine scheduling with pickup and delivery[END_REF], the authors minimize the makespan for the one machine scheduling problem with pickup and delivery in which a single vehicle travels between the machines and the warehouse, whereas in [START_REF] Wang | Production scheduling with supply and delivery considerations to minimize the makespan[END_REF], the authors study a similar problem in which three different locations and two vehicles are considered. The first vehicle transports unprocessed jobs between the warehouse and the factory and the second one transports finished jobs between the factory and the customer. Some models in the literature treat a coordinating problem in which the customer sequence is fixed. For example, in [START_REF] Armstrong | A zero-inventory production and distribution problem with a fixed customer sequence[END_REF] and [START_REF] Viergutz | Integrated production and distribution scheduling with lifespan constraints[END_REF], the authors minimize the total satisfied demand in a single round trip, the authors consider that the products expire in a constant time after their completion time and a time window delivery for each product.

The problem is formally defined in section 2. We present in Section 3 some complexity results for particular cases and in section 4 a column generation scheme to solve a relaxed version of the problem, leading to a lower bound of high quality. Computational results are given in Section 5.

Problem definition and notations

We consider a set of n jobs J = {J 1 , J 2 , . . . , J n } to be processed on a single machine and delivered to a set of n corresponding customers. Each job J j , j = 1, . . . , n, requires a certain processing time p j . Delivery is performed by a single vehicle with capacity c. As mentioned before, there is a set of n customer locations and each job J j , j = 1, . . . , n, is additionally characterized by its location j and its size s j where 0 ≤ s j ≤ c. We denote by t ij the transportation time from location i to location j and D j the arrival time (decision variable) to the location j ,i.e. the delivery time of J j . We use M to denote the machine and, by analogy with vehicle routing problems, we refer to the machine location as the depot.

The vehicle loads a certain number of jobs which have been processed and starts the round trip to deliver them at their respective locations. The set of jobs delivered during a single round trip is called a batch. The problem is then to determine the scheduling sequence, cluster the jobs into batches and determine the best route for each batch. Using the notation introduced by [START_REF] Lee | Machine scheduling with transportation considerations[END_REF], the general problem considered here with one machine, several customers, one vehicle and a limited capacity is denoted by 1 → D, k ≥ 1|v = 1, c|D max for the makespan objective and 1 → D, k ≥ 1|v = 1, c| D j for the total completion time (1 → D means "one machine to delivery", k is the number of customers, v is the number of vehicles, c indicates that a capacity is considered). An illustration for the problem with n = 7 jobs and n customers is given in Fig. 1. We first discuss the complexity of special cases of the problem. Then we propose extended formulations and a column generation framework for the general case.

- D1 D2 D3 D4 D5 D6 D7 0 J1 J2 J3 J4 J5 J6 J7 1

Particular cases

In this section, we consider two special cases of the problem for both objectives functions. We give complexity results for the single customer case and some remarks for the fixed-batches case.

One customer case

In [START_REF] Chang | Machine scheduling with job delivery coordination[END_REF], the authors prove that the problem 1 → D, k = 1|v = 1, c|D max is equivalent to the NP-hard Bin Packing problem when the processing times p j = 0 for all j. Note that this reasoning becomes invalid for the total delivery time objective. However, we prove that problem 1 → D, k = 1|v = 1, c| j D j is strongly NP-hard by reduction from 3-PARTITION problem. For our purpose, we introduce the 3-PARTITION problem.

3-PARTITION. Given 3h integers a 1 , . . . , a 3h , so that a i = hb, and such that b/4 < a i < b/2 for all i, is it possible to partition them into h disjoint sets each summing up to b ?

Theorem 1. Problem 1 → D, k = 1|v = 1, c = z| j D j is NP-hard in the strong sense.
Proof. Given a 3-PARTITION instance, we construct an instance for our problem as follows:

n = 3h jobs, c = b, t M 1 = t 1M = t and t > 0
For each job J j : p j = 0, s j = a j Sum of the delivery times y = 3th 2

From there, the problem consists in determining whether a solution exists such that j D j ≤ y.

→ If there is 3-PARTITION, then there exists a feasible schedule to our problem with j D j ≤ y. Let H 1 , H 2 ,. . . , H h be a solution of 3-PARTITION. Then, we construct a schedule to our problem by setting each batch b i to the triple H i . The vehicle starts the tour at time zero, delivers the first three jobs at time t and is back at the depot at 2t. Since the processing times are equal to zero, the vehicle restarts immediately and the second batch is delivered at time 3t. Following this reasoning (see Fig. 2), a batch b i is delivered at time (2i -1)t and the total delivery time j D j = 3

h i=1 (2i -1)t = y. - t 3t 0 .... R H h 5t (2h -1)t H3 R R H2 R H1 R Fig. 2. 3-PARTITION solution
← Suppose that a schedule S for our problem exists in which j D j ≤ y. According to the generated instance, the number of batches in S cannot be smaller than h, the number of jobs in each batch cannot exceed 3 and the vehicle is never idle at the depot in an optimal solution. We denote by h the number of batches in S. Firstly, we suppose that h = h and denote by S Remark 1. Problem 1 → D, k = 1|v = 1, c| j D j is polynomially solvable when all jobs have the same size [START_REF] Li | Machine scheduling with deliveries to multiple customer locations[END_REF]. The authors propose a polynomial time algorithm with a complexity in O(n 2 ) to solve the problem.

Fixed-batch case

In this case, we consider that the jobs are already clustered into batches and that, for each one, the delivery route is known. We consider below the makespan criterion and the sum of delivery times criterion.

1 → D, k = 1|v = 1, c, f ixed -batches|D max problem Proposition 1. Problem 1 → D, k ≥ 1|v = 1, c = z, f ixed -batches|D max is polynomially solvable.
If we consider a batch as a job, this problem becomes equivalent to the wellknown polynomial two-machine flow shop problem with makespan criterion [START_REF] Johnson | Optimal Two-and-Three-Stage Production Schedules with Set-up Times included[END_REF]. In the resulting problem, we consider the duration of the batch on the machine as the processing time of the corresponding job on the first machine and the duration of the route of the batch as the processing time on the second machine.

1 → D, k = 1|v = 1, c, f ixed -batches| j D j problem Proposition 2. Problem 1 → D, k ≥ 1|v = 1, c = z, f ixed -batches| j D j is NP-hard.
We consider the case in which each batch contains exactly one job and we denote by C j the time at which the vehicle is back at the depot after the delivery of job J j . The delivery time D j of a job J j is then D j = C j -t jM and n j=1 D j = n j=1 C j -n j=1 t jM , with n j t jM a constant. This problem is equivalent to solving the NP-hard two-machine flow shop problem with the sum of completion times criterion [START_REF] Garey | The complexity of flowshop and jobshop scheduling[END_REF], in which the processing times of a job J j on the first machine is equal to p j , equal to t M j + t jM on the second machine and a completion time on the second machine equal to C j .

General case

For the general case, we first establish the following fundamental dominance property. As there are no release dates for the jobs, from any solution, the machine sequence can obviously be reordered according to the routing sequence and the jobs can be scheduled at the earliest without increasing the objective function for both the D max and j D j criteria. The property then follows: Property 1. There exists an optimal solution satisfying the following conditions:

-Jobs are processed on the machine without idle time, -Production sequence and routing sequence are the same. This implies that when the round trip of a batch is given, the sequence on the machine can be deduced. For both objective functions, one can see that the optimal solution of the problem can be obtained by combining batches and the problems are able to be modeled as a set covering problem. Hence, extended formulations and column generation approaches can be considered for both problems. Note that if there was no machine scheduling phase, the problem would resort to the multi-trip travelling salesman problem. Below, we detail these approaches for each criterion. Note that column generation and branch-and-price are techniques of choice for the related multi-trip vehicle routing problem [START_REF] Azi | An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles[END_REF], [START_REF] Lysgaard | A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem[END_REF]. However, we have in our case a single vehicle and a preliminary constrained batching phase due to the machine sequencing sub-problem. It is thus relevant to wonder whether a column generation approach can still be successfully applied or not.

4.1 1 → D, k ≥ 1|v = 1, c|D max problem
We introduce in this section a set covering formulation for the master problem. A column represents a batch and its position on the delivery sequence. The set of feasible batches is denoted as β. For each batch b ∈ β, its duration on the machine and its round trip duration are known. We denote by P b,1 = j∈b p j the duration of the batch b on the machine and, P b,2 the duration of the round trip that delivers the batch b. Since the jobs contained in a batch are known, a i,b takes the value 1 if the job J i is in the batch b and 0 otherwise. A unique set of variables x b,k is used to minimize the D max objective. Variables x b,k ∈ {0, 1} indicates if the batch b at the position k is selected.

min D max

(1)

D max ≥ l k=1 b∈β P b,1 x b,k + n k=l b∈β P b,2 x b,k , ∀l ∈ {1, ..., n} (2)
b∈β

x b,k ≤ 1, ∀k ∈ {1, ..., n} (3)
b∈β

(a i,b n k=1 x b,k ) = 1, ∀i ∈ {1, ..., n} (4)
b∈β

x b,k ≥ b∈β x b,k+1 , ∀k ∈ {1, ..., n -1} (5) b∈β x b,k = 1, ∀k ∈ {1, ..., δ} (6)
x b,k ∈ {0, 1} ∀k ∈ {1, ..., n}, ∀b ∈ β

The first set of constraints ( 2) is equivalent to the fixed-batches case presented above. It ensures that the processing of a batch on the machine starts after the completion of the previous one and that the vehicle starts the delivery of a batch after its completion on the machine, and the end of the previous tour. Constraints [START_REF] Chang | Machine scheduling with job delivery coordination[END_REF] state that a position can contain at most one batch and constraints (4) ensure that each job is contained in exactly one selected batch. Constraints ( 5) are symmetry breaking constraints that enforce that all selected columns (batches) appear consecutively at the first positions. Constraints ( 6) sets a minimum number of batches using a lower bound δ of the number of round trips to deliver all the jobs. To obtain δ, we use the First Fit Decreasing rule which is a 3/2 approximation for the Bin Packing problem. Let τ the number of bins obtained by the FFD algorithm. A lower bound of the minimum number of batches δ is then equal to 2/3τ . Following a standard column generation scheme, the master problem is restricted to a subset of variables (columns) β ⊆ β and a pricing problem is needed to find new non basic variables that can improve the solution for the LP relaxation of model [START_REF] Armstrong | A zero-inventory production and distribution problem with a fixed customer sequence[END_REF][START_REF] Azi | An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles[END_REF][START_REF] Chang | Machine scheduling with job delivery coordination[END_REF][START_REF] Chen | Integrated Production and Outbound Distribution Scheduling: Review and Extensions[END_REF][START_REF] Chen | Logistics scheduling with batching and transportation[END_REF][START_REF] Gao | Integrated batch production and distribution scheduling with limited vehicle capacity[END_REF][START_REF] Garey | The complexity of flowshop and jobshop scheduling[END_REF].

The pricing problem This sub-problem searches for an element of β \ β such that the reduced cost of the new column is negative. We denote by cb,k the reduced cost of x b,k and, one has:

cb,k ≤ 0 ⇔ n i=1 p i n l=k α l -γ i k l=1 α l li a i,b + P b,2 < β k -σ k-1 + σ k + ξ k k l=1 α l r k
where α l , β k , γ i , σ k and ξ k denote the dual values associated to the constraints (2), ( 3),( 4), ( 5), ( 6) respectively. Note that the dual values ξ k exist only for k ≤ δ, σ k-1 for k ≥ 2 and σ k for k ≤ n -1.

We define an auxiliary directed graph G = (V, A) in which V = N ∪ {v s , v d } where nodes N = {v 1 , . . . , v n } represent the locations 1, . . . , n and nodes {v s , v d } the duplicated depot. The set of arcs is

A = {(v i , v j )|v i ∈ N ∪ {v s }, v j ∈ N ∪ {v d }, v i = v j }.
Finally, the sub-problem consists in solving an elementary shortest path problem with resource constraints (ESPPRC) on graph G, in which the distance value d ij of an arc (v i , v j ) is equal to l i + t ij for v i ∈ V -{v s }, d sj = t M j for each arc (v s , v j ), and d sd = r k for arc (v s , v d ). The constraints concern the capacity of the vehicle. A column x bk corresponding to an elementary shortest path in G is introduced in the restricted master problem only if the length of such path is smaller than r k . From the resulting path and given that the jobs sequence on the machine and the delivery sequence are the same, the round trip length and the batch processing on the machine can be obtained. An exact method is used to solve the elementary shortest path problem with resource constraints. The interested reader will find more details about the used algorithm in [START_REF] Lozano | An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints[END_REF].

Starting from the first position, the sub-problem searches for a new column to add by scanning all positions and stops when a column with negative reduced cost is found. The new column is then added. We propose below a heuristic to initiate the column generation process, taking account of this particularity.

Initial solution heuristic

In order to accelerate the sub-problem solution phase by using a minimal number of positions, we propose the following initial solution heuristic:

(1) The first step is to assign jobs into batches according to their sizes. The First Fit Decreasing rule is used for this purpose. (2) Given a constitution of the batches, the route is determined using the nearest neighbor search rule. (3) As soon as the duration of the batch on the machine and the duration of the routes are known, the Johnson's rule (known to solve the two-machine flow-shop problem to optimality) is used to optimally order the batches.

4.2 1 → D, k ≥ 1|v = 1, c| j D j problem
In this part, a formulation for the general problem with a cumulative objective function j D j is suggested. In order to obtain the delivery time of each job, the new columns of the master problem must take the departure time of a batch into account. Hence, we define binary variables y bkt , which take the value 1 if the batch b is delivered at position k and starts to deliver it at time t if selected, 0 otherwise. For each position k, the departure time is given by variable S k ≥ 0.

As the considered objective needs the exact delivery time of each job, we denote by R ib the time between the departure time of the vehicle and the arrival time to location i. This value is known once a batch b is given. Let T be an upper bound on the latest possible departure time of the vehicle for the last batch. As long as the triangle inequality holds, this is given by:

T = n i=1 (p i + 2t 0,i )
The other notations remain the same as those used for the formulation with the D max objective function. Let β denote the set of feasible batches.

Minimize b∈β n k=1 T t=1 i∈b a i,b (t + R i,b )y b,k,t (8)
The delivery time of a job J i is given by the addition of the departure time of the batch which contains it and the transportation time between the depot and the location i (9). The other constraints are similar to those used for the previous formulation.

We denote by c

bkt the reduced cost of variable y bkt . Let β ⊆ β . The subproblem searches for an element of β \ β such that the reduced cost of a new column is negative.

c bkt ≤ 0 ⇔ n i=1 (t + R i,b ) di a i,b + n i=1 (p i,1 ( n k =1 k l=k α l,k ) -γ i ) l i a i,b + +P b,2 ( n k =k+1 k l=1 α l,k ) q ≤ β k + tδ k -σ k-1 + σ k + ξ k r kt
where α lk , β k , γ i , δ k , σ k and ξ k the dual values associated to the constraints ( 9), ( 10),( 11),( 12),( 13) and ( 14) respectively. The dual values ξ k exists only for k ≤ δ, σ k-1 for k ≥ 2 and σ k for k ≤ n -1.

An auxiliary graph G is defined in the same way as the one defined above so that the sub-problem consists in finding an elementary shortest path with resource constraints (ESPPRC) on graph G in which the distance d ij of an arc (v i , v j ) is equal to l i + q • t ij . However, a new label is introduced in order to store the elapsed time R ib between the departure time of the vehicle and the arrival time to location i. To optimally solve the (ESPPRC), Lozano et al algorithm is also used.

Computational Results

The results are performed on a set of data generated as follows. For each job, processing times and the size follow a sets of discrete uniform distribution U(1, 100) and U(1, 10) respectively. For a location j, integer coordinates (X j , Y j ) are randomly generated in the interval [START_REF] Armstrong | A zero-inventory production and distribution problem with a fixed customer sequence[END_REF]40] and the distances between the locations are obtained by computing the classical euclidean distance.

t i,j = t j,i = E (X i -X j ) 2 + (Y i -Y j ) 2
Note that the processing times, locations and sizes of the jobs are generated independently of each other. Capacity c of the vehicle is fixed to 20 and 5 instances are generated for each number of jobs n ∈ {20, 30, 40, 50, 60, 70, 80, 90, 100}. Hence, the experiments are performed on 45 instances. The column generation process could be carried out efficiently only for the D max criterion. Indeed, for the D j model, the need to explicitly represent time makes the convergence much slower as the number of variables becomes huge in the master problem.

The experiments have been implemented for the 45 instances on a Xeon 3.20GHz computer with 8GB using ILOG CPLEX 12.6 to solve the LPs. We evaluate and compare the solutions obtained by the column generation which represents a lower bound (LB) for the problem with the integer solution obtained by branch and bound on the generated columns, which represents an upper bound (UB). In order to obtain 1. Computational results for 1 → D, k ≥ 1|v = 1, c|Dmax problem an upper bound in a reasonable time, the sub-problem add a single column at each time. Therefore, to obtain a good upper bound, all columns with negative reduced costs are integrated to the master problem which has the advantage of providing good upper bounds and the disadvantage of a larger execution times.

In table 1, we were interested on the aggregate results for each value of n. The statistics take into account the average CPU times for the column generation (column LB(sec)). The number of columns generated during the process is given in column #col. The gap between the initial solution and the relaxed solution is given in column (%GAPinit). Finally, the gap between UB solution and the relaxed solution is given by column (%GAPUB). The results show a gap lower than 1% for instances with n ≥ 40, which proves the very good quality of the bounds. The computational times remain lower than 1200s for instances with up to 100 jobs.

Conclusions

In this paper we presented an integrated production scheduling and delivery routing problem that can be seen as a variant of the multi-trip traveling salesman problem with a constrained batching phase due to machine sequencing constraints. We presented complexity results for particular cases and an efficient column generation scheme for the makespan criterion. In the near future, we shall focus on the implementation of a branch-and-price algorithm to close the remaining gap. We will also focus on finding a better decomposition scheme for the sum of deliveries criterion.

Fig. 1 .

 1 Fig. 1. An illustration for problems 1 → D, k ≥ 1|v = 1, c|Dmax or Dj

  1 the corresponding schedule. This implies that each batch b 1 , b 2 , . . . , b h of S 1 contains exactly three jobs and for each batch j∈bi s j = b. Thus, b 1 , . . . , b h define a solution of the 3-PARTITION problem. Suppose now that there exists a schedule S 2 for which j D j ≤ y and h > h. Let n 1 the number of jobs in b 1 , . . . , b h and n 2 the number of jobs in b h+1 , . . . , b h . We denote by σ S1 j and σ S2 j the jobs scheduled at position j in the schedule S 1 and S 2 respectively. Due to the fact that each batch in S 1 contains three jobs, one can see that n1 j=1 D σ S 2 j ≥ n1 j=1 D σ S 1 j . In the schedule S 2 , the remaining n 2 jobs are delivered after the time (2h -1)t which represents the delivery time of J σ S 2 n 1 and the last job J σ S 1 n in S 1 . So, n j=n1+1 D σ S 2 j > n j=n1+1 D σ S 1 j which implies j D j > y on the solution S 2 .

P

  b,2 y b,k,t , ∀k ∈ {1, ..., n}, ∀l ∈ {1, ..., k } (9) b∈β T t=1 y b,k,t ≤ 1, ∀k ∈ {1, ..., n} (10) k,t ) ≥ 1, ∀i ∈ {1, ..., n} (11) b∈β T t=1 ty b,k,t ≥ S k , ∀k ∈ {1, ..., n} (12) k+1,t , ∀k ∈ {1, ..., n -1} (13) b∈β T t=1 y b,k,t = 1, ∀k ∈ {1, ..., δ} (14) y b,k,t ∈ {0, 1} ∀b ∈ β , ∀k ∈ {1, ..., n}, ∀t ∈ {1, . . . , T }

ACKNOWLEDGEMENT

This work was supported by the financial support of the ANR ATHENA project, grant ANR-13-BS02-0006 of the French Agence Nationale de la Recherche.


Azeddine Cheref

Alessandro Agnetis

Christian Artigues

Jean-Charles Billaut

Fixed-sequence single machine scheduling and outbound delivery problems

Keywords: Scheduling, Batching and delivery, Computational complexity, Dynamic programming

In this paper, we study an integrated production an outbound delivery scheduling problem with a predefined sequence. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to multiple customers. A single vehicle with limited capacity is used for the delivery. Each job has a processing time and a specific customer location. Starting from the manufacturer location, the vehicle delivers a set of jobs which constitute a batch by taking into account the transportation times. Since the production sequence and delivery sequence are fixed and identical, the problem consists in deciding the composition of batches. We prove that for any regular sum-type objective function of the delivery times, the problem in NP-hard in the ordinary sense and can be solved in pseudopolynomial time. A dynamic programming algorithm is proposed.

INTRODUCTION

This paper deals with a model for coordinating production and delivery schedules. In many production systems, finished products are delivered from the factory to multiple customer locations, warehouses, or distribution centers by delivery vehicles. An increasing amount of research has been devoted, during the last twenty years, to devise integrated models for production and distribution. These models have been largely analyzed and reviewed by [START_REF] Chen | Integrated production and outbound distribution scheduling: Review and extensions[END_REF], who proposed a detailed classification scheme. The models reflect the variety of issues, including systems structure, vehicle/transportation system characteristics, delivery modes, various types of time constraints. In the large majority of the models in the literature, the coordination of production and distribution is achieved through the creation of batches, i.e., several parts are shipped together and delivered to their respective destinations during a single trip. When forming batches, one must therefore take into account both production information (such as processing time, release dates etc) and delivery information (such as customer location, time windows etc). Most of the models presented in the literature explicitly take into account transportation times to reach the customers' location, but there are no proper routing decisions, since the number of distinct customers is typically very small. Hence, the focus of the analysis is often on scheduling and batching.

Many models consider delivery as a separate step after production, but do not model it in details, e.g. assuming that a sufficiently large number of vehicles is available to deliver the products at any time (Chen and Lee, 2008) [START_REF] Agnetis | Coordination of production and interstage batch delivery with outsourced distribution[END_REF] [START_REF] Fan | Integrated scheduling of production and delivery on a single machine with availability constraint[END_REF], or assuming that there is a single customer. In [START_REF] Chang | Methodological Foundations of Multi-Criteria Decision[END_REF] the jobs have a certain size and the capacity of a vehicle is a physical space available, and jobs have to be delivered to a unique customer. NPhardness results are given as well as heuristic algorithms with performance guarantee. In [START_REF] Li | Machine scheduling with pickup and delivery[END_REF] and [START_REF] Wang | Production scheduling with supply and delivery considerations to minimize the makespan[END_REF], delivery concerns the materials as well as finished jobs which must be transported to a single warehouse. The objective is to minimize the delivery time of the job delivered last to this customer. Li and Ou propose a polynomial time algorithm when the production sequence is fixed. Delivery can also be modeled as a delay after the production completion time. Fan, Lu and Liu [START_REF] Fan | Integrated scheduling of production and delivery on a single machine with availability constraint[END_REF] consider the join problem of scheduling and routing with availability constraints of the machine. The delivery is performed by an unlimited number of uncapacitated vehicles and the objective is to minimize the total delivery time and total delivery cost. Depending on the problem they consider, the authors propose polynomial time algorithms, an algorithm with guaranteed performance and a polynomial time approximation scheme.

In the paper by (Li et al., 2005), a single vehicle is used for delivery, and hence the vehicle schedule has to be synchronized with production and batching decisions. In particular, one must also take account of the time that the vehicle will take to deliver a certain batch of products, and that it will take to be back at the manufacturing facility. (Li et al., 2005) analyze the joint problem of production sequencing and batch formation, in order to minimize total delivery time, given that delivery is performed by a single vehicle. Total delivery time is a meaningful indicator of the overall efficiency of the delivery process. They show that in general the problem is NP-hard, and then give polynomial time algorithms for the problem with a fixed number of distinct destinations. In [START_REF] Tsirimpas | Single vehicle routing with a predefined customer sequence and multiple depot returns[END_REF], the authors consider that all the jobs are ready for the delivery at the beginning of the time horizon (no scheduling problem here). The delivery is performed by a single capacitated vehicle and the sequence of delivery is predefined. The objective is to minimize the total travel time and the authors propose polynomial time algorithms. In (Chen and Lee, 2008), the authors consider the problem with a single machine where finished jobs must be transported by an unlimited number of vehicles. There is no vehicle routing problem, since the vehicle delivers in one trip only jobs delivered at the same destination.

Using the terminology of [START_REF] Chen | Integrated production and outbound distribution scheduling: Review and extensions[END_REF], the models presented in this paper concern batch delivery with routing, i.e., orders going to different customers can be delivered together in the same shipment (batch).

A distinctive feature of the problems we address here is that the jobs must be delivered in the same order in which they are produced. Examples of situations in which the customer sequence is fixed are reported by [START_REF] Armstrong | A zeroinventory production and distribution problem with a fixed customer sequence[END_REF], [START_REF] Viergutz | Integrated production and distribution scheduling with lifespan constraints[END_REF] and include a fixed sequence of customers and a single round trip for the delivery (hence, the production sequence and the routing sequence are the same), as well as the objective is to maximize the total demand without violating the product lifespan. This problem is proved NP-hard by [START_REF] Armstrong | A zeroinventory production and distribution problem with a fixed customer sequence[END_REF]. In [START_REF] Lenté | Problème de livraison a séquence fixée[END_REF], the authors consider that the production sequence is fixed as well as the delivery sequence. The authors search for a batching of jobs minimizing the makespan, the maximum lateness and the number of tardy jobs. The problems are modeled by a graph and polynomial time algorithms are proposed for these objective functions.

In this paper, we will mainly focus on the problem of deciding how to form batches with a given production sequence (problem P1). We completely characterize the complexity of Problem P1, showing that when the objective function is to minimize the total delivery time it is NP-hard in the ordinary sense, and that it can be solved in pseudopolynomial time for any sum-type function of the delivery times.

The paper is organized as follows. In Section 2 we present the problem formally and show that the problem is NP-hard when Z is the total delivery time, and that it can be solved in pseudopolynomial time when Z is any sum-type objective function. Finally, some conclusions and future research directions are presented in Section 4.

PROBLEM DEFINITION AND COMPLEXITY 2.1 Problem definition and notation

The problem considered in this paper can be described as follows. A set of n jobs is given and their production sequence is known. Each job J j , j = 1, . . . , n, requires a certain processing time p j on a single machine, and must be delivered to a certain location site. For the sake of simplicity, when it does not create confusion, we use j to refer to the destination of job J j . We denote by t i, j the transportation time from destination i to destination j. For analogy with vehicle routing problems, we refer to the manufacturer's location as the depot. We use M to denote the depot (manufacturer), hence t M, j = t j,M is the transportation time between the depot and destination j. Unless otherwise specified, we assume that transportation times are symmetric and satisfy the triangle inequality. Deliveries are carried out by a single vehicle. The vehicle loads a certain number of jobs which have been processed and departs towards the corresponding destinations. Thereafter, it returns to the depot, hence completing a round trip. The set of jobs delivered during a single round trip constitutes a batch. The capacity c of the vehicle is the maximum number of jobs it can load and hence deliver in a round trip. The jobs must be delivered in the order in which they are produced, hence the production sequence also specifies the sequence in which the customers have to be reached.

The problem consists in deciding a partition of all jobs into batches, i.e., a batching scheme. Each batch will be routed according to the manufacturing sequence. In general, the performance of the system depends on all the concurrent decisions: production scheduling, batching and vehicle routing. This requires therefore an integrated model, allowing one to coordinate all these aspects. A solution to our problem with fixed sequence, is the specification of a batching scheme. Given a solution, we denote by C j the completion time of job J j on the single machine, which is also the time at which the job is released for delivery, i.e., the batch including job J j cannot start before C j . We denote by D j the delivery time of J j , i.e., the time at which the job J j is delivered at its destination. The performance measures we consider in this paper depend on such delivery times. In particular, denoting with Z the performance measure, in this paper we consider:

• the total delivery time, i.e., Z = ∑ n j=1 D j • a general sum-type performance index, i.e., Z = ∑ n j=1 f j (D j ), where f j (D j ) is a general, nondecreasing function of D j , j = 1, . . . , n. Note that the latter case includes total (weighted) delivery time, total (weighted) tardiness, etc.

We consider the following problem:

Problem P1(Z). Given n jobs of length p j , j = 1, . . . , n, transportation times t i, j for all i, j, and a sequence σ, find a batching scheme B such that Z is minimized.

Complexity

Since the production sequence is given, and since jobs are delivered to the respective customers in the same given order, we assume that the job sequence is σ = (J 1 , J 2 , ..., J n ). Only travel times t j, j+1 are relevant, as well as times t j,M = t M, j , representing the travel time between customer j and the manufacturer or vice-versa.

Let us first consider the problem in which the objective function is the total delivery time, i.e., problem P1(∑ n j=1 D j ). For our purposes, we introduce the following problem.

EVEN-ODD PARTITION (EOP). A set of n pairs of positive integers

(a 1 , b 1 ), (a 2 , b 2 ), . . . , (a n , b n ) is given, in which, for each i, a i > b i . Letting K = ∑ n i=1 (a i + b i ), is there a partition (S, S) of the index set I = {1, 2, . . . , n} such that ∑ i∈S a i + ∑ i∈ S b i = K/2? (1)
EOP is NP-hard in the ordinary sense [START_REF] Garey | One-processor scheduling with symmetric earliness and tardiness penalties[END_REF]. In the following, we will actually use the following slightly modified version of the problem.

MODIFIED EVEN-ODD PARTITION (MEOP). A set of n pairs of positive integers

(a 1 , b 1 ), (a 2 , b 2 ), . . . , (a n , b n ) is given, in which, for each i, a i > b i . Let- ting Q = ∑ n i=1 (a i -b i ), is there a partition (S, S) of the index set I = {1, 2, . . . , n} such that ∑ i∈S (a i -b i ) = Q/2?
(2)

Note that the two problems are indeed equivalent. In fact, suppose that EOP has a partition (S, S).

The corresponding instance of MEOP also admits the same partition. In fact, subtracting ∑ n i=1 b i = ∑ i∈S b i + ∑ i∈ S b i from both sides of (1), one obtains

∑ i∈S (a i -b i ) = K/2 - n ∑ i=1 b i (3)
Now, from the definitions of K and Q it turns out that

Q = K -2 n ∑ i=1 b i
and hence (3) is indeed (2). We next show the following result.

Theorem 2.1. P1(∑ n j=1 D j ) is NP-hard. Proof. The problem is obviously in NP. Given an instance of MEOP, we build an instance of P1 as follows. There are 3n + 3 jobs. The processing times of the jobs are defined as follows:

• p 1 = p 2 = p 3 = 0. • for each i = 0, 1, . . . , n -1, one has -p 3i+1 = p 3i+2 = 1, -p 3i+3 = 4x i + b i -2. • p 3n+1 = 4x n + b n + Q/2. • p 3n+2 = p 3n+3 = 0,
where the x i are defined by

x i = (3a i -2b i +3(n-i)(a i -b i ))/2 ∀ i = 1 . . . n (4)
and x n+1 = 0.

In the following, we refer to the set of jobs (J 3i+1 , J 3i+2 , J 3i+3 ), i = 0, . . . , n, as the triple T i+1 .

For what concerns the travel times, we let:

• for each i = 0, 1, . . . , n -1, one has -t M,3i+1 = t 3i+1,M = t M,3i+2 = t 3i+2,M = t M,3i+3 = t 3i+3,M = x i+1 , -t 3i+1,3i+2 = a i+1 , -t 3i+2,3i+3 = b i+1 , -t 3i+3,3i+4 = x i+1 + x i+2 . • t M,3n+1 = t 3n+1,M = t M,3n+2 = t 3n+2,M = t M,3n+3 = 0. • t 3n+1,3n+2 = t 3n+2,3n+3 = 0.
Finally, vehicle capacity is c = 2. The problem consists in determining whether a solution exists such that the total delivery time does not exceed

f * = n ∑ i=1 (3C 3i +7x i +b i )+C 3n+1 +C 3n+2 +C 3n+3 -Q/2.
(5) For shortness, we call feasible a schedule satisfying (5). The proof has the following scheme.

1. We first establish that if a feasible schedule exists, then there is one having a certain structure, called triple-oriented, 2. We analyze some properties of this structure, 3. We show that a triple-oriented schedule of value f * exists if and only if EOP is a yes-instance.

Lemma 2.2. If a feasible schedule exists, then there exists one satisfying the following property: for all i = 1, . . . , n+1, jobs J 3i and J 3i+1 are NOT in the same batch.

Proof. Suppose that a feasible schedule exists in which, for a certain i (1 ≤ i ≤ n), jobs J 3i and J 3i+1 are in the same batch. Since c = 2, the batch contains no other job. As a consequence, after delivering J 3i+1 , the vehicle must go back to M in order to load the next jobs and start a new trip. If we denote by τ the start time of the round trip of jobs J 3i and J 3i+1 , job J 3i is delivered at time D 3i = τ + t M,3i and job J 3i+1 is delivered at time D 3i+1 = τ + t M,3i + t 3i,3i+1 . Therefore we have

D 3i = τ + x i and D 3i+1 = τ + x i + (x i + x i+1 ).
The vehicle is back at M at time τ + 2x i + 2x i+1 . Now, if we replace this batch with two batches of one job each, the delivery times of both jobs as well as the time at which the vehicle is back at M are unchanged. Therefore, there is an equivalent solution where J 3i and J 3i+1 are not in the same batch. We call triple-oriented a schedule satisfying Lemma 2.2. The reason of this name is that the schedule is decomposed according to triples. More precisely, since c = 2, for each triple T i+1 = (J 3i+1 , J 3i+2 , J 3i+3 ), i = 0, . . . , n -1, there are exactly two batches, and only two possibilities, namely:

• either the first batch is {J 3i+1 , J 3i+2 } and the second is {J 3i+3 }, • or the first batch is {J 3i+1 } and the second is {J 3i+2 , J 3i+3 }.

We call these two possibilities option A and option B respectively (see Fig. 1). Namely, let us view option B as the Base option, and A as a variant to it.

Round trip length. Letting M A i and M B i denote the round trip length of the jobs of T i in the two cases. One has:

M A i = 4x i + a i (6) M B i = 4x i + b i (7)
Since a i > b i , option A implies a longer round trip length than the Base option. The difference between the two (i.e., the additional time with option A with respect to B) is precisely a ib i .

Lemma 2.3. In any triple-oriented schedule, the vehicle is never idle, except possibly before loading J 3n+1 .

Proof. Let consider the first triple T 1 . The vehicle starts at time 0 (to deliver batch {J 1 } or {J 1 , J 2 }), and is back at time 4x 1 + b 1 or at time 4x 1 + a 1 . The completion time of T 2 is precisely equal to

C 6 = ∑ 6 j=1 p j = 1 + 1 + 4x 1 + b 1 -2 = 4x 1 + b 1 .
Therefore, the vehicle can immediately start the delivery of the jobs of T 2 . For the same reasons, the delivery of the jobs of T i cannot be smaller than, the duration of the jobs of T i+1 , and the vehicle will be able to start immediately the delivery of the jobs of T i+1 . This reasoning stops for the last triple T n+1 because the duration of J 3n+1 is particular.

In view of Lemma 2.3, one can compute the total delivery time in the Base scenario, i.e., when option B is always chosen. From ( 7), one has that the vehicle always returns to M exactly at time C 3i . Therefore, the last time the vehicle arrives at M (before delivering the jobs of T n+1 ) is C 3n + 4x n + b n . Because of the definition of p 3n+1 , and because J 3n+1 starts at time C 3n , this time is equal to C 3n+3 -Q/2. In this case, the vehicle will stay idle from C 3n+1 -Q/2 to C 3n+1 , when job J 3n+1 can be finally loaded (see Fig. 2) and delivered (the two reminder jobs have a duration of 0 and travel times equal to 0). Hence, we have:

f BASE = n ∑ i=1 (3C 3i + 7x i + b i ) +C 3n+1 +C 3n+2 +C 3n+3 (8)
Contribution to total delivery time. Before computing the contribution of a certain triple to the total delivery time, let us consider schedules in which the transportation of the last three jobs J 3n+1 , J 3n+2 and J 3n+3 start exactly at their release time, i.e., at time C 3n+1 = C 3n+2 = C 3n+3 (options A and B are equivalent). Let us call regular a schedule in which such a condition holds.

Expression (8) refers to the scenario in which for all triples, the option B is chosen. We want now to compute the objective function of an arbitrary solution. Let us first consider the contribution of triple T i to the objective function in the Base schedule, i.e., assuming that the delivery of T i started at time C 3i , and let us denote such piece of contribution as T DT A i and T DT B i in the two cases. One has: ...

T DT A i = (C 3i + x i ) + (C 3i + x i + a i ) + (C 3i + 3x i + a i ) = 3C 3i + 5x i + 2a i (9) T DT B i = (C 3i + x i ) + (C 3i + 3x i ) + (C 3i + 3x i + b i ) = 3C 3i + 7x i + b i (10) 3(i-1)+1 3(i-1)+2 3(i-1)+3 b i 3(i-1)+1 3(i-1)+2 3(i-1)+3 a i 3i+1 3i+2 3i+3 3i+1 3i+2 3i+3 option A option B a i -b i
3(i-1)+1 3(i-1)+2 3(i-1)+3 b i 3i+1 3i+2 3i+3 x i x i x i x i T i+1 T i

Note that

T DT B i -T DT A i = 2x i + b i -2a i = (3a i -2b i + 3(n -i)(a i -b i )) + b i -2a i = a i -b i + 3(n -i)(a i -b i ) (11)
which is positive, remembering that a i > b i . This means that choosing option A over B brings a benefit in terms of total delivery time. However, such favorable situation for option A is mitigated by the fact that, with option A, one has a longer round trip time than with option B, by the amount (a ib i ) (Fig. 3). In a regular schedule, such increased round trip time will be "paid" by all subsequent jobs, except the last jobs J 3n+1 , J 3n+2 and J 3n+3 . Hence, in a regular schedule the total effect (in favor of option B) on the subsequent jobs of choosing option A for T i is given by

3(n -i)(a i -b i ) (12)
In conclusion, the net benefit of choosing option A over B for T i in terms of objective function value is obtained subtracting ( 12) from ( 11), and in view of the definition of x i (4), one has therefore that

NetBene f it i = (2x i + b i -2a i ) -3(n -i)(a i -b i ) = a i -b i (13)
In conclusion, it turns out that, when A is chosen over the Base option, one has a larger round trip time, by (a ib i ), but also a smaller contribution to total delivery time (also by the amount (a ib i ))(see Fig.

a i -b i 3(i-1)+1 3(i-1)+2 3(i-1)+3 a i x i x i x i x i T i+1 T i 3i+1 3i+2 3i+3
Figure 3: T i is the first triple choosing option A.

4). So, given any regular triple-oriented schedule in which the last three jobs depart at their completion time, let T A be the set of triples for which the option A is chosen. Then, from the above considerations, the value f of the objective function is given by

f = f BASE -∑ i∈T A (a i -b i ) (14)
On the other hand, the time at which the vehicle returns to M before loading the last three jobs (J 3n+1 , J 3n+2 and J 3n+3 ) is given by

C 3n + 4x n + b n + ∑ i∈T A (a i -b i ) (15)
Now, in a regular schedule job J 3n+1 (and also J 3n+2 and J 3n+3 ) starts at time C 3n+1 = C 3n + 4x n + b n + Q/2. Hence, from (15), in a regular schedule, it must hold:

∑ i∈T A (a i -b i ) ≤ Q/2
On the other hand, comparing (5), ( 8) it turns out that

f * = f BASE -Q/2
and hence, from ( 14), a regular schedule is feasible precisely if a subset T A of indices exists such that ∑ i∈T (a ib i ) = Q/2, i.e., if and only if a feasible partition exists in the instance of EOP. To conclude the proof, it is left to show that f * can be attained only by a regular schedule. In fact, if a schedule is not regular, .... ....

T i+1 3(i-1)+1 3(i-1)+2 3i b i .... .... T i+1 ∑ i j=1 a j -b j 3(i-1)+1 3(i-1)+2 3i a i T 2 1 2 3 a 1 T 2 1 2 3 b 1 3n+1, 3n+2, 3n+3 3(n-1)+1 3(n-1)+2 3n an Q/2 3n+1, 3n+2, 3n+3 3(n-1)+1 3(n-1)+2 3n bn Q/2 a 1 -b 1
(∑ i∈T A (a i -b i ) -Q/2) with respect to C 3n+1 .
As a consequence, the expression of f in ( 14) must be modified to take account of such delay of the last three jobs, i.e. it comes

f = f BASE -∑ i∈T A (a i -b i ) + 3( ∑ i∈T A (a i -b i ) -Q/2) = f BASE + 2 ∑ i∈T A (a i -b i ) -3Q/2 (16)
Since, in a nonregular schedule,

∑ i∈T A (a i -b i ) > Q/2,
from ( 16) one has

f > f BASE + Q -3Q/2 = f BASE -Q/2
and hence it cannot be feasible.

3 PSEUDOPOLYNOMIAL TIME ALGORITHM FOR P1(∑ j f j (D j ))

Theorem 2.1 implies that no optimal polynomial time algorithm can be found for P1(∑ n j=1 D j ), and hence for more general objective functions, unless P=NP. In what follows, we show that P1(∑ j f j (D j )) can be solved in pseudopolynomial time, hence settling the complexity status of P1.

In what follows we denote by {i, j} the batch consisting of jobs J i , . . . , J j . As usual, C j is the completion time of job J j (known because σ is known), and hence the release time for delivery. We denote by M(i, j) the duration of the round trip of batch {i, j}, and, if the batch starts at time t, we call K(i, j,t) its contribution to the objective function. Also, we assume that at the beginning, the vehicle is at the manufacturing location.

We denote by F(i, j,t) the value of the optimal solution of the problem restricted to the first j jobs, in which the first job of the last batch is J i , and such that the batch starts at time t. Then, F(i, j,t) can be computed by means of a simple recursive formula. In the optimal solution of the subproblem, if the second last batch is {p, i -1}, and if it starts at time s, then we have:

F(i, j,t) = F(p, i -1, s) + K(i, j,t)
Note that, if the vehicle starts at time s, it must be back before or at time t, i.e., the following constraint must hold:

C i-1 ≤ s ≤ t -M(p, i -1)
In conclusion, the problem is solved by means of:

F(i, j,t) = min max(i-c,1)≤p≤i-1 C i-1 ≤s≤t-M(p,i-1) {F(p, i-1, s)}+K(i, j,t) (17
) Let T be an upper bound on the latest possible departure time for the last batch. As long as the triangle inequality holds, this is given, for instance, by:

T = max max 1≤i≤n-1 {C i + 2 n-1 ∑ h=i t hM },C n
The optimal solution is given by:

z * = min n-c+1≤i≤n,C n ≤t≤T F(i, n,t) (18)
A few boundary conditions must be imposed:

F(i, j,t) = +∞ for all j < i (19) F(1, j,t) = K(1, j,t) for all j,t (20)
Condition ( 19) is obvious. Condition (20) allows to initialize the algorithm.

Let us turn to complexity. First, consider the computation of values M(i, j) and K(i, j,t). Both can be simply computed adding the contribution of the next job in the batch either to the round trip time (for M(i, j)) or to the objective function (for K(i, j,t)). More precisely, the delivery time d h of job J h with respect to the departure time of the batch is simply given by:

d h =    d h-1 + t h-1,h , if i < h ≤ j t M,h ,
if h = i (in this case the vehicle starts from M)

Hence, M(i, j) is simply given by d j + t j,M . Note that M(i, j + 1) = M(i, j) -t j,M +t j, j+1 +t j+1,M . This means that all M(i, j) can be computed in O(nc) assuming j ≤ i + c -1. Similarly, if batch {i, j} starts indeed at time t, the contribution of job J h to the objective function is given by:

f h (t + d h ), ∀i ≤ h ≤ j
Clearly, K(i, j,t) is given by ∑ j h=i f h (t + d h ). Again, assuming that f j (•) can be computed in constant time, note that d j+1 = d j + t j, j+1 and K(i, j + 1,t) = K(i, j,t) + f j+1 (d j+1 ). So, all values K(i, j,t) can be computed in O(ncT ).

Once all values M(i, j) and K(i, j,t) are known, one can compute formula (17) for all feasible triples (i, j,t). Each such computation requires comparing nT values. Finally, O(cT ) values are compared to find the optimal solution. Since the feasible triples are O(ncT ), the computation of all values F(i, j,t) clearly dominates the other phases, and the following result is proved.

Theorem 3.1. Problem P1(∑ j f j (D j )) can be solved in O(nc 2 T 2 ).

CONCLUSION AND FUTURE DIRECTIONS

The problem treated in this paper takes place in a Supply Chain environment, where a manufacturer (modeled as a single machine) has to organize the delivery of the items (performed by a single capacitated vehicle). The sequence of production is given, and is supposed to be the same as the sequence of delivery. The problem is to form batches of jobs, so that the total delivery time is minimised. We prove that the problem is NP-hard for a capacity equal to 2, and a pseudopolynomial time dynamic programming algorithm is proposed.

Several research directions are possible. First of all, several polynomial cases can be proposed for this problem, and dynamic programming algorithms can certainly be proposed. Second, finding the complexity of the problem if the number of sites is smaller than the number of jobs. For the general case when the sequences have to be determined, heuristic algorithms can be proposed, as well as decomposition approaches.

Figure 1 :

 1 Figure 1: Round trips with options A and B.

Figure 2 :

 2 Figure 2: The base schedule (i.e., B is always chosen).

Figure 4 :

 4 Figure 4: Round trips with option A only and option B only