Assem Yamak

Khaled El-Halabi

Dr Rabih Anklis

Dr Alfred Riachi

Dr Ahmad El-Rafii

Mouhamad Khalil

M Rami

M Ahmad Rifaii

M Nasser Safadi

M Adra

Fadi El-Masri

Keywords: Coordinated scheduling, Production and Delivery, Delivery and Inventory, Integrated models, Supply chain management, Heuristic, Batching, Dynamic programming, Branch and Bound, Mixed integer programming

The coordination of logistics activities in a supply chain has recently received a lot of attention in operations management research. In a typical supply chain, finished products are produced and either shipped to be temporary storage or arrived directly on time to the customers. To achieve optimal operational performance, the coordination and integration of production, delivery, and storage is an important consideration. The recent study considered customer storage cost with fixed transportation cost or fixed batch size. In this thesis, we study the coordination of batching and scheduling activities, which include the customer(s) orders which require the delivery time and cost from the supplier and the storage of products at the customer(s). This study focus on the multi-customer scenario and multitransporter scenario. For the first scenario with multi-customer, two models illustrate the transferring of batches to the customer. Where in the first model, we considered a multi-customer with one transporter available to serve the customers without the vehicle routing consideration. Then, in the second model, we considered a multi-customer with multi-transport available to serve the customers. Concerning the second scenario, we studied the case with multi-transporter available to serve a single customer. In this scenario, models with homogeneous and heterogeneous vehicles are studied. The costs and the distances depend of the transporters used or the customers according to the proposed scenario. The future extension of this research may involve considering the vehicle routing consideration with inventory in the multi-customer case.

Publications

 [8]HAMMOUDAN, Z., GRUNDER, O., & El MOUDNI, A. (2015) A genetic algorithm approach to the single-vendor multi-customer integrateddelivery-inventory problem. International Conference on Computers & Industrial Engineering (CIE45), International Conference. IFAC.

National conferences [2]

[9] HAMMOUDAN, Z., GRUNDER, O., & El MOUDNI, A. (2013) Minimisation des coûts dans une chaîne logistique simple, dans le cas multi-transporteur. 14 ème conférence de la société Francaise de Recherche Opérationnelle et Aide à la Décision (ROADEF) [10] HAMMOUDAN, Z., GRUNDER, O., & El MOUDNI, A. ( 2014) Optimisation combinée des couts de transport et de stockage dans un réseau logistique, multi-clients. 15ème conférence de la société Francaise de Recherche Opérationnelle et Aide à la Décision (ROADEF) First and foremost, i would like to to express my deepest sense of gratitude to my chief supervisor Professor Abdellah EL-MOUDNI and my co-supervisor Dr. Olivier GRUNDER. Thanks for their continuous academically and personally support and mentorship in these three years of study. Thanks for their guidance, suggestions and dedication throughout this thesis. They are one of the few people I know that have not lost a bit of their glittering enthusiasm about their job. Working with them was an interesting challenge, made up of hard work and fun at the same time. I would like to thank specially Dr. Olivier GRUNDER for working closely with me. His unconditional support in solving many details surrounding this dissertation and his valuable feedback's are deeply appreciated. A special thank to Dr. Raed KOUTA for all the good advice. Many thanks to the Board of Examiners, Dr. Lionel AMODEO, Dr. Slim HAMMADI, Dr. Abdelhakim ARTIBA and Dr. Philippe LUTZ for their constructive comments and suggestions which lead to a significant improvement in the thesis.

I strongly felt the ceaseless faith and support of my family along the way, I deeply thank my parents, Ahmad HAMMOUDAN and Fadia HAMMOUDAN, my brothers (Youssef, Yasser, Yahya and Abdel-razzak), my sisters (Fatima, Najwa, Nissrine, Hanadi, Nour and Zaynab), and my stepbrother (Khaled HASHEM, Nassim EL-GHARIB, Abdallah BAKER, Raed AL-YOUSSEF and Mouhamad HAM-MOUDAN). Their love and support are a constant inspiration to me in striving to improve myself. This dissertation is dedicated to you, specialy to my Mom and Dad. This dissertation would have not been possible without your supports. Further, I would like to express sincere thanks to my beloved one, Sarra EL-MAAZI, for her love, support and patience, allowing me to accomplish my goal and sharing with me all the happy and sad moments.

I also would like to express my appreciation to all my friends and colleagues at the IRTES-SET laboratory and at the UTBM university for lightening up my life every day and making graduate school more fun than I am sure it is supposed to be. In particular I would like to thank Dr. Imad MATRAJI, Dr. Mouhamad HARMOUSH, Dr. Fayez AHMED, Rabih ZAKARIA, Joseph EL-ASMAR, George GEORGES, Florant PERONET, Abdelrahim CHARIET, XUGUANG HAO, Dr. Jalil AB-BASS TURKI, Dr. Rachid BOUYEKHF, Dr. Mahjoub DIRIDI, Mouaz SAYED-AHMAD, Dr. Inaya LAHOUD, Dr. Mouhamad KABALO, Samer CHEHAIDI, Ghassan MOURAD, Malek SARMOUT, Zaher EL-CHAMI, Mouhamad KHALIL, Mouhamad SLEIMAN. Thanks also go out to the secretary of laboratory SET Ms.

Résumé

La coordination des activités dans une chaîne logistique a suscité de nombreux travaux de recherche dans le domaine du management et la recherche opérationnelle. Dans une chaîne logistique typique, les produits finis sont transportés pour être stockés temporairement ou arriver directement chez les clients. Pour obtenir la configuration opérationnelle optimale, la coordination et l'intégration de la production, de la livraison, et du stockage deviennent importantes. Des études récentes ont considéré le coût de stockage chez le client en fixant le coût de transport ou la taille des lots, mais dans la pratique cela se révèle plus complexe. Dans cette thèse, nous avons étudié la coordination entre le traitement et l'ordonnancement des lots, ce qui inclut les commandes des clients qui requièrent la livraison du fournisseur ainsi que le stockage des produits chez les clients. Ce travail se focalise sur les cas plusieursclients et plusieurs-transporteurs. Pour le premier scénario avec plusieurs-clients, deux modèles illustrent le transfert des lots aux clients. Dans le premier modèle, nous avons considéré plusieurs-clients avec un seul transporteur disponible pour servir les clients sans prendre en considération la tournée de véhicule. Puis, dans le deuxième modèle, nous avons étudié le cas de plusieurs-clients avec plusieurs transporteurs disponibles pour servir les clients. En ce qui concerne le deuxième scénario, nous avons étudié le cas avec plusieurs transporteurs disponibles pour servir un seul client. Dans ce scénario, des modèles avec les véhicules homogènes et hétérogènes sont étudiés. L'ensemble des coûts du système sont calculés en additionnant le coût de la livraison et de stockage pour les différents clients et transporteurs. Les coûts et les distances sont dépendants soient des transporteurs soient des clients suivant le scénario retenu. Dans chaque modèle, nous présentons les procédures de résolution, plusieurs exemples numériques pour soutenir les résultats mathématiques et pour clarifier le problème, ainsi que des comparaisons de performances entre les différents résultats. Les perspectives de recherche se situent actuellement dans la prise en compte de tournées entre les différents clients.

Introduction

Context

The competitive environment in the industrial companies to accommodate the maximum number of customers is considered as a key factor in the evolution of the companies, in order to increase their profits. Today, the issues of cost and time dissipation due to delays are becoming more and more important in terms of customer's requirements. As well, the simultaneous optimization of the production, transport and storage activities becomes a key factor in the success of a company specifically, and the whole supply chain generally. The objective of each supplier is to satisfy its customer demands with high service level requirements to meet the optimal total cost, which will ensure that the products are delivered in time, at the right location, in the right condition, in the right quantity. This relation of coordination between the supplier and its customers assimilate the situation as an integrated problem with taking into account all the related indicators that may an affect on the final cost, as the setup cost, the production cost, the storage cost at the supplier, the delivery cost and the storage cost at the customers.

The increased efficiency of foreign manufacturers in the late 1970s and early 1980s changed the thinking at the managers on the supply chain. The integrating decisions between the different members in the supply chain attracted the attention of companies, where they started to realize the potential cost benefits. At the beginning, the researchers failed to take an integrated view of the integral supply chain. They considered different sub-problems as production or distribution or distribution with inventory at the customer. These sub-problems were solved separately and the optimal solution were then joined together to establish an operating policies. Recently, the coordinated of logistics activities in a supply chain has recently received a lot of attention in operations management research. To achieve optimal operational performance, the coordination of production, delivery and storage is an important consideration.

This thesis studied different scheduling planning problems in various supply chain structures. We mainly consider an integrated Lot-Sizing Delivery-scheduling problems in two different axes: (1) Multiple Customers Lot Sizing Delivery Scheduling Problem (MCLSDSP) (real-world case from the pharmaceutical environment); [START_REF] Hammoudan | A coordinated scheduling of delivery and inventory in a central pharmacy of multi-hospitals[END_REF] Multi-Transporter Lot Sizing and Delivery Scheduling Problem (MT-LSDSP) with batch-size-dependent delivery time and cost.

Chapter 1

Introduction

In the first axe, we investigated a delivery-inventory supply-chain problem with multiple products in a multiple customers and taken into consideration a different parameters related to the health care due to the our real-world studied case from the pharmaceutical environment. The studied systems is composed of a central medical stores which has to deserve pharmaceutical supplies to different hospital sites at given due dates. The objective is to reduce the overall cost which includes the delivery costs and an earliness penalty that is incurred for medical supplies which are delivered before their due dates. For this case, different scenario of the delivery stage are proposed. In the second axe, we studied an integrated scheduling problem for a single item, in a supply chain environment involving a fleet of heterogeneous or homogeneous transporters with batch-size-dependent delivery time and cost. We assumed that a job that arrives at the customer before its due date will incur an earliness penalty depending on the considered job, with the objective is to find a coordinated lot sizing and scheduling scheme such that the total cost is minimized while guaranteeing a certain service level.

Methodology

The methodology, aims to demonstrate that much can be gained in a systematic intervention. This is a structured set of activities to assist people in undertaking research. Generally, a methodology will develop, either implicitly or explicitly, within a particular paradigm and will embody the philosophical assumptions [START_REF] Mingers | Multimethodology: towards a framework for mixing methodologies[END_REF]. Methodologies may emerge as broad prescriptions for good practice in using particular techniques. A high relation is between methodology and technique, where the methodology specifies what type of activities should be undertaken, and the techniques are particular ways of performing these activities. Moreover, each methodology has a number of possible techniques. The optimization of a problem described in a specific variables, where the complexity of the problem is defined as its number of variables and the complexity of the best possible algorithm can solve it. The integrated problems are classified into polynomially solvable and Nondeterministic Polynomial hard (NP-hard) problems. The polynomially solvable problems is that which can be solved by a polynomial time algorithm. A problem is called (NP-hard) if it can be solved by a polynomial time by a nondeterministic machine. Two important way is used to solve an NP-hard problem, that by encoding and enumerating all its feasible solutions, then select the best solution.

The integrated problems belongs to the combinatorial optimization problems. It is a critical hard and it needs an efficient tools in order to formulate and solve problems to make a final decision. Some frequently techniques are used to study the integrated problems comprise dynamic programming algorithm, branch and bound algorithm as an exact methods and some approximation algorithms as an approach methods. For these two exact methods, they help to simplify the search process for an optimal solution it needs to exploring the dominant properties. In this thesis 1.3 Outline of Dissertation we emphasize the modeling and algorithmic development of optimization models for different coordinated scheduling problems. Since the studied problems that we are dealing have high complexity, we focus on the development of efficient and effective heuristic algorithms for those problems. In chapter 3, we proposed two exacts methods to evaluate the coordinated scheduling of delivery-inventory problems with a single supplier and multiple customers. The first method is a mixed integer programming model, and the second one is a branch and bound algorithm supported by a lower bound. Then, we developed an heuristic approach and a genetic algorithm to solve these problems. In chapter 4 we developed a dynamic programming algorithm supported by a dominance and a mixed integer programming approach as an exact methods to solve the integrated scheduling problem with multiple transporters, then we developed a genetic algorithm as an approach method, which could solve the large instances. However, in chapter 5 we studied the case of single-supplier/multicustomer with multiple transporters assumption. For this problem, we proposed a general model with multiple heterogeneous transporters available to serve the customer without any allotment, then we have proposed different models with different delivery structures. For this work, we have developed branch and bound algorithm in the general case, and MIP model for each case solved by CPLEX.

Outline of Dissertation

In this dissertation, we study the coordination of scheduling activities by taken into consideration the integrated production and delivery scheduling with batchsize-dependent on the delivery times and costs in the case of multiple transporters, the coordination of delivery and inventory lot-sizing and batch-scheduling problem with multiple customers in the case of single transporter, and the coordination of delivery-inventory scheduling of multiple customers with multiple transporters. This dissertation is divided into four chapters.

Chapter 2 deals with an extensive literature review on batch scheduling problems and the related cases studied in this dissertation.

In chapter 3, we study the MCLSDSP with a multiple products consideration. We specifically consider a real-world scheduling problem which is motivated by a local pharmaceutical industry. In this problem, there is a central pharmacy which has to deserve pharmaceutical supplies to different hospital sites with a single transporter at given due dates. It is assumed that directing delivery method is used for sending the batches to the hospitals, which means that the jobs are transmitted to each customer separately [Chen, 2010]. The objective is to determine the optimal solutions for inventory lot size, scheduling programs and the number of deliveries to achieve hospitals goal with a minimum total cost for the central pharmacy.

In chapter 4, we discus the MT-LSDSP with batch-size-dependent delivery time and cost. Few research works have been conducted the multiple transporters characteristics in the context of the integrated production delivery problems, assuming Chapter 1 Introduction generally that a transporter is always available to deliver the products. In our work, we develop and analyze a scheduling model that takes into account the storage cost on both sides of the supply chain (supplier and customer) and the delivery time and cost which are dependent on batch-size. The consideration of batch-size-dependent delivery time and cost which take into account the loading and the unloading times, has not yet been studied as far as we know.

In chapter 5, we investigate the multiple transporters MCTLSDSP where different models for the supply of multi-items are proposed. In the first model which is a general case, the manufacturer transfers the jobs to a customer by a finite number of heterogeneous transporters without any allotment, whereas in the other extension models the batches are transferred to the customers by a number of transporters allotted to each customer. Under the first model, the general case of the singlesupplier/multi-customer with multiple transporters is studied, whereas for the second model it is a fleet of transporters available to deliver the jobs from the supplier to the customers where each customer is served by his allotted transporter. The intention of this work is to find an optimal solution technique for each of these two models, and through a sensitivity analysis explore for the best outcome. In this work, we mixed the both previous studied cases in chapters 3 and 4 to produce a new view to the global case of the multiple customers with multiple transporters, in the objective is to minimize the delivery and storage costs.

Introduction

The objective of all effort spent on supply chain management is to devise an optimal strategy between the different stages of supplying a product to develop, manage and operate the supply chain in order to satisfy customer's demand by producing the appropriate product at the right time and places with suitable quantity for the least expenses without lowering any product quality. An efficient supply chain requires a smooth logistics flow in all activities from moving the raw materials into finished products and from moving the finished products to the end customers. Coordination between production, transportation and storage activities can be a major in reducing total costs. In this chapter, we present a literature review on the different lot-sizing and scheduling problems. Lot-sizing and scheduling are important parts of the production process system. It is necessary to know how many items and in which order they have to be produced, to minimize the total costs.

The simultaneous optimization of the production, transport and storage activities becomes a key factor in the success of a company in specific, and the whole supply chain in general. The requirements generation is a key distinction, they may be generated directly by customers orders or indirectly by the different mentioned stages (production, transport and storage). The production scheduling is a sequencing problem and a lot-sizing decision associated with the inventory and transporters processes. The scheduling criteria indicates the measures upon which schedules are to be evaluated in term of schedule cost. The cost associated includes the fixed costs associated with production setups, transporter costs, inventory holding costs at the supplier or the customers.

An efficient supply chain requires a smooth logistics flow in all activities from moving the raw materials into finished products and from moving the finished products to the end customers. In this thesis, a single supplier supplying items to one or multiple buyers. The supplier produce the item in batches and at a finite rate. The supplier then sends the finished items to the buyer(s). In this process, the studied system(s) incur(s) batch delivery and storage costs, in different assumptions. Meanwhile, the buyer(s) has his own deterministic demand. In the problem under study, the supplier and the customer have a problem of determining the shipping schedule and the lot-sizing of each batch, which minimizes the operating cost. During the last three decades, researchers have been searching for the solution to to take an integrated view of the entire supply chain. They considered only one piece of the Chapter 2

State-of-the-Art overall problem, such as production or distribution sub-models. These sub-models were optimized separately and the solutions were then joined together to establish operating policies. The supplier and the buyer(s) have known as integrated supply chain system, rather than as separate individuals, total system cost can be reduced significantly. Here, we concentrate on developing optimization tools to enable companies to take advantage of opportunities to improve their supply chain. This chapter gives the propoerties of the studied models, the definitions of Lot-Sizing and Batch-Scheduling problems, a short overview of each problem is noted and we reviewed the Multi-level Lot-Sizing and Batch-Scheduling problems. The review then shifts to the integrated production-delivery-inventory problems with batchsize-dependent scenario and the delivery-inventory problems with incompatible jobs families and due dates objectives.

Description of a supply chain

In the integrated supply chain, the supplier needs to have a clear information about their customer(s) demand. Due to the great improvements in the electronic information, the exchange of the information between the supplier and the customer(s) becomes feasible. The diagrams in Figure 2.1 and Figure 2.2 show two integrated supply chain models, where in Figure 2.1 the flow of one/supplier multi/customer with one transporter, and the second diagram in Figure 2.2 shows the flow of sine/supplier single/customer with one transporter. The production planner is concerned with determining optimal production-inventory and distribution inventory levels for each product in every period so that the total cost of production, delivery and inventory holding is minimized. On the other hand, the distribution planner must determine schedules for distribution of products to customers so that the total transportation cost is minimized. The inventory and distribution planning problem decides on the replenishment policy at the warehouse and the distribution schedule for the customers, so that the total of inventory and distribution costs are minimized. In supply chain, transportation cost is a major part of operational cost. Transportation time, cost, and capacity constraint play a role in making decisions. In today's world, short life cycle and countless specialties of similar products have made the global market highly competitive. In order to survive market pressure, every company has to be highly competitive in terms of product quality, price and product supply. For example, shipping in smaller quantities and with high frequency reduces the inventory level at the warehouse, but causes higher transportation costs. The delivery and inventory activities can function independently if there is a sufficiently large inventory buffer that completely decouples the two. However, this would lead to increased holding costs and longer lead times, since on one side the distribution planer, in order to minimize transportation costs, would prefer full truck shipments and minimum number of stops; and on the other side the production planner would prefer less number of machine setups. The pressure of reducing inventory and lead times in the supply chain forced companies to explore the issue of closer coordination between production and distribution.

Lot-Sizing and Batch-Scheduling problems

The Lot Sizing problem (LSP) and Batch Scheduling Problem (BSP) are both parts of the most challenging subjects that arises in production planning for the supply chain managers. The LSP is the activity to transform customer demands into lots to minimize the total costs of setup costs, product change costs and inventory costs.

Chapter 2

State-of-the-Art

The objective of the LSP is to determine the periods in which production will take place and the quantities that have to be produced per period. The LSP depends on the setup times, which depend on the assignment of the machine and the product sequence which are fixed by the scheduling. The BSP is the activity when and which machine should be produced where there are no shortages in the production plan. Since each production series involves an additional cost of setup, thus the global production quantity has to satisfy the total demand of the customer and has to minimize the global cost of the system. The BSP needs the production volume to decide about the machine assignment and the sequence [Quadt, 2004].

The coordination between lot sizing and scheduling problems have the objective to make an optimal decision about the number of items by batch and also the sequence of the items, to make the production planning feasible.

Single-level lot-sizing and batch-scheduling problems

Historically, [Harris, 1913] predates the first work on LSP which is based on the economic order quantity (EOQ). He considered a model that assumes demands occur continuously over time. In the early fifties, the EOQ was followed by the dynamic model developed by [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF]. [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF] developed an extension of the work of [Harris, 1913], where they studied a model with a dynamic demand in each period and no capacity constraints with a finite time horizon. They find an optimal solution by using a dynamic programming algorithm to solve the problem. The [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF] model has received a considerable attention and it was discussed in several hundred papers. [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF] model is extended to Capacitated LSP, which is a singlelevel multi-item capacitated lot-sizing model. [Fleischmann, 1990] studied the CLSP with scheduling, where that is one setup per period for each item which is produced in the period. The setup occurs at the beginning of the period. The integration of the capacity constraint is defined in the Discrete LSP with scheduling is the "all-ornothing-assumption", where that is one item produced over a full period or not at all [Salomon, 1991]. In this case, the number of items of the consecutive batches must be the same. If the number of items by batch in two consecutive separated periods is changed, a new setup state must be taken into consideration. which mean that, in the DLSP the continuity of the setup time is not considered. The latter drawback is handled in the Continuous Setup LSP (CSLSP) which allows partial capacity usage. Still, only a single item can be produced per period. [START_REF] Brahimi | Single item lot sizing problems[END_REF] defined the CSLSP as a sequence independent kind of a small bucket problem, what still means that only one item can be produced per period, but the "all-or-nothing" assumption is given up. The problems with multi-item is classified as a coordinated lot-sizing and batch-scheduling problems. The first problem studied in this domain is the Economic Lot-sizing and batch-Scheduling Problem (ELSP) in [Salomon, 1991]. [Salomon, 1991] defined the model as a minimization of sum of setup and inventory holding costs, while determining the production schedule. The ELSP studied the model of multi-item produced separately. The twins of the CSLP with one item is the Proportional Lot-sizing and batch-Scheduling Problem (PLSP). In the PLSP two different items can be produced per period. We can use the capacity of a full period at most for two different items with only one changeover allowed per period.

The development of this model is the General Lot-sizing and batch-Scheduling Problem (GLSP). In the GLSP, the planning horizon is finite, the demand is dynamic and no backlogging is allowed. In this model, the periods are divided into subperiods, which allowed more than one setup per period with a restricted number of lots per period [START_REF] Drexl | Lot sizing and scheduling survey and extensions[END_REF]. The extension of the GLSP is the GLSP with Setup Times (GLSPST). The GLSPST is a single-level multi-item capacitated model with dynamic demand and a finite planning horizon [Tischer, 2007]. The objective of the GLSPST is to minimize the inventory holding costs and the sequence dependent setup costs [Meyr, 2000].

Recent applications of lot sizing and batch scheduling models are described in [START_REF] Relvas | Integrated scheduling and inventory management of an oil products distribution system[END_REF], [START_REF] Khan | An integrated supply chain model with errors in quality inspection and learning in production[END_REF] among others. [START_REF] Relvas | Integrated scheduling and inventory management of an oil products distribution system[END_REF] studied the lot sizing and batch scheduling with inventory management of an oil products distribution system, they have proposed two different models to the sizing decision of batch volume. The first one is the fixed batch size model (FBS) and uses a set of prefixed volumes of batches that vary with product, where a decision has to be taken to select which one to pump. On the other hand, the variable batch size model (VBS) provides for each product a valid interval for batch volume, being any intermediate value allowed. [START_REF] Relvas | Integrated scheduling and inventory management of an oil products distribution system[END_REF] proved that the (VBS) model offers a better final values than the (FBS). Next, [START_REF] Khan | An integrated supply chain model with errors in quality inspection and learning in production[END_REF] studied an integrated supply chain model with errors in quality inspection and learning in production, concerning the lot sizing problem they supposed that the supplier replenishes the order in a number of equal-sized shipments, there aim is to determine an optimal supplier-customer inventory policy for a single product.

Multi-Level lot-sizing and batch-scheduling problems

The DLSP, ELSP, PLSP, GLSP and GLSPST are single level models for simultaneous Lot-sizing and Batch-scheduling problems. The extension of the single level models mentioned above leads to the multi-level LSP (MLLSP) model which is studied in different complex real world industrial cases. The feature of the MLLSP is that the production of each item generates dependent demand for its constituent components, if any [START_REF] Brahimi | Single item lot sizing problems[END_REF] . [Tischer, 2007] classified the MLLSP as NP-hard problem and [Salomon, 1991] sorted it in four structures (Serial, Assembly convergent, Arborescent divergent and General network) as follows:

The serial product structure

The assembly product convergent structure

The arborescent product divergent structure As seen in Figure 2.3, in the serial structure each item has a single predecessor and a single successor in the network. For example the item B has the item A as predecessor and the item C as successor. The serial product structure is studied by [START_REF] Billington | Multi-item lotsizing in capacitated multi-stage serial systems[END_REF],

where they assumed a linear product structure and uniform processing times without setup times. They applied sequentially a multi-item single-level specialized heuristic to each level of the problem to solve the problem. This type of problem frequently occurs in "process" industries, furniture making, and apparel manufacturing. In furniture manufacturing, for instance, one product line can consist of several products that must be processed through an identical sequence of machines with a setup between products due to the different materials being used [START_REF] Billington | Multi-item lotsizing in capacitated multi-stage serial systems[END_REF].

For the assembly convergent structure represented in Figure 2.4, each item can be made from several predecessors and one successor. For example, the item E has two predecessors (A and B) and it has one successor which is the item G. [START_REF] Blackburn | Simultaneous lot-sizing and capacity planning in multi-stage assembly processes[END_REF] and [Simpson, 1999] and others, studied a different lot-sizing assembly systems and proposed several heuristics methods, where most of them based on the level-by-level approach found in Material Requirements Planning (MRP) system. [START_REF] Blackburn | Simultaneous lot-sizing and capacity planning in multi-stage assembly processes[END_REF] considered an assembly convergent system to study an alternative approach to the capacity planning problem, by integrating it with the MRP lot-sizing process. [Simpson, 1999] studied nine multiple level production planning heuristics under rolling horizon planning conditions. Four of nine evaluated heuristics in his study represents the sequential (level-by-level) application of single item lot-sizing technique. Four others represent these same algorithms applied in conjunction with the multiple level cost modification technique of [START_REF] Blackburn | Improved heuristics for multi-stage requirements planning systems[END_REF]. The ninth lot-sizing rule is an iterative technique which begins with a lot-for-lot solution proposed by him in [START_REF] Simpson | Improved heuristic methods for multiple stage production planning[END_REF]]. Then, he proposed a tight lower bound to evaluate these heuristics. His lower bound is similar to much of some mathematical programming developed for multiple level production planning proposed in ( [START_REF] Afentakis | Computationally efficient optimal solutions to the lot-sizing problem in multistage assembly systems[END_REF], [START_REF] Crowston | Dynamic lot size models for multi-stage assembly systems[END_REF], [Zangwill, 1969]). In contrast, the arborescent divergent structure represented in Figure 2.5 has at most one predecessor, but may have any number of successors. For example, the item B has one predecessor which is A and two successors are (D and E). The arborescent network is the prototype for a distribution system, whereby each node is represented as a warehouse may have at most one immediate predecessor as a distribution center, but possibly may have more than one successors seen as customers. The arborescent system was studied by [START_REF] Maxwell | Establishing consistent and realistic reorder intervals in production-distribution systems[END_REF] and [START_REF] Muckstadt | Multiitem, one-warehouse, multi-retailer distribution systems[END_REF]), in which the end-item (the customer demand) is constant. They have focused on the relationship of the reorder intervals at intermediate stages to the end-item reorder intervals. These analytic treatments lend insight to the overall problem, but do not appear easily adaptable to the more common situation of time-varying demand. [START_REF] Bookbinder | Replenishment analysis in distribution requirements planning*[END_REF] have em-Chapter 2

State-of-the-Art ployed a simulation model to study time-varying demands in a pure arborescent system. In a recent work focused on a part of it on the pure arborescent system, [START_REF] Bookbinder | Production planning for mixed assembly/arborescent systems[END_REF]] studied a complex manufacturing system often has arborescent or non-assembly portions in its network. They compared the pure arborescent system with the pure assembly systems, then they proposed a mixed assembly/arborescent systems. They concluded that the pure arborescent system could give an optimal total cost, if cost revision is not applied. The arborescent system could be used in a sub-assembly line in automotive company and in the distribution center. Finally with the general network structure represented in Figure 2.6, here each item can be made from several predecessors and can have several successors. For example, item F has two predecessors are (C and D) and two successors are (H and I). The general assembly structure is studied by [START_REF] Wang | Data driven production modeling and simulation of complex automobile general assembly plant[END_REF], where they proposed an automotive general assembly plant and developed a data driven simulation method to integrate assembly, arborescent and serial structures with Just-in-Time (JIT) and Material Handling System (MHS). They developed a data driven approach to automatically generate simulation model based on manufacturing process parameters and configurations, and also real-time update the model based on dynamic production information during the simulation running phase. They applied their work to a typical automotive general assembly plant to quickly and automatically generate simulation model for production analysis. The objective of the MLLSP is to minimize the relevant costs which are the setup costs, the inventory holding cost and the production costs [Salomon, 1991].

In this thesis, we study the coordination of scheduling activities, which includes the coordinated lot-sizing and delivery scheduling problems. At the most general level, coordination can be seen in terms of integrating decisions of different functions (for example, inventory planning, production planning, distribution planning, etc.). [START_REF] Bhatnagar | Models for multi-plant coordination[END_REF] refer to this level of coordination as "general coordination". At another level, the problem of coordination may be addressed by linking decisions within the same function at different echelons in the organization. They classified the research on general coordination into three categories as follow:

Supply and production planning

Inventory and distribution planning

Production and distribution planning These categories represent integration of decision-making related to studies on coordination between supplier and customer(s) focused on determining the order quantity that is jointly optimal for both. Our work contributes to the second and third research categories. We consider complex supply chain with decisions on integrated production-delivery-inventory problems.

The integrated Production-Delivery-Inventory problems

An integrated production and distribution planning problem is the problem of simultaneously finding the decision variables from different functions that have traditionally been optimized independently [START_REF] Seyedhosseini | An integrated model for production and distribution planning of perishable products with inventory and routing considerations[END_REF]). Production planning tackles decision of how to transform raw materials into finished products respecting to meet demands on time with minimum cost. Determining lot sizes, that is, calculating the quantity to be produced for each item at each time, is an important decision in tactical production planning. On the other hand, distribution planning tackles decision of how to deliver the finished products to the customers respecting to meet their demands on time with minimum cost. Integrated production and distribution system often includes facilities producing the products and number of distribution centers warehousing products. Due to the number of decision variables to be determined, the integrated production and distribution planning problem is so complex that optimal values are very hard to obtain. In addition, considerations such as complex structure of the network, geographical span of the supply chain, and involvement of different entities with conflicting objectives can further complicate the problem [START_REF] Pandey | Adaptive logistic controller for integrated design of distributed supply chains[END_REF]. Indeed, simplification of a real-life scenario in developing a supply chain model has become unavoidable as most of the complex production delivery planning problems are classified under the category of NP-hard problems [START_REF] Thomas | Coordinated supply chain management[END_REF] and [START_REF] Ajian | An integrated model for optimising manufacturing and distribution network scheduling[END_REF].

Basic studied models

The integrated production and delivery with inventory costs planning was studied by several researchers. [START_REF] Blumenfeld | Analyzing trade-offs between transportation, inventory and production costs on freight networks[END_REF] determined optimal shipping policies (direct shipping, shipping via a consolidation terminal and a combination of terminal and direct shipping) by analyzing trade-offs between transportation, inventory and production setup costs. In another work, [START_REF] Blumenfeld | Synchronizing production and transportation schedules[END_REF] considered the problem of scheduling production and distribution for a producer supplying parts to a final assembly manufacturer. They considered a very specific scenario that featured one destination per part type, identical production cycles with each production cycle including a production run of every part type, and fixed transportation costs per shipment. They showed that coordination can reduce costs by up to 42% and that maximum savings occur when the demand, item value and variable costs are the same for all items. [START_REF] Blumenfeld | Reducing logistics costs at general motors[END_REF] reported a successful implementation of this research at GM's Delco electronics division that resulted in a 26% ($2.9 million per year) reduction in logistics costs. More recently, [START_REF] Chandra | Coordination of production and distribution planning[END_REF] studied a plant that produces a number of products over time and maintains an inventory of finished goods at the plant. The products are distributed by a fleet of trucks to a number of retail outlets at which the demand for each product is known Chapter 2

State-of-the-Art for every period of a planning horizon. They compared two approaches to managing this operation, one in which the production scheduling and vehicle routing problems are solved separately, and another in which they are coordinated within a single model. their results showed that the reduction in total operating cost from coordination ranged from 3% to 20%, which indicates that the conditions under which companies should consider the organizational changes necessary to support coordination of production and distribution. [START_REF] Fumero | Synchronized development of production, inventory, and distribution schedules[END_REF] proposed an integrated optimization model for production, distribution and inventory planning, with the aim of optimally coordinating important and interrelated logistic decisions such as capacity management, inventory allocation, and vehicle routing.

They solved the integrated production distribution model via Lagrangian relaxation. [START_REF] Bertazzi | Minimizing the total cost in an integrated vendor-managed inventory system[END_REF]] considered a complex production-distribution inventory system, where a facility produces several items which are distributed to a set of retailers by a fleet of vehicles with a fixed transportation costs. They proposed two different policies: The order-up-to level policy, in which the order-up-to level quantity is shipped to each retailer whenever served (i.e. the quantity delivered to each retailer is such that the maximum level of the inventory at the retailer is reached) and the fill-fill-dump policy, in which the order-up-to level quantity is shipped to all but the last retailer on each delivery route, while the quantity delivered to the last retailer is the minimum between the order-up-to level quantity and the residual transportation capacity of the vehicle. Two different decomposition of the problem are proposed together with optimal or heuristic procedures for the solution of the sub-problems. They concluded that the fill-fill-dump policy reduces the average cost with respect to the order-up-to level policy and that one of the decomposition is more effective.

In the recent years, the integrated production-delivery-inventory problem has received a lot of attention. [START_REF] Sarmiento | A review of integrated analysis of production-distribution systems[END_REF], [START_REF] Fahimnia | A review and critique on integrated production-distribution planning models and techniques[END_REF] and [Chen, 2010] provided comprehensive reviews on the general subject. [Chen, 2010] reviewed the production and distribution scheduling models and classified these problems in five classes: (1) models with individual and immediate delivery; (2) models with batch delivery to a single customer by direct shipping method; (3) models with batch delivery to multiple customers by direct shipping method; (4) models with batch delivery to multiple customers by routing method (5) models with fixed delivery departure date. In the first model, jobs have delivery windows, and thus production windows can be incurred, however, due to the immediate and individual delivery requirement, the problems under this model can be reduced to fixed-interval scheduling problems (without the delivery). For all other models, no production windows have been specially considered in the survey. Problems addressing an objective function that combines machine scheduling with the delivery costs are rather complex. However, they are more practical than those involving just one of the two factors, since these combined-optimization problems are often encountered when real-world supply chain management is considered. [Bard and Nananukul, 2009a] solved the production and delivery problem in three different works. In the first one , they formulated an integrated lot sizing and inventory routing problem as 2. [START_REF] Grunder | Production and Delivery Integrated Scheduling to Minimize the Costs with Heterogeneous Transporters[END_REF] The integrated Production-Delivery-Inventory problems a mixed integer program with the objective of maximizing the net, and they developed a two-step algorithm to estimate daily delivery quantities and then solved the problem for each day of the planning horizon [Bard and Nananukul, 2009a]. After this work, they proposed an algorithm centered on reactive tabu search in [START_REF] Bard | The integrated production-inventory-distribution-routing problem[END_REF] for solving a model with a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of vehicles for making the deliveries. In [START_REF] Bard | A branch-andprice algorithm for an integrated production and inventory routing problem[END_REF], they proposed a hybrid methodology that combines exact and heuristic procedures within a branch-and-price framework for an integrated production and inventory routing problem. These results showed that, the proposed hybrid scheme can solve medium and large instances with up to 50 customers and 8 time periods within 1 hour. This level of performance could not be matched by standard branch and price alone. [START_REF] Fu | Coordinated scheduling of production and delivery with production window and delivery capacity constraints[END_REF] studied the problem of coordinated scheduling of production and delivery subject to the production window constraint and the delivery capacity constraint. They considered a single delivery time case and multiple delivery time case. On the first one the problem became a LSP and no delivery schedule is necessary.

On the case of the multiple delivery time, the goal is to find a feasible coordinated production and delivery schedule whose total profit is close to optimal which means that it is not optimal.

Extension of the basic models

Determining the optimum batch size is related to the determining of the ordering policy for procurement of raw materials, the production schedule, the level of inventory, distribution batch size etc. In the classical ordering policy, it is often assumed that the shortages are either completely backlogged or completely lost. In reality, often some customers are willing to wait until replenishment, especially if the wait will be short, while others are more impatient and go elsewhere. The relation between the order-size and the batch-size is very complex, whereas the batch-size is a solution of the order-size. The batch-size could be represented in the different stage of the supply chain, but the order-size is represented mostly in the first stages under study. [START_REF] Chuang | An integrated inventory model with order-size-dependent trade credit and quality improvement[END_REF]] studied an integrated supplier-customer inventory model with an order-size-dependent trade credit and defective items. Their model is related to the customer's order quantity; the customer can fully delay its payment if its order reaches a threshold quantity, but otherwise may only partially delay its payment. They proposed an iterative algorithm to solve the problem. They found that the supplier should set the proportion of partial delay payment and the threshold quantity more careful, therefore the supplier can avoid the more loss in profit and to attract the sales more effective. Most of authors assumed that the equal batches sizes in their works to prevent the complexity of the batch-size problematic. The equal batches sizes is presented by [Szendrovits, 1975]. His work is extended by [Goyal, 1976], where they fixed the transportation cost with a regardless of the batch-size. After that, [START_REF] Szendrovits | Optimizing multi-stage production with constant lot size and varying numbers of batches[END_REF] developed Chapter 2

State-of-the-Art the equal-sized batch and showed that this assumption reduces the total costs in a multi-stage production-inventory system to reduce the work-in-process. In the early nineties, [START_REF] Sarker | An optimal batch size for a production system operating under a fixed-quantity, periodic delivery policy[END_REF]] developed an ordering policy, for raw materials to meet the requirements of a production facility under a fixed quantity, periodic delivery policy. They considered that the manufacturer is allowed to place only one order for raw material per cycle. They fixed the delivered batch-size and the delivery time in a fixed interval. An exact algorithm is proposed to solve the problem. In another work, [START_REF] Sarker | Optimal batch size and raw material ordering policy for a production system with a fixedinterval, lumpy demand delivery system[END_REF]] developed a model with multiple lots of raw material for one lot of the product. The objective is to minimize the total cost for meeting equal shipments of the finished products, at fixed intervals, to the customers. In a recent work, [START_REF] Sarker | An optimal batch size for a production system operating under periodic delivery policy[END_REF]] considered a similar model to ( [START_REF] Sarker | An optimal batch size for a production system operating under a fixed-quantity, periodic delivery policy[END_REF] and [START_REF] Sarker | Optimal batch size and raw material ordering policy for a production system with a fixedinterval, lumpy demand delivery system[END_REF]), but without the assumption of delivery of final product to the customer. They assumed that the production order-size equal to the delivery batch-size, and a product cannot be delivered until the whole lot is finished and quality certification is ready. In a recent work, [START_REF] Bogaschewsky | Optimizing multi-stage production with constant lot size and varying number of unequal sized batches[END_REF] solved the problem of multi-stage production/inventory system where subsequent batch shipments are of unequal size. Due to the complexity of the model, it required developing algorithms for finding the optimal solution. [START_REF] Hill | Another look at the singlevendor single-buyer integrated production-inventory problem[END_REF] relaxed the assumption said that the first k shipments increase in size, and that the last n -k shipments are of equal sizes, studied by [Hill, 1999]. [START_REF] Hill | Another look at the singlevendor single-buyer integrated production-inventory problem[END_REF] relaxed the assumption that the customer's inventory carrying charges exceed those at the supplier. The multi-product lot-sizing problem with sequence-dependent setup times is studied by [START_REF] Clark | Rolling-horizon lotsizing when set-up times are sequence-dependent[END_REF]. They formulated a mixed-integer programming model to solve the problem. The sequence-dependent setup times and cost is examined by [START_REF] Transchel | A hybrid general lot-sizing and scheduling formulation for a production process with a two-stage product structure[END_REF], where they studied the problem of multi-product production planning and scheduling. [START_REF] Sajadieh | An integrated vendor-buyer model with stock-dependent demand[END_REF]] investigated an integrated production-inventory model for two-stage supply chain (supplier-customer) where the demand of customers at the customer is stock-dependent. [Grunder, 2010] considered a single-product batch scheduling problem with the objective of minimizing the sum of production, transportation and holding cost. Particularly, he assumed that the delivery time depend on the batch sizes and proposes a dynamic programming approach based on a dominance relation property. [START_REF] Wang | Single-item production-delivery scheduling problem with stage-dependent inventory costs and due-date considerations[END_REF] have extended this study to an integrated scheduling problem for single-item supply chain involving due date considerations with the objective of minimizing the total logistics cost.

[ [START_REF] Khanra | An eoq model for a deteriorating item with time dependent quadratic demand under permissible delay in payment[END_REF] developed an EOQ (Economic Order Quantity) model for a deteriorating item having time dependent demand when delay in payment is permissible. The deterioration rate is assumed to be constant and the time varying demand rate is taken to be a quadratic function of time. [Mishra and Sahab Singh, 2011] developed the inventory model for deteriorating items with time dependent linear demand and holding cost. Most recently, [Glock, 2012] studied a single-supplier-singlecustomer integrated inventory model with lot size-dependent lead time. They as-2.5 The integrated Delivery-Inventory problems sumed that lead time consists of production and setup and transportation time.

They showed that lead time reduction is especially beneficial in case of high demand uncertainty and that may either be reduced by shortening setup and transportation time or by increasing the production rate, which results in a reduced production time. [START_REF] Pal | A production inventory model for deteriorating item with ramp type demand allowing inflation and shortages under fuzziness[END_REF] worked on price and stock dependent demand for deteriorating item under inflation and delay in payment. [Swami et al., ] considered an economic ordered quantity model for deteriorating item with stock dependent demand and holding cost per unit time.

The integrated Delivery-Inventory problems

The distribution planning tackles decision of how to deliver the finished products to the customers respecting to meet their demands. The delivery and inventories management have a decisive influence on the effectiveness of the distribution process.

Previously, the delivery and the inventory management in the distribution process optimization was usually considered independently with a negligible mutual impact.

However, the integrated delivery-inventory problem has recently motivated some authors to model these two activities simultaneously, in the objective to minimize the total delivery-inventory costs. The delivery-inventory problem is denoted as Vendor-Managed Inventory (VMI) problem. [START_REF] Borade | Decision support system for vendor managed inventory supply chain: a case study[END_REF] says that, the VMI problem is a widely used collaborative inventory management policy in which manufacturers manages the inventory of retailer and takes responsibility for making decisions related to the timing and extent of inventory replenishment. VMI partnerships help organizations to reduce demand variability, inventory holding and distribution costs.

A pioneering paper is due to [START_REF] Bertazzi | Minimization of logistic costs with given frequencies[END_REF], where a given set of shipping frequencies is allowed and different products may be shipped at different frequencies. Several heuristic algorithms, based upon the idea of first solving single link problems and then locally improving the solution, are proposed. The effectiveness of these proposed heuristics has been evaluated according to [START_REF] Burns | Distribution strategies that minimize transportation and inventory costs[END_REF], where [START_REF] Bertazzi | Minimization of logistic costs with given frequencies[END_REF] showed that the efficiency of these proposed heuristics, in terms of the required computational resources, is certainly lower than the efficiency of different approaches, such as the one based on the method by [START_REF] Burns | Distribution strategies that minimize transportation and inventory costs[END_REF]. [START_REF] Herer | The metered inventory routing problem, an integrative heuristic algorithm[END_REF] considered a system of a central warehouse, a fleet of trucks with a finite capacity, and a set of customers, for each of whom there is an estimated consumption rate, and a known storage capacity. The objective is to the determine when to service each customer, as well as the way to be performed by each truck, in order to minimize the total discounted costs. To solve the problem, they proposed a rolling horizon approach that takes into consideration holding, transportation, fixed ordering and stock out costs. [START_REF] Viswanathan | Integrating routing and inventory decisions in one-warehouse multiretailer multiproduct distribution systems[END_REF]] considered a distribution systems with a central warehouse and many retailers that stock a number of different products, where the products are delivered from the warehouse to Chapter 2

State-of-the-Art the retailers by vehicles that combine the deliveries to several retailers into efficient vehicle routes. they proposed a heuristic that develops a stationary nested joint replenishment policy. These results showed that, the proposed heuristic is capable of solving problems involving distribution systems with multiple products. [START_REF] Sindhuchao | An integrated inventory-routing system for multi-item joint replenishment with limited vehicle capacity[END_REF] considered a system that consists of a set of geographically dispersed suppliers that manufacture one or more non-identical items, and a central warehouse that stocks these items. The warehouse faces a constant and deterministic demand for the items from outside retailers. The items are collected by a fleet of vehicles that are dispatched from the central warehouse. The vehicles are capacitated, and must also satisfy a frequency constraint. They studied the case where each vehicle always collects the same set of items. They formulated and solved the problem by using a branch-and-price algorithm, then they proposed a greedy constructive heuristics and a very large-scale neighborhood search algorithm. These results indicates that the constructive heuristics used in conjunction with one of the proposed very large-scale neighborhood algorithms can find near-optimal solutions very efficiently. [START_REF] Archetti | A branch-and-cut algorithm for a vendor-managed inventory-routing problem[END_REF]] considered a distribution problem in which a product has to be shipped from a supplier to several retailers over a given time horizon. Each retailer defines a maximum inventory level. The supplier monitors the inventory of each retailer and determines its replenishment policy, guaranteeing that no stock out occurs at the retailer (supplier-managed inventory policy). Every time a retailer is visited, the quantity delivered by the supplier is such that the maximum inventory level is reached (deterministic order-up-to level policy). Shipments from the supplier to the retailers are performed by a vehicle of given capacity. They presented a mixed-integer linear programming model and they derived new additional valid inequalities used to strengthen the linear relaxation of the model. They implemented a branch-and-cut algorithm to solve the model optimally. Then, they studied two different types of replenishment policies in [START_REF] Archetti | Analysis of the maximum level policy in a production-distribution system[END_REF]. The first one is the well-known order-up to level (OU) policy, where the quantity shipped to each retailer is such that the level of its inventory reaches the maximum level. The second one is the maximum level (ML) policy, where the quantity shipped to each retailer is such that the inventory is not greater than the maximum level. They showed that, when the transportation is outsourced, the problem with OU policy is NP-hard, whereas there exists a class of instances where the problem with ML policy can be solved in polynomial time. They also showed the worst-case performance of the OU policy with respect to the more flexible ML policy. In this study, [START_REF] Archetti | Analysis of the maximum level policy in a production-distribution system[END_REF] focused on the ML policy and the design of a hybrid heuristic, they implemented an exact algorithm for the solution of the problem with one vehicle and designed a hybrid heuristic for the multi-vehicle case. These results showed that the proposed heuristic can produce high quality solutions in a very short amount of time. In [START_REF] Archetti | A hybrid heuristic for an inventory routing problem[END_REF], they studied the previous problem with a single vehicle which has a given capacity. The transportation cost is proportional to the distance traveled, whereas the inventory holding cost is proportional to the level of the inventory at the customers and at the supplier. They proposed a heuristic that combines a tabu search scheme with ad hoc designed mixed-integer 2.5 The integrated Delivery-Inventory problems programming models. The effectiveness of the heuristic was proved over a set of benchmark instances for which the optimal solution was known.

Basic studied models

In the supply chain management literature, the single-supplier single-customer problem has received a lot of attention in recent years as it is the building block for the wider supply chain. The global supply chain can be very complex and link-by-link understanding of joint policies can be very useful [START_REF] Ben-Daya | The joint economic lot sizing problem: Review and extensions[END_REF]. The integrated single-supplier single-customer problem is called the joint economic lot sizing problem (JELP). This term is coined by [START_REF] Banerjee | A coordinated order-up-to inventory control policy for a single supplier and multiple buyers using electronic data interchange[END_REF]. The basic policies considered in the literature for JELP were based on the combination of the equal-shipment sizes and the increasing shipment sizes. The reason for considering these two policies is that the requirement of equal-shipment sizes is good from the customer's perspective. However, having a small first shipment followed by larger ones leads to a small minimum system stock, which means a reduced average system inventory.

One of the early works related to JELP was due to [Goyal, 1977], he proposed a simple model with infinite production rate and lot-for-lot assumption. In his research, the supplier produces in lots and sends the entire lot to the customer. [START_REF] Banerjee | A coordinated order-up-to inventory control policy for a single supplier and multiple buyers using electronic data interchange[END_REF] kept that lot-for-lot policy, but relaxed the assumption of infinite production rate. [Goyal, 1988] contributed to the efforts of generalizing the problem by relaxing the lot-for-lot policy. He assumed that the production lot is shipped in a number of equal-size shipments, but only after the entire lot has been produced and he showed that his joint total relevant cost is less than or equal to that of the JELP model. In [Goyal, 1995], a different approach than equally-sized shipment to come up with an idea of geometric shipment size is used. This means that the successive shipment size is the product of the prior shipment size in relation to the ratio of production and demand rate. In this paper, the author formulated the problem and gave the optimal expression for the first shipment size as a function of the number of shipments. [Viswanathan, 1998] called the model of [Goyal, 1995] as the "deliver what is produced" (DWP) policy, and showed the model studied by [Lu, 1995], where he called it as "Identical delivery quantity" (IDE). [Viswanathan, 1998] concluded that neither policy is better than the other for all type of problems, and the best policy depends on the problem's parameters. [Hill, 1997] generalized the model of [Goyal, 1995] by taking the geometric growth factor as a decision variable. He showed numerically that his policy outperforms both the equal-shipment-size policy and the policy adopted by [Goyal, 1995]. [Goyal, 2000] extended the work of [Hill, 1997], by proposed that the following shipment sizes will be determined by first shipment size. The following shipment sizes are depended of the production rate. The resulting improvement was demonstrated with a small number of experiments. It was unclear whether the improvement was in general significant, or for what kind of problems it is so.

Chapter 2

State-of-the-Art

In a recent work, [START_REF] Goyal | Determination of economic production-shipment policy for a single-vendor-single-buyer system[END_REF] suggested that among "n" shipments, the first shipment is smaller and followed by (n -1) equal-sized, which is equal to the product of the first shipment size as well as its rate of production over rate of demand. [START_REF] Pan | A study of an integrated inventory with controllable lead time[END_REF] extended the work of [Goyal, 1988], where they argued that better customer satisfaction levels and reduced safety stock levels can be achieved through improving lead-time. However, these changes occur at the expense of lead-time crashing cost. In a recent work, [START_REF] Zanoni | Vendor managed inventory (vmi) with consignment considering learning and forgetting effects[END_REF] compared different policies (equal or nearly equal in size). They considered two issues, which are the "VMI with consignment" inventory policy and the "Learning Curve". They showed how learning in production can give flexibility to the supply chain stake holders in assigning the size and the time of each shipment. In [Bylka, 2013] the assumption on equal in size deliveries has been relaxed. He presented a continuous deterministic model, and to satisfy the customer's demands, he supposed that the product is delivered in discrete batches from the supplier's stock to the customer's stock and all shipments are realized instantaneously.

Problems with different shipment policies

The papers listed above incorporated the problem under an assumption on shipment policy, in which the sizes of successive shipments either are increased by a factor or are equal in size. [Hill, 1999] combining these two type of policies, derived the structure of a globally optimal production distribution cycle. He showed that the structure of the optimal policy includes shipments increasing in size according to a geometric series followed by equal-sized shipments. He also suggested an exact iterative algorithm for solving the problem. [Hill, 1999] was revisited by [START_REF] Hill | Another look at the singlevendor single-buyer integrated production-inventory problem[END_REF], who relaxed the assumption that the customer's inventory carrying charges exceed those at the supplier. This is the case especially if the supplier is a small specialist manufacturer with little storage space available and the customer a large company, which possesses low-cost storage facilities. They showed how the optimal batch shipment policy may be derived when unit stock-holding costs increase as the product moves down to the customer under non-required equal shipping size. An alternative solution technique for the problems studied by [Hill, 1999] and [START_REF] Hill | Another look at the singlevendor single-buyer integrated production-inventory problem[END_REF], which guarantees that the optimal solution is always found, can be found in [Hoque, 2009]. The model studied in [Hill, 1999] and revisited by [START_REF] Hill | Another look at the singlevendor single-buyer integrated production-inventory problem[END_REF], has been modified by [START_REF] Zhou | Optimal production and shipment models for a single-vendor-single-buyer integrated system[END_REF], where they refuted the assumptions that customer's unit holding cost is greater than the supplier's or not, and they also allowed shortages but only for customers. They showed that their model performs better in reducing the average total cost regardless of the supplier's or customer's stock-holding costs, which are never equal to each other. In this study they observed that it is more beneficial for the integrated system to make the supplier's holding cost higher than the customer's than to make the supplier's holding cost lower than the customer's if shortages are not permitted to occur, otherwise it just reverses. In a most recent work, [START_REF] Bylka | The consignment stock of inventories in coordinated model with generalized policy[END_REF] 2.5 The integrated Delivery-Inventory problems developed a continuous deterministic model with centralized decision process, and proposed two types of shipment strategies, neither required equal in size of all deliveries nor assumed the delivery cost per shipment is the same. Further, they considered that the stock level at the customer as a decision with respect to a possible choice of shipment policy used. Their developed model is realistic and general in the sense that the well know results such as [START_REF] Braglia | Modelling an industrial strategy for inventory management in supply chains: the'consignment stock'case[END_REF]] and [START_REF] Zanoni | A note on an industrial strategy for stock management in supply chains: modelling and performance evaluation[END_REF] are special case of their proposed model.

In all models above, it has been implicitly assumed that the transportation cost is part of the ordering cost. This assumption is not in general valid because transportation cost is affected by the routing decisions and the selected shipment size. [START_REF] Baumol | An inventory theoretic model of freight transport demand[END_REF] introduced freight cost into an inventory model. They proposed two models for inventory cost minimization and profit maximization. In those models, they include freight rates, speed, variance in speed, and the en-route losses in an order-sizing model. They assume that unit shipping cost is fixed and is not dependent on the shipment size. [START_REF] Abad | Incorporating transport cost in the lot size and pricing decisions with downward sloping demand[END_REF] studied the problem of determining the re-seller's lot size and pricing assuming that the re-seller is responsible for paying for freight. They assumed that the final demand for the product is sensitive to the selling price that the re-seller sets. Another paper that considers transportation cost is [START_REF] Ertogral | Production and shipment lot sizing in a vendor-buyer supply chain with transportation cost[END_REF]. They developed two models that integrate the transportation cost explicitly in the single-supplier/single-customer problem. For the first model, the transportation cost is considered to be in an all-unit-discount format. In the second model, they explored the option of over declaring a shipment to exploit the transportation unit cost structure. They concluded that the explicitly integrating transportation cost could be realize a savings, and could affected on the inventory decisions.

Few research works have been conducted in the context of the integrated deliveryinventory problems with multi-transporters, assuming generally that a transporter is always available to deliver the products. Consequently, such problems can be classified into two classes based on the vehicle availability. The first class assumes that there are an infinite number of vehicles available at each departure time, whereas the second class assumes that there are a limited number of vehicles available at each departure time. [START_REF] Wang | Production and transport logistics scheduling with two transport mode choices[END_REF] and [START_REF] Stecke | Production and transportation integration for a make-to-order manufacturing company with a committo-delivery business mode[END_REF] have considered problems with different types of vehicles. In these both papers, vehicles are heterogeneous due to different characteristics, like their delivery speed, cost or capacity. Mainly, it is assumed that the fastest vehicle is more costly. [Omar, 2009] considered an integrated production-delivery system to determine the number and sizes of shipments which minimizes the total cost assuming the supplier and customer collaborate and find a way of sharing the consequent benefits. In this case, the optimal policy may be derived when the shipments size are identical. [START_REF] Merzouk | The holding and the transportation costs optimization in a simple supply chain: The multiple transporters case[END_REF] studied the multiple transporters in a simple supply chain with a so-called widthfirst search Branch and Bound. The manufacturer cost is considered to be the same for all jobs and linear with respect to the holding time. However the proposed exact method could not solve the medium to large size instances. In all models above, it is Chapter 2

State-of-the-Art assumed that the transportation of the products has processed without the routing of the transporters between the customers. Another major research direction considered the case of one-supplier/multi-customer supply chains with inventory routing problem.

Problems with due date objectives

In this subsection, we reviewed the integrated problems with due date constraints.

The due-date assignment problem has already been considered as a critical factor during the negotiation process in supply chains. When the demand is high, these lead times will be understated leading to missed due dates and disappointed customers, or to higher costs due to expediting. When the demand is low, they will be overstated and some customers may choose to go elsewhere. In scheduling theory, one of the most important criteria for measuring the performance of schedules is related to due dates or deadlines. Performance measures involving due dates model the informal criteria that are applied by practitioners. This makes these objective functions a very attractive and widely explored subject of research [Sterna, 2011].

In practice, the scheduler may needs an efficient method for quoting the due dates and job scheduling. Thus, an increasing number of studies have considered the due date assignment as a part of the scheduling problem, where they showed that the determination of due dates can be a major factor in improving system performance. Several methods have been proposed to establish and specifying an optimal due dates or to solve scheduling problems with due-date constraints. The duedate assignment procedure is concerned with the performance of some scheduling rules. The problems with due date determination have received considerable attention in the last three decades due to the introduction of new methods of inventory management such as just-in-time concepts [Hsu, 2013]. Early research on due date assignment in single-machine scheduling is conducted by [Seidmann et al., 1981]and [START_REF] Panwalkar | Common due date assignment to minimize total penalty for the one machine scheduling problem[END_REF], where they considered the constrained version where the scheduler must decide on a common due date for all the jobs (this due date assignment method is usually referred to as common due date assignment method). Many studies have focused on the common due date assignment problem. For reviews of scheduling models that consider common due date assignment with practical applications, the reader can refer to [START_REF] Lauff | Scheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey[END_REF], [START_REF] Cheng | Survey of scheduling research involving due date determination decisions[END_REF]] and [START_REF] Gordon | A survey of the state-of-the-art of common due date assignment and scheduling research[END_REF]). While [Seidmann and Smith, 1981] study the unrestricted case where each job can have a different due date. They proposed a method to identify due date for incoming order. They presented an analytical formulation of a dynamic single-machine scheduling problem with an objective of minimizing expected aggregate cost per job. These studies have inspired extensive research on due date assignment in scheduling as [START_REF] Cheng | Survey of scheduling research involving due date determination decisions[END_REF]], [START_REF] Gordon | A survey of the state-of-the-art of common due date assignment and scheduling research[END_REF] and [START_REF] Gordon | Scheduling with due date assignment under special conditions on job processing[END_REF]. Most of researchers in the eighties and early nineties have dealt with due date decisions under a single product and single stage production system. In the early years of the current century [ Van Ooijen and Bertrand, 2001] 2.5 The integrated Delivery-Inventory problems studied the investigation of the setting of optimal cost internal due dates for determining the priorities on the floor shop.

The due-date management or orders with availability intervals and lead time sensitive revenues in a single-server setting is studied by [START_REF] Keskinocak | Scheduling and reliable lead-time quotation for orders with availability intervals and lead-time sensitive revenues[END_REF] .

In their model, revenues obtained from the customers are sensitive to the leadtime, there is a threshold of lead-time above which the customer does not place an order and the quoted lead times are 100% reliable. They showed that different strategies for quotation are needed for different categories of customers. The benefits of lead time flexibility to the manufacturer in an offline setting with 100% service guarantees have been studied by [START_REF] Charnsirisakskul | Pricing and scheduling decisions with leadtime flexibility[END_REF]. They presented an optimization model for due date and price sensitive customers under deterministic demand function. The pricing and lead-time decisions from a supplierretailer perspective considered by [START_REF] Liu | Pricing and lead time decisions in decentralized supply chains[END_REF]. In their model, the demand is sensitive to price and lead-time decisions and it is considered as deterministic. [START_REF] Kaminsky | Scheduling and due-date quotation in a make-to-order supply chain[END_REF] analyzed a make-to-order supply chains and design effective scheduling for the centralized and decentralized versions of those systems. They developed due date quotation model in the supply chain environment where it is affected by the performance of supplier. A problem with known average lead-time is studied by [START_REF] Zorzini | capacity planning in make-to-order companies: Results from an[END_REF]. They investigated a current practice supporting capacity and delivery lead-time management in the capital goods sector, and they proposed a model to formalize the decision process for set ting due dates in the selected cases. In two recent works, [START_REF] Steiner | Minimizing the weighted number of late jobs with batch setup times and delivery costs on a single machine[END_REF] addressed the minimization of the sum of the total weighted number of tardy jobs and delivery costs on a single machine based on the batch setup time for one customer, where they presented the optimal properties and a pseudo-polynomial time DP algorithm for obtaining the optimal solution. [START_REF] Steiner | Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries[END_REF] presented a pseudo-polynomial algorithm for minimizing the sum of the common due date assignment costs, the weighted number of tardy jobs, and the batch delivery costs for a single customer. Most recently, [START_REF] Rasti-Barzoki | A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs[END_REF] proposed heuristic and branch-and-bound algorithms for solving the problem of studied by [START_REF] Steiner | Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries[END_REF]. [START_REF] Rasti-Barzoki | A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs[END_REF] proposed studied multiple customers problem and proposed an integer programming method, a heuristic algorithm, and a branch-and-bound method. [Piya, 2015] proposed a method to quote the due date and the price of incoming orders to multiple customers simultaneously when the contingent orders exist. Their proposed method is based on two steps method to counter the uncertainty caused by contingent orders while preparing quotes for multiple new customers simultaneously.

The complexity of the problem of minimizing weighted number of early jobs on a simple supply chain is studied in different similar and convergent ways. [Karp, 1972] proved that the problem of minimizing weighted number of tardy jobs on a single machine is NP-hard in the ordinary sense even if all the jobs are subject to the same due dates. A survey of due-date-based research reveals that due dates are usually treated as given information and taken as input to a scheduling problem.

Chapter 2

State-of-the-Art However, actually to respond to customers needs, the due date can be a decision variable within the domain of the scheduling problem and according to different related variables could affected to the total cost as the delivery time, the delivery cost and the inventory cost.

Extended studied models

Although researchers have given a considerable attention on synchronization of the single-supplier single-customer integrated inventory system. Another major research direction extended the previous basic models in many different directions. The global supply chain can be very complex and link-by-link understanding of joint policies can be very useful [START_REF] Ben-Daya | The joint economic lot sizing problem: Review and extensions[END_REF].

A several authors have investigated the effect of the number of customers on the integrated problems. [Lu, 1995] developed a one-supplier multi-customer integrated inventory model, while [START_REF] Parija | Operations planning in a supply chain system with fixed-interval deliveries of finished goods to multiple customers[END_REF] extended their published work on single-supplier, single-customer, integrated production-inventory problems with lumpy delivery systems under perfect and imperfect production cycle situations. [Lu, 1995] argued that all the previous studies assumed that the supplier must know the customer's holding and ordering costs, which are quite difficult to estimate unless the customer is willing to reveal the true values. Therefore, the author considered another circumstance, in which the objective is to minimize the supplier's total cost per year, subject to the maximum cost that the customer may be prepared to incur. [START_REF] Parija | Operations planning in a supply chain system with fixed-interval deliveries of finished goods to multiple customers[END_REF] introduced the problem of determining the production start-time and proposed a method that determines the cycle length and raw material ordering frequency for a long-range planning horizon. The cycle-length is restricted to be an integer-multiple of all shipment intervals to the customers as an ideal situation, the solution to which may be sub-optimal. [START_REF] Viswanathan | Coordinating supply chain inventories through common replenishment epochs[END_REF] proposed a model to study and analyze the benefit of coordinating supply chain inventories by means of common replenishment epochs or time periods. A onesupplier multi-customer supply chain is considered for a single product. Under their strategies, the supplier specifies common replenishment periods and requires all customers to replenish only at pre-determined time periods. However, the authors did not include any inventory cost of the supplier in the model. In most papers dealing with integrated inventory models, the transportation cost is considered only as a part of fixed setup or replenishment cost. [START_REF] Ertogral | Production and shipment lot sizing in a vendor-buyer supply chain with transportation cost[END_REF] have studied how the results of incorporation of transportation cost into the model influence on better decision making under equal size shipment policies. A fundamental advance in the two-side cost structure is in recognizing how delivery-transportation costs apply to both sides. [Hoque, 2008] proposed three models for supplying a singleitem from a single-supplier to multiple customers under deterministic demand by synchronizing the production flow with equal-sized batch transfer in the first two and unequal-sized batches transfer in the third. In the first two models, all batches 2.5 The integrated Delivery-Inventory problems forwarded are of exactly the same size but the timing of their shipment is different. In the first assumption, the manufacturer transfers a batch to a customer as soon as its processing is finished, whereas in the second a batch is transferred to a customer as soon as the previously sent batch to the customer is finished. In the third model, the subsequent shipment lot sizes increase by the ratio of production rate and sum of demand rates on all the customers. [START_REF] Zavanella | A one-vendor multi-buyer integrated production-inventory model: The 'consignment stock'case[END_REF] proposed a model for a single-supplier multi-customer system, integrated in a shared management of the customer's inventory, so as to pursue a reduction or the stability of the holding costs while descending the chain. [Hoque, 2011a] transferred the lot from a supplier to multiple customers with l number of unequal sized batches first; where the next one is a multiple of the previous one by the ratio (k > 1) of the production and the total demand rates, followed by (n -l) number of equal sized batches. The equal sized batches are restricted to be less than or equal to the lth batch (the largest unequal sized batch) multiplied by k. The models developed were solved by applying Lagrangian Multiplier method. However, in cases of single-supplier single-customer or single-supplier multi-customer or multi-stage production, synchronization of the production flow by transferring the lot with equal and/or unequal sized batches was found to lead to the least total cost for some numerical problems. Although [Hoque, 2011a] served that purpose, it did not cope with the relaxation of the discussed impractical assumptions. Following this trend of synchronization, [START_REF] Hoque | An optimal solution technique to the singlevendor multi-buyer integrated inventory supply chain by incorporating some realistic factors[END_REF] developed two generalized single-supplier multicustomer integrated inventory models by accumulating the inventory at the supplier and customers independently, but with the traditional trend of ignoring the cost of benefit sharing. Transportation of each of the batches incurs a transportation cost.

In order to implement the models by taking into account the industry reality, he also incorporate them with the relaxation of the discussed impractical assumptions. [START_REF] Battini | Consignment stock inventory model in an integrated supply chain[END_REF]] developed a single supplier and multi-customer consignment stock inventory model in which many clients can establish a consignment stock inventory policy with the same supplier.

Recently, [START_REF] Jha | Single-vendor multi-buyer integrated production-inventory model with controllable lead time and service level constraints[END_REF]] studied an integrated single-supplier multi-customer model with lead time reduction under independent normally distributed demand on the customers. They assumed that non-identical lead time of the customers and the inventory at the customers is reviewed using continuous review policy. [START_REF] Hariga | A note on generalized single-vendor multi-buyer integrated inventory supply chain models with better synchronization[END_REF]] analyzed Hoque's models I and II studied in [Hoque, 2011a], then they modified some of Hoque's models. [START_REF] Hariga | A note on generalized single-vendor multi-buyer integrated inventory supply chain models with better synchronization[END_REF] compared the cost between the results of the models in [Hoque, 2011a] and [START_REF] Zavanella | A one-vendor multi-buyer integrated production-inventory model: The 'consignment stock'case[END_REF], then they concluded that both models are not appropriate as they are using different functional forms of the total setup and ordering costs. Moreover, it is shown that Hoque's model yields impractical solutions for zero transportation costs. When the total setup and ordering cost was adjusted to be similar the one in Zavanella and Zanoni's model, Hoque's model resulted in a larger total cost per unit time. [START_REF] Chiu | A single-producer multi-retailer integrated inventory system with scrap in production[END_REF]] studied a single-producer multi-retailer integrated inventory system with scrap in production. They considered all random defective items produced Chapter 2

State-of-the-Art as scrap items and a multi-shipment policy was used to synchronously deliver finished items to multiple retailers in order to satisfy customer demands. An optimal production lot-size and shipment policy that minimized the expected system costs was derived with the help of a mathematical model.

Problems with incompatible job families

Generally, jobs having identical processing times belong to the same family, and jobs in different families cannot be processed together in the same batch. A synchronization of production, delivery and inventory schedules for the incompatible jobs is therefore considerably more involved. The first models proposed for this problems examined each stage separately by neglected the others stages. The production setup costs are supposed negligible and shipments are supposed always made in full loads in the work of [START_REF] Maxwell | Coordination of production schedules with shipping schedules[END_REF]. The only costs affected by the production and transportation schedules in this case are inventory costs. They developed a method for minimizing total inventory costs. Since the early 1990s, an abundance of research has been done on the integrated problems with incompatible job families by taking into consideration more than one stage. [Uzsoy, 1995] studied a model with constant job sizes and proposed two different algorithm to solve the problem according to the release dates of the jobs. If the jobs are released at the same time, he provided exact polynomial time algorithms for the problems of minimizing make-span, total weighted completion time and maximum lateness on a single batch processing machine and heuristic algorithms for minimizing the above three objectives on parallel machines. When the jobs are subject to different release dates, he developed an exact polynomial time algorithm for the problem of minimizing makespan and a heuristic algorithm for the problem of minimizing maximum lateness.

Their system could discover rules that are structurally similar to and competitive with the batch-apparent-tardiness-cost rule proposed by [START_REF] Mehta | Minimizing total tardiness on a batch processing machine with incompatible job families[END_REF]].

In another work, [START_REF] Blumenfeld | Synchronizing production and transportation schedules[END_REF] studied a model with one supplier and multiple customers where the supplier produces multiple products, one for each customer. Each product is allowed to be produced multiple times within a production cycle. The authors studied the case of homogeneous products, where the production cycle time is an integer multiple of delivery cycle time. The delivery of multiple products to multiple customers was the motivation for research by (Hahm and Yano) in more than three works. First, they considered the one-supplier-onecustomer model in [START_REF] Hahm | The economic lot and delivery scheduling problem: the single item case[END_REF]. In this work, they assumed that the unit inventory holding cost at the supplier is the same as that at the customer. They formulated the problem as a nonlinear mixed integer program which is solved by a heuristic approach. In [Hahm and Yano a, 1995], they considered the multiple items case and a single shipment to deliver the products from the supplier to the assembler. Then, they relaxed the assumption set by [Hahm and Yano a, 1995] in [START_REF] Hahm | The economic lot and delivery scheduling problem: Models for nested schedules[END_REF], by allowed the multiple shipments through a production cycle which requires the multiple items to be partitioned into groups. Another policy 2.5 The integrated Delivery-Inventory problems of delivery is proposed in [Hahm and Yano c, 1995] differs from that proposed by [Hahm and Yano a, 1995], in which multiple equally spaced shipments take place at each cycle. The work of [Hahm and Yano a, 1995] was extended by [Khouja, 2000].

He considered the problems of determining the production scheduling and distribution intervals for different types of components when a supplier provides different kinds of components. He used a volume flexible where component quality depends on both lot sizes and unit production times of each items. Recently, [Khouja, 2003] examined production sequencing and distribution scheduling in a single-product and multi-product supply chain when production intervals equal distribution intervals. Most recently, [START_REF] Stecke | Production and transportation integration for a make-to-order manufacturing company with a committo-delivery business mode[END_REF] described a storage constrained, inbound inventory routing problem for incompatible jobs families. They explained the importance of the storage space on the routing and the inventory decisions. A variation of the multi-product version which also considers a system called (many-toone structure) was analyzed by [START_REF] Moin | An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem[END_REF]. They considered a finite horizon, multi-periods, multi-suppliers and multi-products where a fleet of capacitated homogeneous vehicles, housed at a depot, transport products from the suppliers to meet the demand specified by the assembly plant in each period. Similarly but with a many-to-many structure, [START_REF] Ramkumar | Mixed integer linear programming model for multi-commodity multi-depot inventory routing problem[END_REF] studied a multi-item multi-depot IRP, and they proposed a mixed integer linear program to solve this problem. They showed that the MILP is limited on time, since small instances with only two vehicles, two products, two suppliers, three customers and three periods could not be solved to optimal within eight hours of computing time. [Coelho et al., 2013] reviewed the problem of the incompatibles jobs families in an IRP with more focus given to the methodological aspects. Then in [Coelho and Laporte, 2013], they considered a multi-product multi-vehicle, where it deals with share inventory capacity and shared vehicle capacity for all products. They solved the problem using branch-and-cut and the implementation is able to solve instances with up to five products, five vehicles, three periods and 30 customers. In the most recent work, [START_REF] Coelho | Classification, models and exact algorithms for multi-compartment delivery problems[END_REF] studied a wide range of routing problems with several compartments used for the delivery of several products spanning several period. They developed two models, and they could solve instances containing up to 50 customers, four compartments and 14 vehicles.

Models with inventory routing problems

Some papers are devoted to the case with constant deterministic, customer specific, demand over an infinite time horizon. In their papers [START_REF] Anily And Federgruen ; Anily | One warehouse multiple retailer systems with vehicle routing costs[END_REF], [Anily and Federgruen, 1990a] and [Anily and Federgruen, 1991a]), they analyzed fixed partition policies for the inventory routing problem with constant deterministic demand rates and an unlimited number of vehicles. In [Anily and Federgruen, 1990a], they considered a class of general routing problems where the cost of driving a route depends both on its length and the number of points visited on the route via some general cost function having two arguments. The paper described a class of simple Chapter 2

State-of-the-Art heuristics of complexity O(nlogn) which are shown to be asymptotically accurate if the cost function satisfies certain conditions. Then in [START_REF] Anily And Federgruen ; Anily | One warehouse multiple retailer systems with vehicle routing costs[END_REF], they considered a distribution system with a depot and many geographically dispersed retailers each of which faces external demands occurring at constant, deterministic but retailer specific rates. in the objective of determining the feasible replenishment strategies (i.e., inventory rules and routing patterns) minimizing (infinite horizon) long-run average transportation and inventory costs. They restricted the problem to a class of strategies in which a collection of regions (sets of retailers) is specified. When one of the retailers in a given region receives a delivery, this delivery is made by a vehicle who visits all other outlets in the region as well (in an efficient route). They proposed a class of low complexity heuristics and a lower and upper bounds to solve the problem. Experimental studies showed that the proposed heuristics come close to the optimal solution even for problems of moderate size.

For further information, see also the comment by [Hall, 1991] and the rejoinder by [Anily and Federgruen, 1991a]. The analyses work in [START_REF] Anily And Federgruen ; Anily | One warehouse multiple retailer systems with vehicle routing costs[END_REF] was extended in [START_REF] Anily | Two-echelon distribution systems with vehicle routing costs and central inventories[END_REF], where the central depot also keeps an inventory. Here, the depot faces fixed ordering costs as well as inventory costs, and its replenishment strategy must be coordinated with the strategies of the customers.

For the same class of replenishment strategies as in [START_REF] Anily And Federgruen ; Anily | One warehouse multiple retailer systems with vehicle routing costs[END_REF] restricted to power-of-two structures, the proposed heuristic is almost asymptotically optimal. In a power-of-two-structure, the replenishment periods for all customers and the warehouse are power-of-two multiples of a base planning period, see [Roundy, 1985] for details on the power-of-two structure. In a later paper by [START_REF] Anily And Federgruen ; Anily | Structured partitioning problems[END_REF], details about calculating the lower bounds are described. Then in [Anily, 1994], she showed that the optimal solution can be bounded from below by a special partitioning problem whose solution can be given in closed form, and she proposed a simple heuristic in [Anily, 1994]. Recently, [START_REF] Anily | An asymptotic 98.5% effective lower bound on fixed partition policies for the inventory-routing problem[END_REF] derived lower bounds for the special case when a customer can only belong to one region. A probabilistic analysis of the performance of this bound demonstrates that it is asymptotically 98.5 % effective. [START_REF] Zhao | A partition approach to the inventory/routing problem[END_REF] focused on the integrated system with a warehouse responsible for the replenishment of a single item to the retailers with demands occurring at a specific constant rate, combining deliveries into efficient routes. They proposed a fixed partition policy for this type of problem, in which the replenishment interval of each of the retailer's partition region is accorded the power of two principles. To solve the problem, they proposed a lowed bound and they compared it to a tabu search algorithm. These results revealed the effectiveness of the policy as well as of the proposed algorithm. In another work, [START_REF] Raa | A practical solution approach for the cyclic inventory routing problem[END_REF]] assumed a deterministic constant customer demand rates and therefore, they adopted a long-term cyclical approach. Further, [START_REF] Raa | A practical solution approach for the cyclic inventory routing problem[END_REF] took into consideration the realistic side-constraints such as limited storage capacities, driving time restrictions and constant replenishment intervals. They proposed heuristic algorithm to solve the problem, which is analyzed and evaluated against a comparable state-of-the-art heuristic as [START_REF] Viswanathan | Integrating routing and inventory decisions in one-warehouse multiretailer multiproduct distribution systems[END_REF].

The Inventory-Routing Problem (IRP) is among one of the model types in the literature that are applied to this kind of problems. In such problems, distribution of a product(s) from a central location to multiple geographically dispersed customers using limited/unlimited number of capacitated vehicles is considered. The decisions to be made are (1) when to deliver to each customer, (2) how much to deliver to each customer at each time, and (3) how to serve customers using the vehicles [START_REF] Bertazzi | Inventory routing. In The vehicle routing problem: latest advances and new challenges[END_REF]. [START_REF] Bertazzi | A stochastic inventory routing problem with stock-out[END_REF] introduced the inventory routing problems with multiple customers in the case the demand of multiple customers has to be satisfied. They presented and discussed the basic problem of the IRP, where one vehicle only is available. Then, they considered the extension of this problem to the multi-vehicle case. Recently, an interesting work has been published in [Coelho et al., 2012a], [START_REF] Coelho | The inventory-routing problem with transshipment[END_REF] and [START_REF] Koc | A class of joint production and transportation planning problems under different delivery policies[END_REF], where in the first one, [Coelho et al., 2012a] introduced the concept of consistency in the Inventory-Routing Problem with Transshipment (IRPT) solutions. The multi-vehicle IRP, with and without consistency requirements, is formulated as a mixed integer linear program. A meta-heuristic, that applies an adaptive large neighborhood search scheme where some sub-problems are solved exactly, is implemented. These results showed that the problem is very difficult to solve exactly by the MIP model and the proposed heuristic can produce high quality solutions within reasonable computing times. They showed also the importance of the used of the transshipment, which allows to reduce the solution cost significantly on these instances, depending on the ratio between the unit transshipment cost and the cost of using the supplier's vehicle.

The case with transshipment is analyzed in [START_REF] Coelho | The inventory-routing problem with transshipment[END_REF] where an adaptive large neighborhood search heuristic is proposed. [START_REF] Koc | A class of joint production and transportation planning problems under different delivery policies[END_REF] analyzed the manufacturer's planning problem under different delivery policies and different types of orders. The orders can be split or consolidated, and two types of vehicles are considered. The first type of vehicle is expensive and available in unlimited numbers. The second type, which is less expensive, has limited and time-varying availability. In this work, the issue of multi-transporters and its importance are mentioned, however no resolution method has been proposed. [START_REF] Leung | Integrated production and distribution with fixed delivery departure dates[END_REF] fixed the delivery departure dates in the case of a single machine and a set of orders. The completed orders are then delivered to manufacturers by a finite number of vehicles. Three objectives are used. The first one is to minimize the worst-case delivery performance relative to the due dates. The second and third objectives go one step further by considering both the worst case delivery performance and the total transportation cost.

Conclusion

The state of the art briefly recalls the development of the supply chain management systems, starting from the representation of the lot-sizing and batch-scheduling problems with an overview of the single and multi-level models. Then, we reviewed the Chapter 2

State-of-the-Art integrated production-delivery-inventory problem and we cited the basic models and moving toward more advanced models. The rest of this state of the art focuses on the integrated delivery-inventory problem, where we reviewed the basic integrated models as the models with different shipment policies and the problems with due date objectives, moreover we cited numerous extensions of the integrated deliveryinventory models as the problems with incompatible job families and the models with inventory-rounting-problems. We showed that each study has its own weakness. Realistically, most of the problems are constrained, however our models are different from many existing models and it can be applied to a variety of real-world industrial problems.

There are very few researchers considered constraints mentioned above in the integrated production-delivery-inventory problems or in the integrated delivery-inventory problems one at a time. In our work, we present two different models. In the first one, a single-supplier/single-customer integrated supply chain model is presented as a production-delivery-inventory considerations, with multiple transporters and unequal due dates constraints; this model considers unequal batch size dependent on times and costs, transporter time and costs dependent by each transporter, a capacity constraint and a customer holding cost to each product arrive before its due date. In the second model, a single-supplier/multi-customer integrated model with unequal due dates constraints; this model considers a holding cost dependent by each customer, a transporter time and cost dependent also by customer, a capacity constraint, and the model is considered with unequal batch size. In our proposed models, the holding cost at the supplier could be higher or lower than at the customer; the transporter time and cost are considered different from a transporter to another; the transporter time and cost at the customers are different; the holding cost at the customers could be different from than other customers; the due dates related to each jobs could be equal or unequal from a job to another.

This work emphasizes the modeling and algorithmic development of optimization models for coordinated scheduling. Since most of the problems that we are dealing with high computational complexity. We focus on the development of efficient and effective heuristic algorithms for those problems, in the objective is to minimize the total cost in the supply chain, within the different constraints under assumption to guarantee a certain customer level. In each of the problems studied, we also conduct computational experiments to test the performance of our algorithms and discuss the insights obtained from the experimental results.

3 Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

Introduction

The expansion of supplier to accommodate the maximum number of customers is considered as a key factor in the evolution of companies, in order to increase their profits. Classical scheduling problems did not consider delivery costs, so considering the coordination between the delivery costs and scheduling objective to minimize the total cost is an important point that researchers have paid attention to recently. One important benefit of this coordination is a more efficient management of inventories across the entire supply chain. In traditional inventory management, the optimal production and shipment policies for vendor and customers in a two-echelon supply chain are managed independently. As a result, the optimal lot size for the customer may not result in an optimal policy for the vendor, and vice versa. To overcome this difficulty, the integrated vendor-customers model is developed, where the joint total relevant cost for the customer as well as the vendors is minimized. Consequently, determining the production and shipment policies based on integrated total cost function, rather than customer's or vendor's individual cost functions results in reduction of the total inventory cost of the system. The system under study in this chapter, is inspired from a distribution system of a local pharmaceutical industry.

In the pharmaceutical industry, contractors and generic manufacturers have been increasing their market share for the last decade and their competition advance relies largely on providing a fast response to their customers and being flexible in order to react quickly to changes in demand.

The increased competition has also forced other manufacturers in the same direction [START_REF] Stefansson | Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry[END_REF]. [START_REF] Aptel | Improving activities and decreasing costs of logistics in hospitals: a comparison of us and french hospitals[END_REF]] stated that management of pharmaceutical supplies is one of the most important managerial issues in health care industries. However, many health care industries experience difficulty in managing their distribution-inventory pharmaceutical products. It is thus important to improve production schedules in order to strive for minimizing the total deliveryinventory costs between the vendor and the customers in a pharmaceutical industry Chapter 3

Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery Scheduling Problem case.

Existing inventory models for multi-customers are not applicable to pharmaceutical products for several reasons. Pharmaceutical products can be more expensive than other products to purchase and distribute, and shortages and improper use of essential medicines can have a high cost in terms of wasted resources and preventable diseases and death. Therefore, special care should be taken in pharmaceutical inventory decisions to ensure 100% product availability at the right time, at the right cost, and in good condition to the right customers. The quality of health care industries strongly depends on the availability of pharmaceuticals on time. If a shortage occurs at a customer, an emergency delivery is necessary, which is very costly and can be implicated for patient health. Inventory management strategies that are unsuitable for health care industries may lead to large financial losses and a significant impact on patients. Hence, inventory strategies for pharmaceutical products are more critical than those for other products. Thus, a specific inventory model is necessary for control of pharmaceutical products to save patient lives and reduce unnecessary inventory costs.

In this chapter, we investigate a delivery-inventory supply-chain for multiple customers products in a customer. The studied system is composed of a central supplier which has to deserve products to different customers sites with a single transporter at given due dates. The objective is to reduce the overall cost which includes the delivery costs and an earliness penalty that is incurred for products which are delivered before their due dates. The problem studied in this chapter inspired from a real-world scheduling problem of a Central medical stores in the health systems.

The contributions in this chapter include enhancements to the batching and the delivery of batches of the central supplier in this context, which takes into account the different parameters related to the problem under study environment. Moreover, we propose an efficient genetic algorithm which is compared with a developed Branch and Bound algorithm and a Mixed Integer Programming model as an exact solutions. Two important advantages of this chapter should be emphasized. First, the resolution of real world scheduling problems helped to focus the research in the development of optimization models that can effectively be implemented. Second, although the scheduling models and solution approaches developed were motivated by a case-study, they can be applied to other types of industries, as long as the scheduling problem has a similar structure.

The rest of the chapter is organized as follows. In Section 2, the problem definition and the mathematical formulation is introduced, the notation used along this chapter are defined, then the problem is formulated as a mixed integer programming (MIP) model. In Section 3, we describe the proposed B&B algorithm as an exact method of resolution. In section 4 and 5, we developed an heuristic algorithm and a genetic algorithm for solving the problem, respectively. At last, in Sections 6 and 7, we provide the experimental results and draw some conclusions of this chapter.

Problem Definition and Mathematical Formulation

We consider a supply chain scheduling problem where there are m customers and one manufacture in which each customer h orders a finite number of heterogeneous jobs to the manufacture, {J 1 , J 2 , ..., J n }. The jobs have to be ready for delivery in batches by their common contracted due date for each job. In (Figure 3.1) a single supplier and multi-customer system has been depicted as an example. Each customer h orders a finite number of jobs to the supplier. There is a single transporter considered to deliver the products and each round trip between the supplier and a customer h requires a delivery cost η h as well as a delivery time τ h . The batches delivered from the supplier to the customers can be of different sizes. It is assumed that directing delivery method is used for sending the batches to the customers, which means that the jobs are transmitted to each customer separately [Chen, 2010]. The total number of jobs belonging to the same batch cannot exceed the capacity c of the transporter. Each job j has a due date d j specified by the customers and each job has to arrive to the customer site before its due date. If job j of customer h arrives before its due date d j , it will incur as an earliness penalty β h . Batching and sending several jobs in the batches will reduce the transportation costs. The objective is to determine the sequence of batches that has to be processed, such that the expected total cost of both supplier and customers sites is minimized.

Notations

The following notations are used in developing the mathematical model:

Parameters

• J = 1, 2, ..., n: set of all jobs, where n is the total number of jobs,

• H = 1, 2, ..., m: set of all customers,

• j: index for jobs, j ∈ J, Chapter 3

Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

• k: index for batches,

• h: index for customers,h ∈ H,

• d j : due date of the job j,

• cl j : destination of the job j,

• c : capacity of the transporter,

• τ h : time for the vehicle to deliver a batch to customer h and to return to the supplier location,

• η h : delivery cost to deliver a batch to customer h and to return to the supplier location,

• β h : customer earliness penalty function for customer h,

Primary variables

• δ 1 jk = 1 if the job j belongs to the k th batch, 0 otherwise, • δ 2 kh = 1 if the batch k belongs to the customer h, 0 otherwise, Secondary variables

• y k = 1 if the batch k exists and is not empty, 0 otherwise,

• C j : the arrival time of job j at the customer,

• B k : the arrival time of the batch k at the customer,

• B δ jk ≥ 0 : the result of B k × δ 1 jk , • k: index for batches, k ∈ K,
• K = 1, 2, ..., u: set of all batches, where u is the total number of batches,

• u h : number of delivered batches for customer h,

Mixed Integer Programming Model

In this research, the integrated model is developed for delivery and inventory policies. The first term aims to calculate the total delivery cost for n delivered products through η h u h . The second term calculates the inventory costs for all jobs arrived before their due dates through β cl j (d j -C j ). The objective function in equation (Equation 3.1) attempts to minimize the total cost of the system under study.

The supply chain has many aspects that need to be considered in a supply chain model. However, by taking all concerned factors into account, the model would be of so high complexity that it would be extremely hard for analysis. In this section, the mathematical programming model of the above mentioned problem is presented.

Problem Definition and Mathematical Formulation

Using the structural properties, we develop a MIP model for the mentioned problem as follows:

M in Z = m h=1 η h u h + n j=1 β cl j (d j -C j ) (3.1)
Subject to :

n k=1 δ 1 jk = 1, j = 1, . . . , n (3.2) m h=1 δ 2 kh ≤ 1, k = 1, . . . , n (3.3) δ 2 k,cl j ≥ δ 1 jk , j, k = 1, . . . , n and k ≤ j (3.4) u h = n k=1 δ 2 kh , h = 1, .., m (3.5) y k ≥ y k+1 , k = 1, ..., n -1 (3.6) n j=k δ 1 jk ≤ c, k = 1, . . . , n (3.7) C j ≤ d j , j = 1, . . . , n (3.8) B k+1 ≥ B k , k 1 , k 2 ∈ J 2 and k 1 < k 2 (3.9) B k+1 -B k ≥ m h=1 τ h (δ 2 k+1,h + δ 2 kh ), k = 1...n -1 and h ∈ H (3.10)
Chapter 3

Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

C j = n k=1 B k × δ 1 jk , j = 1, .., n (3.11) C j ≥ 0, j = 1, 2, . . . , n (3.12) δ 1 jk , δ 2 kh ∈ {0, 1}, j, k = 1, .., n and h = 1, .., m (3.13)
The objective function (Equation 3.1) minimizes the sum of delivery and customers inventory cost. Constraint (Equation 3.2) guarantees that, each job must be scheduled exactly in one batch, in this constraint the jobs will be batched only in the batch which it belongs. Constraints (Equation 3.3 and Equation 3.4) indicate that, each batch must be scheduled exactly to one customer, in this constraint the batches will be delivered only to the customer which it belongs. Constraint (Equation 3.5) calculates the number of batches delivered to each customer. Constraint (Equation 3.6) guarantees that no empty batch is allowed. Constraint (Equation 3.7) prevents the number of jobs scheduled in one delivery batch to exceed the capacity of the vehicle. Constraint (Equation 3.8) indicates that arrival time of each job is at least equal to the contracted due date for each customer. Constraint (Equation 3.9) arranges the arrival time of batches by order. Constraint (Equation 3.10) shows the relation between the arrival time of two consecutive batches and the delivery time which their belong, to prevents the overlap between two consecutive batches in the case of two consecutive jobs delivered separately to two different customers. Constraint (Equation 3.11) represents the conversion of the completion time of the products that belong to the same batch C j to B k the arrival time of each batch to the customers. This constraint is represented in a non-linear way in this mathematical representation to facilitate the understanding of the problem. Constraints (Equation 3.12) and (Equation 3.13) define the range of the variables.

For ease of reference, we denote this problem: Multiple Customers Lot Sizing Delivery Scheduling Problem (MCLSDSP).

The complexity of the MCLSDSP is still an open question. To the best of our knowledge, no polynomial algorithm can solve this problem. However from simulation experiments, we observe that the problem is still intractable on an empirical basis. In the next section, a Branch-and-Bound (B&B) algorithm with a lower bound is described to solve the problem as an exact method.

Branch and Bound Algorithm

In this section, we describe the B&B algorithm that we have developed to solve the MCLSDSP. The objective of this B&B is to solve small and medium instances, 3.3 Branch and Bound Algorithm and to be a reference for validating the efficiency of the proposed heuristic algorithms. This B&B algorithm maintains a list of sub-problems (nodes) whose union of feasible solutions contains all feasible solutions of the original problem. The list is initialized with the original problem itself. In each major iteration, the algorithm selects a current sub-problem from the list of unevaluated nodes. This branching seems to be natural, however the number of branches will be very large for large problems. Consequently, if this method is used in the B&B algorithm, it may take too much time to find optimal solutions, as redundant schedules would be checked repeatedly. Yet, several of the sub-problems would already have been eliminated upon the generation of nodes, since the B&B tree includes redundant solutions.

At each node of the search tree, the number of products that still needs to be delivered to each customer has to be updated. Iterations are performed until the list of sub-problems to be processed is empty. The crucial part of a successful B&B algorithm is the computation of the lower bounds. Therefore, we have developed a lower bound described in the next part.

Efficient lower bound would significantly reduce the time and efforts needed for the B&B method. Based on the main feature of the problem, the lower bound value for the problem is the summation of lower bounds on the total earliness cost and the transportation cost. We assume that w is a partial batch sequence solution, z(w) is the evaluation of w, and r h (w) is the number of products remaining at the customer h for partial solution w. This notation will be used throughout this part.

In each node, the solutions are built from the last batch to the first one and the evaluation of the partial or complete solution is processed with backward equations.

The research of a solution starts by constructing a partial solution w. Then, the remainder of products is added in order to get a complete solution, with the objective of achieving a minimum delivery cost. Therefore, the more the transporter will be loaded, the more this lower bound will be efficient.

Proposition 1 For a partial solution w, a lower bound for the delivery cost of the remaining products is given by:

m h=1 r h c × η h (3.14)
Proof. For each customer h, if r h (w) is the number of products remaining to be delivered, the number of round trips will be equal to r h c , and the delivery cost of the remaining products is as denoted in equation (Equation 3.14).

We add the partial solution w to the solution found in equation (Equation 3.14) to get the lower bound of the current node under study.

Corollary 1

The lower bound LB(w) of the partial solution w is given as follows:

LB(w) = z(w) + m h=1 r h c × η h (3.15)
Chapter 3

Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

Proof. Straightforward.

The mathematical model and the B&B algorithm developed in the previous sections could solve the small and medium size instances, however the time of resolution to solve the large size instances grows exponentially (demonstrated later, in section 6.3). Therefore, developing fast heuristics to yield near-optimal solutions in a reasonable running time is still of great importance. In the next section, a solving method is proposed to solve the problem and to study its performances.

Heuristic Algorithm

In this section, we proposed an efficient heuristic algorithm to solve the multicustomer lot-sizing and delivery-scheduling problem. This procedure is a heuristic, and therefore does not capture all solutions, possibly including the optimal solution to the problem. The proposed algorithm is divided on two i defines the lot sizes and then schedules these batches according to the due dates of the jobs. This heuristic will be denoted Lot Sizing and Scheduling algorithm (LSS) and will have the same operational characteristics assumed in the development of the proposed exact methods of the MCLSDSP.

The LSS algorithm starts by generating an initial solution through the means of a progressive constructive procedure. Then, it applies the above-mentioned two-steps process until a predefined stop condition is satisfied. At first, some elements of the current solution are constructed. Then, a local improvement phase based on a swap operator is applied to the reconstructed solution in order to improve its quality. Finally, LSS chooses the optimum solution between the current solution and the solution obtained from the improvement procedure.

Based on the prune rule, the following heuristic is proposed: lets denote that (x; cl j ; C j ) the notation which will be used for a solution of one batch, where the first term x describes the number of jobs in this batch, the second term cl j describes the customers destination and the third term C j is the arrival time of the product at the customer to which it belongs. For level 0, there are no jobs. For the first level (includes only one job), there is only one possible joint solution which is (1;

cl n ; C n ).
For level k (includes k jobs), all the "good solutions" for a number of k jobs will be kept. The process to build the "good solutions" for level k is described as follows: (1) build delivery-inventory solutions of level k by considering all the delivery-inventory solutions in the retained" good solutions" of all the previous levels from 1 to (k -1).

For each retained solution of level k ≤ k, a new solution of level k is built by simply adding a batch of (k -k ) jobs, if this is possible. Then, repeat this procedure until the level n is considered.

The details of the Algorithm (Algorithm 3.1) are presented as follows: The generation of the initial solution and the construction procedure is represented from lines 1

3.4 Heuristic Algorithm to 4. Then, the size of batches procedure is represented from lines 5 to 17 according a scattering/gathering procedure. The improvement procedure is named in line 14, then it is described in Algorithm Algorithm 3. The lot sizing procedure, performed in an iterative way, extends a partial solution by adding one job from a set J of all jobs. The construction of the good solution advances progressively and in a hierarchical manner. The process starts from the last job and arrives recursively to the first one. The jobs are distributed to the customers to whom they belong, and the batches sizes are defined according to a scattering/gathering procedure described in Algorithm Algorithm 3.1.

In this algorithm, the number of delivered jobs j varies from 0 to n (line 1). For each level of j delivered jobs, the different partial solutions are built from the solution of previous levels (<j). Moreover, the necessary number of batches to these solutions is added, to complete the partial solution of level j. After every product addition to level j, the partial solution of this level is completed by adding the necessary delivery scheme to the considered solution in the list of all kept solutions from 0 to (j -1), to obtain the new list of solutions of level j. A test of verification of the capacity of the transporter used is done directly after each advancement in level (See line 6 in Algorithm Algorithm 3.1). This destruction procedure leads to a list of solutions for level j. The final step of each level j is denoted in line 15, which is mentioned in Algorithm Algorithm 3.1. In this phase the good solution is memorized and inscribed to level j. After that, a new level (j + 1, j + 2...) is started till reaching level n. Each solution in level j is improved according to a swap operator that is described by Algorithm Algorithm 3.2.

In this operator, all consecutive batches are swapped, by starting from the last batch recursively to the first one, while the index of batch is positive (See line 6 in Algorithm Algorithm 3.2). After every swap operation, the new solution is kept, if it is better than the current. If not, a new swap operation is generated. The improvement operation stops, when the index of batches equals 0.

Let's take an example to explain the application of the LSS algorithm, to illustrate the MCLSDSP. We consider a problem of three jobs and two customers. The due dates associated with these jobs equal to 1000, 1100, 1150, where jobs 1 and 3 belong to customer 1 and job 2 belongs to customer 2. The transporter delivery cost and time depend upon the customer's location with (η 1 = 20, τ 1 = 60 u.t and η 2 = 15, τ 2 = 40 u.t) belonging to customer 1 and 2 respectively. The storage costs at the customers are set to be (β cl 1 = β cl 3 = 30 and β cl 2 = 15 ), belonging to customer 1 and 2 respectively. The LSS process is described in detail as follows: The process starts by the last job recursively to arrive to the first one.

1. Set n = 1. For j = {3}, there is only one possible joint solution which it

(1, cl 1 -1150).

2. Set n = 2. For j = {3, 2}, there are different possible solutions. Firstly a complementary solution is built by simply adding a batch of (2-1) job to the previous delivery solution. We provide in the next section a genetic algorithm started by the solutions found in the heuristic algorithm proposed above, in the objective is to improve the results of the approach method of resolution which could help us to solve large instances.

Genetic Algorithm

A genetic algorithm (GA) is a heuristic search algorithm that resembles natural selection. This algorithm was invented by [Holland, 1975] and developed and applied to different areas [Goldberg, 1989]. As the name suggested, GA is an evolutionary algorithm inspired by reproductive biology. As the name suggested, GA is an evolutionary algorithm inspired by reproductive biology. Genetic algorithms, when applied to scheduling, view sequences or schedules as individuals or members of a population. Each individual is characterized by its fitness. The fitness of an individual is measured by the associated value of the objective function. The procedure works iteratively, and each iteration is referred to as a generation. The population of one generation consists of survivors from the previous generation plus the new schedules, i.e., the offspring (children) of the previous generation. The population size usually remains constant from one generation to the next. The offspring is generated through reproduction and mutation of individuals that were part of the previous generation (the parents). Individuals are sometimes also referred to as chromosomes. The use of genetic algorithms has its advantages and disadvantages.

One advantage is that they can be applied to a problem without having to know much about the structural properties of the problem. They can be very easily coded and they often give fairly good solutions.

Chapter 3

Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

Gene Representation

A genetic algorithm, as a search process, differs in one important aspect from other algorithms. At each iterative step a number of different schedules are generated and carried over to the next step. In other algorithms only a single schedule is carried over from one iteration to the next. Hence those algorithms may be regarded as special cases of genetic algorithms with a population size that is equal to 1. This diversification scheme is an important characteristic of genetic algorithms. In genetic algorithms the neighborhood concept is also not based on a single schedule, but rather on multiple schedules. The design of the neighborhood of the current population of schedules is therefore based on more general techniques than those used in other algorithms. A new schedule can be generated by combining parts of different schedules from the current population. A mechanism that creates such a new schedule is often referred to as a crossover operator.

There is numerous coding methods to represent the solutions of a genetic algorithm. In our case, a solution is a list of batches (and jobs composing batches) the transporter will deliver to precise customers in a determine order. For example the chromosome ((1,c1),(3,c3),(2,c1),(3,c2)) represent the solution of 4 batches : first 1 jobs are delivered to customer 1 then 3 jobs are delivered to customers 2 and so on. To code this form of solution, we use the number coding method; which is the most commonly used coding method. Each chromosome is a list of numbers which formed groups (called genes) of identical strictly positive integers and represent the number of jobs containing in a batch and the customers which will be delivered. Every batch is separate by a 0 to easily identifies the different genes. For instance, the previous example may be represent by the chromosome of Table 3.1.

1 0 3 3 3 0 1 1 0 2 2 2 Table 3.1: A chromosome representing a solution

Detailed algorithm

The algorithm we use is detailed in Figure 3.2. We start by creating a population of random individuals then use the crossover operator on some of them then mutating them depending of a dynamic mutation probability which is randomly chosen every twenty cycles. The best solution of the current population are determine then use to begin another cycle and create a new population until a chosen time limit or maximum cycles number is reached.

After deciding on an encoding, the second decision to make in using a genetic algorithm is how to perform selection-that is, how to choose the individuals in the population that will create offspring for the next generation, and how many offspring Scheduling Problem randomly choose, with replacement, two chromosomes as "parents".

Crossover

This operator randomly chooses a locus and exchanges the sub-sequences before and after that locus between two chromosomes to create two offspring. It could be said that the main distinguishing feature of a GA is the use of crossover. Single-point crossover is the simplest form: a single crossover position is chosen at random and the parts of two parents after the crossover position are exchanged to form two offspring. The idea here is, of course, to recombine building blocks (schema) on different strings. Single-point crossover has some shortcomings, though. For one thing, it cannot combine all possible schema. Likewise, schema with long defining lengths are likely to be destroyed under single-point crossover. In this work, The crossover is a linear order that intends to preserve relative positions of the genes, and work on a sub-sequence level of each chromosome to preserve a good batch sub-sequence. We decide to switch some parts of two solutions (parents) to obtain two new solutions (children). Two sub-sequences of the same length are randomly chosen in each chromosome and then switched. This method cannot guarantee the legality of the new born solutions which may be discard if necessary.

Table 3.2 shows the details of a crossover between two solutions then the resulting children. After selecting two parents, a random value is generated to determine whether the crossover process has to be performed.

parent 1 1 0 3 3 3 0 1 1 0 2 2 2 parent 2 2 0 3 3 0 2 2 2 0 1 1 1 After the crossover, the two offsprings are obtained as follows:

child 1 1 0 3 3 3 0 3 3 0 2 2 2 child 2 2 0 1 1 0 2 2 2 0 1 1 1 Table 3.2: The two parents crossover operator

Mutation

Here, we defined a mutation operators, the purpose of this kind of operators is to ensure the non-stagnation of the solutions in a local extreme by randomly modifying a chromosome without considering another one. In case of every chromosomes convergence through a unique solution, two randomly chosen chromosomes may be quite identical and the crossover operator will create two children similar to their parents. 58 3.6 Experimental results the mutation operator is needed to explore other solutions and ensure the solutions legitimacy. A common view in the GA community, dating back to [Holland, 1975] book Adaptation in Natural and Artificial Systems, is that crossover is the major instrument of variation and innovation in GAs, with mutation insuring the population against permanent fixation at any particular locus and thus playing more of a background role. This differs from the traditional positions of other evolutionary computation methods, such as evolutionary programming and early versions of evolution strategies, in which random mutation is the only source of variation. However, the appreciation of the role of mutation is growing as the GA community attempts to understand how GAs solve complex problems. Some comparative studies have been performed on the power of mutation versus crossover; for example, [START_REF] Spears | An overview of evolutionary computation[END_REF] formally verified the intuitive idea that, while mutation and crossover have the same ability for "disruption" of existing schema, crossover is a more robust "constructor" of new schema.

In this study, we use three mutation operators which are defined as follows.

• A swap operator which works to swap two randomly selected couples of batches and their corresponding customers of one solution.

• A split mutation operator, which aims to divide a randomly selected batch of one solution into two separate batches with the same customer.

• A fusion operator, which works to merge two successive batches of one solution of a supply link into one new batch. The corresponding customer is chosen among the two customers of the initial batches.

New Population and stopping criterion

A complete cycle of the selection, crossover and mutation operations forms an iteration. Once the offspring is reproduced, it is stored in a temporary population. Until all the offspring have been reproduced, the "offspring population" is then combined with the latest population to form two new populations. The new chromosomes are compared according to their fitness values. The chromosomes with hight total cost are eliminated and the remaining chromosomes form the next generation. The GA is then performed again until the stopping criterion is reached. The stopping criterion for the problem is either when number of iterations are completed.

Experimental results

In this section, a set of problems taken from the supplier data with different sizes are used for this study. The computational experiments are carried out to test the performance of the B&B, LSS algorithm, Genetic algorithm and the results of the MIP model.

Test cases

The characteristics of orders to schedule differ by customers, transporter capacity, quantity delivered, due date, transporter time, transporter cost and the storage cost at each customer. Three cases are considered to test the proposed methods. The characteristics of the case are listed in Table 3.6.2. For each case {A, B and C}, the number of products n, number of customers h, the transporter time, the transporter cost and the storage cost at each customer are displayed. In the first class, η h is higher than β h , where η h and β h are randomly generated from the uniform distribution with ranges [1000, 1500] and [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF], respectively. In the second class, η h are generated in the same way and with the same distribution with ranges [1000, 1500] and β h of the first class are multiplied by 10, where β h are randomly generated from the uniform distribution with ranges [10,50]. In the third class, β h is calculated by multiplying the ranges of the first class by 100, where β h are randomly generated from the uniform distribution with ranges [100, 500] Euro. The results can be seen in (Table 3.5, Table 3.6, Table 3.7 andTable 3.8). In the computational study, the following parameters are used: the vehicle's capacity is randomly generated from the uniform distribution with range [n/5, 2n/5], further, its round-trip delivery time for each customer are randomly generated from the uniform distribution with range [3,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF] Moreover, for each case, the number of jobs set as 10, 20, 30 and 40, and the number of customers as 2, 3 and 4 for each case.

Comparison of the computational time of solutions

The parameters are generated with a magnitude order which is consistent with those of the supplier. For each combination, 25 problem instances are randomly generated and the average cpu time for each method of resolution are collected. The results show that heuristic algorithm runs much faster than the exact methods of resolution. For the exact methods, the B&B algorithm which is supported by the lower bound to accelerate the proposed algorithm runs faster than the CPLEX solver. The CPLEX solver finds the optimal solution, however its computational time grows exponentially as the instance size increases in the same class. Conversely, the resolution of the B&B algorithm is acceptable, which explains the efficiency of the lower bound used in the B&B algorithm to give the optimal solution for small to medium size instances. The computational time of the proposed LSS will never exceed 0.3 second. Moreover, the LSS can obtain optimal or near optimal solutions for all of the situations.

Class of Class A Problem→

In Table 3.5, the results show that it was possible to solve all the instances with the three proposed methods. In this case, the total storage cost at the customer n j=1 β cl j (d j -C j ), which constitutes the second part from the objective function (Equation 3.1), will be less than those of the total transporter cost m h=1 η h u h , which 62 3.6 Experimental results 3.1). In this case, the problem is very easy to solve, because the vehicle is fully loaded according to the cheapness of the storage cost at the customer.

Class of Class B Problem→

(h)→ 2 3 4 (n)↓ CpuT (s)
In Table 3.6, the problem becomes harder to solve with CPLEX onset from 30 products on regardless of the number of customers. However, the time of resolution of the B&B algorithm exceeds the proposed time limit onset from 4 customers if the number of products equals to 30, and onset from 3 customers when the number of products equals to 40. In this case, the number of batches is increased and the number of products by batch is decreased.

In the third class of problem, in Table 3.7, the efficiency of CPLEX decreases, where the MIP model solves only the instances of 10 products with 2, 3 and 4 customers. However, the B&B solves the same instances as in Table 3.6, but its processing time grows progressively when the number of customers and products increase. In this case, the vehicle is very lightly loaded. Clearly, more the instances will be larger, more they will be harder to solve.

These results show that the proposed B&B algorithm is more efficient than the MIP model, and the LSS proposed algorithm gives an optimal or near optimal solutions for small to large size instances.

Comparison of the quality of solutions

In this section, the performance of the proposed LSS heuristic algorithm and Genetic algorithm are analyzed thoroughly, by comparing these results with the performance of the proposed exact methods. In the first time, we will compare the results of the proposed heuristic algorithm with the results of the fast exact method found above which is the B&B algorithm. Then, we will study the performance of our GA which starts by LSS heuristic algorithm as an initial algorithm.

The three considered cases are found in (Table 3.8). For each case, three scenarios are considered beginning with two customers in use, then three and four. Moreover, for each case, the number of products sets as 10, 20, 30 and 40 respectively. In each case, the customer storage cost β h is generated from a discrete uniform distribution in the interval [1, 5], [10, 50] and [100, 500] Euro for the three classes, respectively.

In the computational study, the following parameters are used: the vehicle's capacity is randomly generated from the uniform distribution with range [n/5, 2n/5], further, its round-trip delivery time for each customer are randomly generated from the uniform distribution with range [3,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF] hours. The due dates (d j ) j=1..n are uniformly separated with values randomly generated. 64 3.6 Experimental results

Heuristic algorithm performance

Considering the different parameters, 36 situations of the problem are tested. For each situation, 25 problem instances are generated to study the performance of the LSS. Based on the results of the exact methods, the error ratio is defined as ER(LSS/Exact)=(E LSS -E Exact )/E Exact , where E LSS denotes the average of the evaluation of the solution generated by the proposed LSS, and E Exact denotes the average of the evaluation of the solution generated by exact methods. The results are displayed in Table 3.8.

Class of

The 3.8 shows clearly that the overall average equals to 5.82% which demonstrates that the proposed LSS is capable of generating near-optimal solutions within a reasonable amount of CPU time. One of the reasons may be the improvement phase which is presented in the approach method presented in section 4. As seen in each case, the average error ratios appear in an increasing trend as the value of n increases.

Genetic algorithm performance

In order to evaluate the performance of the proposed GA, we compare these results with the performance of the B&B algorithm. We used the same instances as above with three scenarios beginning with two customers in use, then three and four. After the comparison between the results of the proposed LSS algorithm as initial solution of the GA, we have compared the results found by the GA with the results of the B&B algorithm. We used the same method of evaluation to evaluate our developed GA, where we calculate the error ratio between the GA and the B&B algorithm. The error ratio between the solution found by LSS algorithm and the B&B algorithm is defined as ER=(E GA -E B&B )/E B&B , where E GA denotes the average of the evaluation of the initial solution generated by the developed GA, and E B&B denotes the average of the evaluation of the proposed Branch and Bound.

According to Table 3.9 for the ER of the different cases (A, B and C), the results confirms the optimal solution obtained by the GA heuristic, within a reasonable amount of CPU time. Compared with the results found by LSS in Table 3.8, the GA still performs better than the LSS. GA is capable of obtaining an optimal solution compared to the LSS for the tested instances, and requires far less computational time compared to the proposed B&B algorithm. Therefore, the GA heuristic developed in this chapter is capable of validating the quality of the solutions obtained from other methods of resolution that attempt to solve this king of supply chain optimization problems.

Conclusion

In this chapter we have studied the case of a single supplier sourcing a products at multiple heterogeneous customers. To reduce storage and transportation costs, the transporter serves every customer separately. Further, it is assumed that jobs are first processed in the production stage, and then gathered in batches and delivered to the customer to which it belongs. The resource of products is a number of available machines that produce according to a multi-customer command. Each job has a due date specified by the customers. Moreover, it was supposed that a job that arrives at the customer before its due date will incur a customer inventory cost. We proposed two methods of resolution and two heuristic algorithms. We have first proposed a MIP model and developed a B&B algorithm as exact methods. Then, we have developed a simple heuristic algorithm and showed that the relative error ratio of the heuristic solution is important and it needs to improvement. We have further developed a more sophisticated genetic algorithm with a better solutions more the first heuristic algorithm. Our computational study not only shows that the improved genetic algorithm is effective in practice but also shows that it can provide a substantial optimal results in a few time of resolution.

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

Introduction

In many make-to-order businesses, the production only takes place after customers place their orders. Under such a circumstance, coordinating production with transportation and inventory can become challenging, especially when the related facilities possess very limited resources. The coordination between the supplier and the customer for improving the performance of inventory control has received a great deal of attention and the integrated approach has been studied for years. Typically, the integrated approach focuses on the production-delivery-inventory decisions of supply chain partners while minimizing the total relevant cost of the system. The delivery method used plays a role in resolving the problem, such as the number of transporters used, the capacity of each transporter and the size of each batch. Due to the number of decision variables to be determined, the integrated production and distribution planning problem is so complex that optimal values are very hard to obtain.

In this chapter we investigate a variant of the lot sizing and batch scheduling problem with delivery time and cost dependent on batch size. This delivery and inventory scheduling problem based on finite number of heterogeneous or homogeneous vehicles. In particular, we address a model with more than one transporter, in which a number n of jobs are produced and delivered in un-equal sized batches. In the first time, the supplier received an order of n jobs. When the production of one batch at the supplier's end is finished, the products are loaded in a chosen transporter capacity. In order to do so, we have to assume that the supplier has enough production resources represented by a multi-machine, and that the delivery sequence of batches is the same as the production one. The round trip cost increases with the augmentation of the size of the batch and the capacity of the transporter. The setup time between any two batches is not considered because all the jobs are identical. The customer will demand a specific date for the arrival of each product. Therefore to satisfy this requirement and to minimize the related costs, the different Chapter 4

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem products have to be gathered in batches before being transported. The aggregation of products will lead to the need for storage, which would mean storage cost for both the supplier and the customer. The computation of the production/delivery date is processed by backward equation [START_REF] Elmahi | A modelling-optimization approach for discrete event systems using the (max,+) algebra and genetic algorithms[END_REF]. It is a method where lot-sizing and scheduling is done chronologically backwards. The objectives of the study in this chapter are:

• To study the behavior of each parameters of the problem under study.

• To find optimal cost.

• To find optimal batch size with the respect of the different constraints.

• To find optimal batch number related to each transporter.

• To find best policy to reduce total system cost.

As far as we know, the assumption of a batch-size-dependent delivery times and costs in order to take into account the loading and the unloading times of the transporters, in a single-supplier/single-customer with multiple vehicles configuration has not been studied till now. This assumption is one of the distinguishing features of the work presented in this chapter. The second distinguishing feature is to propose an exact resolution method based on a dominance property, which is very efficient in the identical transporters case and to compare the corresponding results to a mixedinteger-programming model solved by CPLEX and an approach method consists of an efficient genetic algorithm.

For ease of reference, we denote this problem: the Multi-Transporter Lot Sizing and Delivery Scheduling Problem (MT-LSDSP). The complexity of the (MT-LSDSP)

is still an open question. To the best of our knowledge, no polynomial algorithm can solve this problem. However from simulation experiments, we observe that the problem is still intractable on an empirical basis. The given mathematical model is non linear as the delivery time of a batch depends on its size.

The rest of the chapter is organized as follows. In Section 2, the problem description is introduced, the notation used along this chapter are defined, then a definition of the studied problem is given and an illustrative example is given. The mathematical model is formulated and analyzed. In Section 3, mathematical analyses are established where the first one is a dominance relation in general case and the second one is a specific dominance relation for the identical transporters case. We then introduce in section 4 a dynamic programming approach and we formulate the problem as a mixed integer programing (MIP) model as an exact methods for solving the problem, and a genetic algorithm is developed as an approach method. Finally, in Sections 5 and 6, we provide the experimental results and draw some conclusions of this chapter.

Problem description

In this section the formulation of the operational model is presented to illustrate the assumptions production, delivery and inventory policies. This work is based on some notations are first defined, then the problem definition is represented, and an illustrative example is represented and a mathematical formulation is proposed.

Notations

Parameters

• J = 1, 2, ..., n: set of all jobs, where n is the total number of jobs,

• H = 1, 2, ..., m: set of all transporters, where m is the total number of transporters,

• j: index for jobs, j ∈ J,

• h: index for transporters, h ∈ H,

• d j : due date of the job j,

• c h : capacity of the vehicle h,

• τ h,b : delivery time of the vehicle h to deliver a batch of size b. Denote that, τ h,0 is the return time of the empty transporter h from the manufacturer to the subcontractor,

• η h : round-trip delivery cost of the transporter h,

• α h : sum of the subcontractor holding and delivery costs when using the transporter h. The α h functions are assumed to be non-decreasing functions,

• β j : manufacturer earliness penalty function for job j. The β j functions are assumed to be non-increasing functions,

Primary variables

• σ k : size of production and delivery batch k,

• h k : the transporter which is assigned to deliver the batch k,

Secondary variables

• K = 1, 2, ..., u: set of all batches, where u is the total number of batches,

• k: index for batches, k ∈ K

• u h : number of delivered batches for transporter h, u = m h=1 u h • C j : the arrival time of job j at the manufacturer,

• B k : the arrival time of the batch k at the manufacturer,

• k σ = k k=1 σ k , k σ = k σ -σ k + 1 : index of

Problem definition

The studied model in this chapter aims to study an integrated problem for job scheduling and batching wherein different inventory holding, costs between the supplier and the customer are allowed. There are n identical jobs j to be processed on a facility of multi-machines available at the subcontractor. Each job j (numbered j = 1, 2, ..., n) has a due date d j specified by the manufacturer. It is not allowed to any job to arrive after its due date, however if the job j arrives before its due date, it will incur an earliness penalty cost. The jobs are batch processed at the subcontractor with no setup time between any two batches. Moreover, each job needs a constant processing time, however we assume that the total production time of any batch is less than the minimum round-trip delivery time for the transporters. After the processing of a batch is completed, the products are delivered to the manufacturer in different batch sizes by an available vehicle. We define a delivery-batch as a group of jobs that are delivered together in one shipment. Each transporter h has a given capacity c h , a round-trip delivery cost η h and for each batch size b, a round trip delivery time τ h,b which includes the loading and unloading phase of the products, where the delivery cost and time dependent on batch sizes. It is supposed that each job j that arrives before its due date will incur an earliness penalty (or storage cost) β j , which is a non-decreasing function, according to the assumption of [Baptiste, 2000].

The sequence of the delivery batches that has to be processed and the schedule of the transporters that have to be used, have to satisfy the total manufacturer demand and need to minimize the global cost of the system. In the section an illustrative example is shown to explain in more details the considered system, then a mathematical formulation of the problem is proposed.

Illustrative Example

Here, an example is given to explain the considered problem with 100 jobs and two different transporters whose main characteristics are as follows. For the first transporter (resp. 2nd transporter), the capacity c h is 20 (resp. 15) ; the delivery time τ h,b is given between 40 when the transporter is empty and 110 when it is fully loaded (resp. between 35 and 89) and the delivery cost η h is 80 (resp. 60). We remark that the first transporter is more , but slower, than the second one.

In Figure 4.1, the gantt chart draws the activity of the different processes involved in the system, that is to say the manufacturing and delivery processes for the 2 transporters, depending on the time parameter. Moreover the due dates of the products have been represented at the top of the axe of the resources, in order to understand the relationship between the delivery dates of the different batches and their corresponding due dates. For the solution represented in Figure 4.1, 8 batches have been scheduled, 3 of which are delivered by the first transporter and the 5

Mathematical Formulation and Dominance property

The considered problem consists of determining the sequence of batches, as well as specifying the transporter that has to deliver the parts from the subcontractor to the manufacturer.

The elements of the model's profit are the subcontractor production storage cost, the delivery cost of each batch and the earliness penalty at the manufacturer. Each element has its special internal constraints which are affected by the due dates imposed by the manufacturer. We assume that there are no waiting time between the end of the production of a batch and the starting date of its delivery, which is possible in a just-in-time context with enough production machines. Consequently, the subcontractor WIP holding cost will depend only on the batch size and can thus be included with the delivery costs of the corresponding delivery batch. These both costs are represented by a non-decreasing function α h that depends on the size of the batch. However products need to be delivered at the latest possible dates in order to reduce the manufacturer earliness penalties, which rely on the arrival time C j , the due date d j , and the earliness penalty function β j .

The WIP holding time incurs an inventory cost that will depends on the batch size. The total WIP holding cost and delivery cost is represented in equation (Equation 4.1) as follows:

m h=1 u k=1 α h (σ k ) (4.1)
On the other hand, the products have to arrive at the manufacturer at the latest possible dates with respect to the due date initially imposed. The holding cost of the customer will be formulated as follows:

n j=1 β j (C j ) (4.2)
Consequently, the objective function is the sum of the delivery cost (Equation 4.1) and the holding cost (Equation 4.2) defined in the following expression:

f (σ) = m h=1 u k=1 α h (σ k ) + n j=1 β j (C j ) (4.3)
subject to :

4.3 Mathematical Formulation and Dominance property

1 σ k c h k , k = 1, ..., u (4.4) u k=1 σ k = n, k = 1, ..., u (4.5) k σ = k k=1 σ k , k = 1, ..., u (4.6) C j d j , j = 1, ..., n (4.7) C j C j+1 , j = 1, ..., n -1 (4.8) C j = C k k = 1, ..., u, j = k , ..., k (4.9) C k 2 -C k 1 ≥ (τ h k 2 ,0 + τ h k 2 ,σ k 2 ), k 1 , k 2 = 1, ..., n; k 1 < k 2 and h k 1 = h k 2 (4.10)
The objective function (Equation 4.3) minimizes the sum of delivery costs between the manufacturer and the subcontractor, and the storage cost on each side. Constraint (Equation 4.4) guarantees that the number of jobs scheduled in one delivery batch cannot exceed the capacity of the vehicle. Constraint (Equation 4.5) defines the total number of production jobs. Constraint (Equation 4.6) indicates the accumulation of jobs by each batch. Constraints (Equation 4.7) and (Equation 4.8) guarantee that each job must arrive at the manufacturer on time and by order. Constraint (Equation 4.9) defines that the arrival time of jobs for a given batch are identical. Constraint (Equation 4.10) maintains the time intervals between the arrival of two batches delivered by the same transporter to be greater or equal to the round-trip delivery time of the transporter for the second batch.

In the next subsection, we propose a general dominance relationship which will be used to accelerate the resolution of the problem. Then, the specific case when all the transporters share the same characteristics (capacity, delivery time and cost) is studied and an improved dominance relationship is highlighted between the solutions of the new problem.

General case

We define a partial solution where the number of delivered jobs is less than n jobs. A partial solution is not a complete solution, simply because its number of delivered Chapter 4

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem jobs is less than the total number of jobs requested by the manufacturer. The number of transporters used to deliver a sequence of batches for a partial solution could be less or more than that of a complete solution. In the same way, the number of the round trips done on a partial solution could be less or more than that of a complete solution.

We introduce now a general dominance relation among the partial solutions. We denote u σ (resp. u ω ) the final number of batches that will be delivered for a partial solution σ (resp. ω).

Theorem 1. Let σ and ω be two partial solutions with σ = ω. σ dominates ω if the two sequences satisfy the following properties :

∃ k 1 , Q = u σ k=k 1 σ k = u ω k=k 1 ω k (4.11) m h=1 u σ k=k 1 α h (σ k ) + n j=j 1 β j (d j -C σ j ) ≤ m h=1 u ω k=k 1 α h (ω k ) + n j=j 1 β j (d j -C ω j ) (4.12) ∀k ≥ k 1 , B σ k -τ h k ,σ k ≥ min   min k ≥k 1 /h σ k =h ω k B ω k -τ h k ,ω k , +∞   (4.13)
with j 1 first job in the partial solution:

j 1 = n -Q + 1.
Proof. Suppose that the complete solution ω * satisfies (Equation 4.11), (Equation 4.12) and (Equation 4.13), and that is not dominated by any solution that derives from σ. Now consider the complete solution σ that derives from σ as follows:

σ k = ω * k , 1 ≤ k < k 1 σ k = σ k , k 1 ≤ k ≤ u σ (4.14)
For the new solution σ , the number of new batches equals k 1 -1 which is the same as the batches that have been added to ω * . Moreover, the production holding cost for these batches will be the same for σ and ω * . From this, the equation (Equation 4.12) can be rewritten as: From the manufacturer point of view, we consider a batch ω * k with k < k 1 . This batch is the same as the batch σ k . The completion time of the job inside this batch will depend on the corresponding due dates, which are the same, and will depend on the next departure time of the same transporter h k . The equation (Equation 4.13) shows that for a given transporter h, the departure date of this transporter for the partial solution σ, and consequently σ , is always delayed than the earliest departure date of the same transporter for the partial solution ω. Consequently, the arrival time of the jobs from the first batch to the batch k 1 -1 for the solution σ are delayed than those of the solution ω * . It follows that :

m h=1 j 1 -1 k=1 α h (σ k ) ≤ m h=1 j 1 -1 k=1 α h (ω * k ) (4.15)
j 1 -1 j=1 β j (d j -C σ j ) ≤ j 1 -1 j=1 β j (d j -C ω * j ) (4.16)
The sum of the three expressions (Equation 4.12, Equation 4.15 and Equation 4.16) leads to: F (σ ) ≤ F (ω * ). Thus, the initial assumption is false, which concludes the proof.

This proposition means that the best batch sequence solution obtained from the partial solution σ is better than the best batch sequence solution obtained from the partial solution ω.

To illustrate this proposition, let's consider the 2 partial solutions σ and ω in the Figure 4.3 with 2 transporters A and B. The number of delivered jobs is 70 for the two partial solutions. If the total partial cost of σ is less than that of ω, then σ dominates ω, because for all batches, the minimum starting delivery time for transporters A and B is later for σ than for ω.

Lemma 2. Consider 2 partial solutions σ and ω with the same number of delivered parts, and the set of transporters that is affected to σ is a subset of the set of transporters that is affected to ω.

Chapter 4

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem σ dominates ω if the partial evaluation of σ is better than those of ω, and for each transporter h used for σ, the first delivery starting date of h for σ is scheduled after the first delivery starting date of the same transporter h for ω.

Proof. This is a direct consequence of theorem 1.

In the theorem 1, we establish a dominance relationship for single supply link situation between two partial solutions with the same number of delivered jobs.

Identical transporters case

In the case of homogeneous transporters, every transporter can be exchanged with another one. Consequently, the dominance relationship of theorem 1 may be adapted to the identical transporters case, at the first glance, when two solutions have the same number of transporters used. More precisely, if a solution ω has less transporter used than another solution σ, then no dominance can exist because the unused transporter of solution ω could be planned as late as possible and it is not guaranteed that a transporter already used for solution σ could be planned in the same way. Consequently, the manufacturer holding cost for solution σ could be higher than those for solution ω.

To introduce the dominance relationship in the case of a homogeneous fleet of transporters, we introduce ν i the index for the i th transporter used in the considered solution, without taking into account the case where the same transporter is used more than once. For solution σ, the first transporter used is C, then A is used for the second delivery and finally B is used. In this case, ν 1 (σ) = C, ν 2 (σ) = A and ν 3 (σ) = B. For the solution ω, the first batch is delivered by A and the second batch is delivered by B, so we have ν 1 (ω) = A and ν 2 (ω) = B. The third batch is delivered by B but B has already been used for the second batch. We consider then the 4 th batch that is delivered by transporter A which has already been used ; so the final batch is treated, which is delivered by C, and this gives :

ν 3 (ω) = C.
The delivery dates of the transporters for solution σ and ω can be compared in the order given by the ν function. We observe that the transporter ν 1 (σ) for σ starts its delivery after the first delivery of the transporter ν 1 (ω) for ω. In the same way, the earliest starting time of the transporter ν 2 (σ) (resp. ν 3 (σ)) for σ is later than the earliest starting time of the transporter ν 2 (ω) (resp. ν 3 (ω)) for ω. If moreover, the current evaluation of solution σ is better than the current evaluation of solution ω, then solution σ dominates solution ω. The creation of the same new batch in the beginning of both solutions will incur a greater manufacturer holding cost for solution ω than for solution σ, which mean the new solution of σ dominates that of ω.

Theorem 3. Let consider the homogeneous transporter case and let σ and ω be two partial solutions with σ = ω. σ dominates ω if the two sequences satisfy the following constraint :

∀ i ∈ [1, m] , min k/h σ k =ν σ i (B σ k -τ ν σ i ,σ k ) ≥ min k/h ω k =ν ω i (B ω k -τ ν ω i ,ω k ) (4.17)
with the constraints (Equation 4.11) and (Equation 4.12) of theorem ( 1).

Proof. Based on the same principle used on the general dominance relation section 3.4, we will prove the dominance relation of the identical transporter case. If a sequence of batches is added for a given transporter h 1 for the solution ω, this sequence can be added to the transporter h 2 for σ such as h 1 (resp. h 2 ) is the i th transporter used for ω (resp. σ). This is equivalent to say, that: ∃i,

ν ω i = h 1 and ν σ i = h 2 .
The overhead of this sequence of batches for ω will be greater than that for σ because the corresponding transporter start later for solution σ than for solution ω. This means that the finishing time C σ j for the jobs inside that sequence of batch will be greater than the corresponding C ω j for ω. Therefore, the storage cost of the sequence solution σ for the manufacturer will be less than that of the sequence solution ω, which concludes the proof.

The case where all the transporters share the same parameters is a restriction of the MT-LSDSP in the general case. However, the resolution of this particular problem Chapter 4

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem has an important application, as it can provide both a lower and an upper bound for the optimal value of a general problem. In fact, let consider P a MT-LSDSP with m transporters, if we consider the new problem P min (resp. P max ), which derives from P , and for which the capacities of the transporters is the maximum (resp. minimum) of the capacities of the transporters of P ; the delivery times of the transporters is the minimum (resp. maximum) of the delivery times of the transporters of P and the delivery costs of the transporters is the minimum (resp. maximum) of the delivery costs of the transporters of P , then the optimal solution obtained for P min (resp. P max ) is a lower bound (resp. upper bound) of the optimal solution of P .

In the next section, two solving methods that will be proposed to resolve the problem.

Solving methods

To solve the problem, we propose in this section a dynamic programming algorithm based on the dominance procedure to optimally solve the problem. In order, to validate the proposed model the general model will be linearized to built a mixed integer programming model.

Dynamic programming approach

Dynamic programming is a powerful optimization technique applicable to many complex problems requiring a sequence of interrelated decisions. Currently, dynamic optimization techniques have become an essential part of modern control theory, systems designs and operations, such as the design of the aircraft, the operation of a reservoir system and multi objectives routing problems see [START_REF] Li | Multiobjective dynamicprogramming-the state-of-the-art[END_REF]].

The main advantages of the dynamic programming formulation are, first, an optimal solutions found rather than near optimal solutions, second, the formulation permits general cost functions for each stage in the network. As a consequence, we propose a generalized dynamic programming scheme, named GDP , to build the optimal solutions starting from a single delivered part and ending with all the delivered parts (see algorithm Algorithm 4.1). Each level k will be composed of the dominant solutions for a number k of delivered parts. The dominated solutions will not be retained as they will lead to worse evaluations than the dominant ones. The process to build all the dominant solutions for level k consists on considering the retained solutions of all previous levels from level 1, to level k -1. For each retained solution of level k < k, a new solution of level k is built by simply adding a batch of k -k parts for each transporter h. With this procedure, the number of possible solutions for level k will grow very quickly, as this is the sum of all the dominant solutions of the previous levels. To reduce the size of this set of solutions, the dominance criteria is applied among the population, in such a way that the dominated solutions of that level are removed. After reaching level n, the solution with the minimal evaluation is the optimal solution of the considered problem.

This procedure allows to find the optimal solution in the general case with heterogeneous transporters and a delivery time that is batch-size dependent. However, the experimental results show that the dominance relationship does not reduce efficiently the number of dominant solutions, and consequently, the processing time of the GDP grows very quickly when the number of jobs or the number of transporters increases.

Chapter 4

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

The Mixed Integer Programming Model

We have assumed for the MT-LSDSP general model, that the delivery time of the transporters were batch-size dependent. Therefore, the corresponding mathematical model is not linear. In order to build a linear MIP model, this assumption has to be relaxed and the delivery times for a given transporter has to be considered as fixed, which of course produces a problem less complex to solve. By using a MIP model and by solving it with CPLEX, we will measure the performances of the proposed algorithms in the case where the delivery times of the transporters are constant.

In the following, we formulate our problem as a mixed-integer programming model. This model is used to determine resource deployment, given a logistics structure.

In practice, such a tool is useful for evaluating and supporting strategic decision making. Furthermore, firms using such a model would most likely have an existing logistics structure, making variable-fixing an appropriate action. Before the model is presented, new parameters and variables, which are used in the MIP model, are described below.

Parameters

• τ h : round trip delivery time of the vehicle h to deliver a batch,

• β j : the unit holding cost for job j in the manufacturer area

• c max = max h=1..m
(c h ) : the maximum capacity of the transporters

• ξ j = E( j-1 cmax ) + 1 : the minimum batch number for job j taking into account the maximum capacity of the transporters.

Primary variables

• y k = 1 if the batch k exists and is not empty, 0 otherwise,

• δ 1 jk = 1 if the job j belongs to the k th batch, 0 otherwise,

• δ 2 kh = 1 if the batch k is delivered by the transporter h, 0 otherwise, With the notations mentioned above, the mixed integer programming model is proposed as follows:

M in Z = m h=1 η h u h + n j=1 β j (d j -C j ) (4.18) Subject to: 82 4.4 Solving methods j k=ξ j δ 1 jk = 1 j = 1, .., n (4.19) m h=1 δ 2 kh = y k k = 1, .., n (4.20) y k ≥ y k+1 k = 1, ..., n -1 (4.21) u h = n k=1 δ 2 kh h = 1, .., m (4.22) n j=k δ 1 jk m h=1 c h × δ 2 kh k = 1, .., n (4.23) C j d j j = 1, .., n (4.24) B k 1 ≤ B k 2 k 1 , k 2 ∈ J 2 ; k 1 < k 2 (4.25) C j = j k=ξ j B k × δ 1 jk j = 1, .., n; (4.26) B k 2 -B k 1 m h =1 2τ h δ 2 k 1 h -(2 -(δ 2 k 1 h + δ 2 k 2 h ))M k 1 , k 2 ∈ J 2 ; k 1 < k 2 ; h ∈ H (4.27) δ 1 jk δ 1 j+1,k + δ 1 j+1,k+1 j, k = 1, .., n -1; k ≤ j (4.28) δ 1 jk , δ 2 kh ∈ {0, 1} j, k = 1, .., n ; h = 1, .., m (4.29)
The objective function (Equation 4.18) minimizes the sum of delivery and manufacturer inventory cost. Constraint (Equation 4.19) guarantees that, each job must be scheduled exactly in one batch, in this constraint the jobs will be batched only in the batch which it belongs. Constraint (Equation 4.21) assures that no empty batch allowed during the resolution of the problem. Constraint (Equation 4.20) forces every batch to be delivered using one transporter only. Constraint (Equation 4.22) calculates the number of batches delivered by each transporter. Constraint (Equation 4.23) guarantees that the number of jobs scheduled in one delivery batch cannot exceed the capacity of the vehicle to which it belongs. Constraint (Equation 4.24) and Chapter 4

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem (Equation 4.25) guarantees that each job must arrive at the manufacturer by order and on time. Constraint (Equation 4.26) represents the conversion of the completion time of the products belong to the same batch C j to B k the arrival time of each batch to the manufacturer. This constraint represented in a non-linear way in this mathematical representation to facilitate the understanding of the problem. Constraints (Equation 4.27) prevent the overlap between two consecutive batches in the case of two consecutive jobs delivered separately by the same transporter. Constraint (Equation 4.28) indicates that two consecutive jobs j and j + 1 will either be in the same batch or be in consecutive batches. Constraints (Equation 4.29) define the range of the variables.

The performance of the both exact methods will me compared to a developed genetic algorithm, introduced and represented in the next section.

Genetic Algorithm

Introduction

The exact methods are a methods these examine the search space completely with an add proposed by the developer as the dominance relation proposed in our work.

In addition, at each search step only the solution concerned with the dominance relation are allowed to minimize the search space. This may cause some concerns for the time of resolution of the large instances tested. Genetic algorithm (GA) is a general, robust, and well developed optimization method. As a global optimization method, genetic algorithm has been used successfully to find optimal or near-optimal solutions for a wide variety of optimization problems, Genetic Algorithms (GAs) was invented by [Holland, 1975] who developed this idea in his book "Adaptation in natural and artificial systems". Holland proposed GA as a heuristic method based on "Survival of the fittest". A flowchart of a simple GA is illustrated in Figure 4.5. In a genetic algorithm, a population of strings (called chromosomes or the genotype of the genome), which encode candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem, evolve; towards better solutions. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations have been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has been terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached [START_REF] Jat | A guided search genetic algorithm for the university course timetabling problem[END_REF]. [Wang, 2012] used the (GA) to reduce the problem of the Integrated Scheduling of Production Distribution-Inventory problems (ISPDI).

Evolving the population

A GA evolves a population by means of selection, crossover, and mutation, etc. When the evolution terminates, the chromosome with the best fitness represents the optimal solution of the optimization problem. This is the major part of a GA, and is an iterative procedure with each iteration containing the following steps:

• Evaluation the population Decode each chromosome and evaluate its fitness (function value). For each chromosome, a rate allocation problem is solved and the optimal objective function value is assigned as the fitness of the corresponding chromosome.

• Genetic Operators

The current generation of the population is modified through selection, crossover, mutation, and other operations to produce the next generation of population.

Selection

In the selection steps, we replicate chromosomes for mating. This study implements a tournament selection, in which a mating chromosome randomly picked two chromosomes from the current population, and the one with higher fitness value is selected as the mating chromosome. Repeat this procedure until n mating chromosomes are selected.

Crossover

In the crossover step, we introduce two-points crossover operator based on the characteristics of the scheduling problem. This crossover is a linear order crossover that intends to preserve relative positions of the genes, and works on a sub-sequence level of each chromosome. The function of this crossover is to preserve a good batch subsequence. For this two-point crossover operator, we have introduced an appropriate linear coding in order to represent every batch delivered by a transporter t with a sequence of genes whose length is the corresponding batch size and of value t. Moreover two consecutive batches are separated with a gene whose value is 0 . For example in (Table 4.2), we consider a problem with 10 products and 3 transporters. Parent1 equals (2, t 1 ), (3, t 2 ), (4, t 1 ), (1, t 1 ), therefore its coding begins with 2 (the size of batch 1) genes whose value is 1 (transporter t 1 ), then continue with a '0' and a sequence of 3 genes whose value is 2 (3 jobs delivered by t 2 for batch 2), and so on.

For this crossover operator, two sub-sequences of same length are determined randomly for both parents. The children are then created by exchanging these two sub-sequences except the 0' values; these are not exchanged in order to keep the legality of the solutions. For example, the two-point crossover of parent1 and parent2 will generate two children (Table 4.2).

Mutation

parent 1 1 1 0 2 2 2 0 1 1 1 1 0 1 parent 2 3 3 3 0 2 2 0 3 3 0 1 1 0 2 child 1 1 1 0 3 3 2 0 1 1 1 1 0 1 child 2 3 3 3 0 2 2 0 2 2 0 1 1 0 2 Table 4.2: The crossover operator

Mutation is used to produce small perturbations on chromosomes to promote diversity of the population. There are several mutation operators such as swapping, inversion, insertion and shift mutation (see [START_REF] Cheng | Genetic algorithms and engineering design[END_REF]). In this study, three mutation operators are defined as follows :

• A swap operator which works to swap two randomly selected couples of batches and their corresponding transporters of one solution.

• A split mutation operator, which aims to divide a randomly selected batch of one solution into two separate batches with the same transporter.

• A fusion operator, which works to merge two successive batches of one solution of a supply link into one new batch. The corresponding transporter is chosen among the two transporters of the initial batches.

Elitism

In this study, the "roulette wheel of reserving elites" method is adopted. This selection scheme allows chromosomes to be selected for the next generation through a probability that is directly proportionate to their fitness. A maximum of two chromosomes are chosen randomly based on these scheme [Goldberg, 1989].

We provide in the next section the experimental results obtained with the dynamic programming, the mixed integer programming model and the genetic algorithm and we analyze them.

Experimental and Computational results

In this section, we evaluate the computational performance of the three techniques of resolution used to solve the problem under study: the proposed genetic algorithm, the proposed dynamic programming procedures and the mixed integer programming model solved by CPLEX, through 1650 test cases randomly generated, with respect to various parameter settings. Two different cases proposed for the evaluation of the problem, where the first one is the general case with heterogeneous transporter and the second one is the case with identical transporters. The performance of Chapter 4

Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem GA was measured by the average error gap compared to the fast exact method (which is the developed GDP in this study), and was defined as ER(GA/GDP ) = 100 * (GA-GDP )/GDP where GA denotes the best evaluation found by the genetic algorithm and GDP stands for the optimal value found by the dynamic programming method. The performance of the proposed GDP procedure was measured by its CPU time needed to find the optimal solutions and was compared with that by the CPLEX solver that solves the MIP model directly. Both the GDP procedure and the GA were programmed in JAVA language and implemented through a desktop Intel core 2 processor operating at 2.67 GHz clock speed and 4 GB RAM. The maximum solving time allowed for this instances is one hour. The MIP model is solved by CPLEX on the same machine.

Instances with Heterogeneous Transporters

Three classes of problems are considered so that in the first class the total transporter cost is bigger than the total manufacturer storage cost, this case is denoted as A in (Table 4.3). In the second class which is denoted as B in (Table 4.4), the total transporter cost is almost equal to the total customer storage cost. In the third class which is denoted as C in (Table 4.5), the storage cost is less than that of the total transporter cost. For each class, three scenarios are considered, beginning with two transporters in use, then three transporters and finally four transporters. Moreover, for each case, the number of jobs equals 10, 20 and 30, respectively. For each scenario, the vehicles's capacity are randomly generated from the uniform distribution with range [n/3, 2n/3], further, its round-trip delivery time of each transporter is randomly generated from the uniform distribution with range [20,100].

The due dates (d j ) j=1..n are uniformly distributed over an horizon [0, 50.n]. The transporters cost η h are randomly generated from the uniform distribution with ranges [100,250]. The storage cost at the customer's varies in every case, where β is randomly generated from the uniform distribution with ranges [0.01, 0.05], [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF] and [10,50] in the three different cases A, B and C, respectively.

The results of the CPLEX solver and the GDP procedure are shown in (Table 4.3, Table 4.4 and Table 4.5). The results show that the GDP runs much faster than the solution proposed by the MIP model. The CPLEX solver which used to solve the MIP model finds the optimal solution, however its computational time grows exponentially as the instance size increases, regardless of the parameters of the studied problem. In contrast, our proposed GDP is influenced by the value of the parameters used and the increase of the complexity of the problem. With a small and medium instances, the computational time of the proposed GDP will never exceed one hour. Moreover, the GDP can obtain the optimal solutions for all the situations.

For the problem of the class A in finds the optimal solution but its computational time grows rapidly as the instance size and the number of vehicles increases. Conversely, the computational time of the GDP is very short, which explains the efficiency of the dominance relation used in the GDP method to give the optimal solution from small to medium-sized instances.

In this case, the two methods solve the problem rapidly for the parameters used.

In these experiments, the optimal solution corresponds to fully loaded vehicles. In this case, the total holding cost at the customer is less than those of the total transporters cost. Consequently, this configuration is the least complex to solve, because the vehicles have to be fully loaded in order to minimize the delivery cost. In the second class of the problem B in Table 4.4, the problem becomes harder to solve with CPLEX onset from 30 products regardless of the number of transporters. Our GDP runs faster than the CPLEX solver but the gap between the two methods becomes significantly prominent as the number of products and transporters increases. In this case, the time of resolution of the CPLEX solver starts to increase rapidly according to the variation of β in [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF]. In the optimal solution, we noticed that the number of batches is increased and the number of products by batch is decreased gradually.

Class of CPLEX

GDP CPLEX GDP CPLEX GDP Problem↓ CpuT (s) CpuT (s) CpuT (s) CpuT (s) CpuT (s) CpuT (s) Size(n)→
In the third class of the problem C in Table 4.5, we observe that the GDP runs much faster than the CPLEX solver when the number of products is more than 10 products. Interestingly, The efficiency of CPLEX decreases enormously, where the MIP model solves only the instances of 10 products with 2, 3 and 4 vehicles. In this [10,50] case, the computational time of the two methods becomes very large so that the variation of β equals to [10,50], where in the optimal solution the vehicles are very lightly loaded, but our proposed GDP is still more efficient than the results of the MIP model. These results show the efficiency of the proposed GDP method to give the optimal solution from small to medium-sized instances. Now, we analyzed the performances of the dynamic programming and the genetic algorithm for the heterogeneous transporters instances. The aim of these experiments is to show the efficiency of the GA compared to the GDP . Several classes of problem have been considered for which several instances have been generated with different number of jobs and transporters. Three classes (1, 2 and 3) of problems are considered and the results are denoted in Table 4.6. For each class, three scenarios are considered, beginning with two transporters in use, then three transporters and finally four transporters. Moreover, for each case, the number of jobs equals 10, 20 and 30, respectively. For each scenario, the vehicles's capacity are randomly generated from the uniform distribution with range [n/3, 2n/3], further, its round-trip delivery time of each transporter is randomly generated from the uniform distribution with range [20,100]. The due dates (d j ) j=1..n are uniformly distributed over an horizon [0, 50.n]. The transporters cost η h are randomly generated from the uniform distribution with ranges [100,250]. The storage cost at the customer's varies in every case, where β is randomly generated from the uniform distribution with ranges [0.01, 0.05], [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF] and [10,50] in the three different cases 1, 2 and 3, respectively.

The parameters of the GA are summarized as follows:

• Population size : 500

• Termination condition: 500 iterations or fitness of the best individual did not change for a certain number of generations

• Mutation probability : 0.1

• Crossover probability : 0.6 Table 4.6 report on the performance of solution approaches of both method of resolution, the proposed GDP algorithm and the GA, under the impact of three parameters: n, m, β. As we can see, the GA demonstrated a promising performance with the largest average error ratio less than 5%, in the first and second cases, where β equal to [0.01, 0.05] and [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF], respectively. In the third case, the average error ration increase significantly and consistently as the number of products and the number of transporters increase. This is because the problem becomes more complicated to solve, if the number of products by batch is more restrictive.

Instances with Homogeneous Transporters

The performance of the dominance relation in the identical transporters case has been evaluated thoroughly. Here all the transporters are identical in capacity, round trip time and cost.

Three cases are considered, similar to what was done in the heterogeneous transporters, these three cases (A, B and C) are found in (Table 4.7), respectively. For each case, three scenarios are considered beginning with two transporters in use, then three and four. Moreover, for each case, the number of jobs is 10, 20 and 30 respectively.

For each scenario, the vehicles's capacity are randomly generated from the uniform distribution with range [n/3, 2n/3], further, its round-trip delivery time of each transporter is randomly generated from the uniform distribution with range [20,100]. Concerning the computational time of resolution, the proposed GDPid is often much more efficient than the proposed MIP model. Especially, in the complex case when the number of transporters are more than three and the number of products become large. For instance in the third case of problem in (Table 4.7) when β = [10, 50] (case C) and the number of products equal to 30 with 4 transporters, the time of resolution of our GDPid is still efficient and it does not exceed one minute, while CPLEX needs more than one hour.

Compared with the results found in (Table 4.3,Table 4.4 and Table 4.5), the proposed GDPid is faster than that of the GDP and its time of resolution is not expelled in the same pace according to the increase of the number of products or transporters. After the comparison of the Computational Results of the GDPid algorithm and the MIP model, we analyzed the performances of the dynamic programming with the identical transporters case and the genetic algorithm. The aim of these experiments is to show the efficiency of the GA compared to the GDPid . Several classes of problem have been considered for which several instances have been generated with different number of jobs and transporters. Three classes (1, 2 and 3) of problems are considered and the results are denoted in Table 4.8. For each class, three scenarios are considered, beginning with two transporters in use, then three transporters and finally four transporters. Moreover, for each case, the number of jobs equals 10, 20 and 30, respectively. For each instance, the vehicles's capacity are the same and it is randomly generated from the uniform distribution with range [n/3, 2n/3]. Further, the round-trip delivery time of each transporter is the same in each instance and it is randomly generated from the uniform distribution with range [20,100]. The due dates (d j ) j=1..n are uniformly distributed over an horizon [0, 50.n]. The transporters cost η h is the same for all the transporters in the same instances, and it is randomly generated from the uniform distribution with ranges [100,250]. The storage cost at the customer's β is randomly generated from the uniform distribution with ranges [0.01, 0.05], [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF] and [10,50] in the three different cases 1, 2 and 3, respectively.

The parameters of the GA are summarized as follows:

• Population size : 500

• Termination condition: 500 iterations or fitness of the best individual did not change for a certain number of generations

• Mutation probability : 0.1

• Crossover probability : 0.6 Table 4.8 report on the performance of solution approaches of both method of resolution, the proposed GDPid algorithm and the GA. As we can see, the GA demonstrated a promising performance with the largest average error ratio less than 1.5%, in the first and second cases, where β equal to [0.01, 0.05] and [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF], respectively. In the third case, the average error ratio increase significantly and consistently as the number of products and the number of transporters increase, but it does not exceed 15.11%. In the third case, the problem becomes more complicated to solve, where the number of products by batch is more restrictive. Compared with the quality of results in the heterogeneous transporters cases, the GA demonstrate an efficient performance with a maximum average error ratio less than to 15.11%.

Large instances with Homogeneous Transporters

To test the performance of the GDPid with a large instance, we conducted experiments using random instances with large problem sizes. We decided to study the case B considered in ( Comparison of the quality of the solutions found by the GA and the GDPid three and finally four. In (Table 4.9), only the performance of the GDPid is studied. the results show that, GDPid is able to solve the problem of this large instance with a reasonable time despite the increase in the number of products or transporters. However, the resolution time of the problem increases significantly according to the increase in the number of products, and the number of transporters.

Class of

Conclusion

In this chapter we investigate an Integrated Batch Production and Distribution Problem. In particular, we address a Multi-Transporter Lot Sizing and Delivery Scheduling Problem, where in a supply chain environment involving a fleet of heterogeneous or homogeneous transporters with batch-size-dependent delivery time and cost. The objective is to find a joint schedule in order to minimize the total delivery and inventory cost.

The problem is formulated as a non-linear model in a general way. We analyze several properties of the problem, which lead to dominance property for the general case when transporters are heterogeneous. This dominance property is enhanced in the identical transporters case. Based on these dominant properties, a dynamic programming algorithm has been proposed and compared with CPLEX in the case where the delivery time is not batch-size dependent, which allows to have a linear model. In the objective of solving large instances, we have developed an Improved Genetic Algorithm as an approach method to solve the problem. Each method of resolution have been evaluated computationally and the performance of the fast exact method of resolution has been compared with the developed GA.

The computational results show that the dynamic programming approach with heterogeneous transporters is much more efficient than CPLEX for solving small and medium-sized instances. The GA has been evaluated with the GDP , where the error ratio between the GA and the GDP demonstrate that the efficiency of the GA decreases significantly when the storage cost at the customerβ increase, where the problem becomes more complicated to solve.

In the case of identical transporters, the results show that the proposed dominance relation reduces more drastically the time of resolution compared with the proposed MIP model solved by Cplex. The time of resolution of this method does not exceed 36.00 seconds in the most complicated case where n = 30, m = 4 and β is randomly generated from the uniform distribution with ranges [10,50].

The study presented in this chapter may be extended in several directions. First, improving the efficiency of the proposed dynamic programming method in the general case, although it is already an efficient method, in order to solve larger problem instances. For that purpose, it is possible to use a lower bound by solving a similar problem with identical transporters case. Secondly, from both theoretical and practical point of view, there exist other possible objectives of interests to be considered, to this initial model in order to be closer to the industrial reality of the considered problem. The first extension could be to consider a different schedule between the production stage and the delivery stage, which means that products may wait between the end of the production stage and the start of the delivery. The second one is to consider the multi-products case when products have different volumes. The methods presented in this chapter form a foundation for modeling and solving these extensions.

5 Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem

Introduction

The supply chain optimization problem we discuss in this chapter considers deliveryinventory decisions. In particular, we study a multi-customer multi-transporter supply chain model, coordinating delivery-inventory decisions. The coordination between supplier and customer for improving the performance of inventory control has received a great deal of attention and the integrated approach has been studied for years. Typically, integrated approach focuses on the production-inventory decisions of supply chain partners while minimizing the total relevant cost of the system. During processing and supply of the product, inventory accumulates with the manufacturer and also with each of the buyers in this system. Delivery of the product in small lots reduces the inventory cost but increases set-up, ordering and transportation cost. On the other hand, delivery in larger lots increases inventory cost but reduces the other costs, and scheduling interference results because of scarce storage capacity at both the manufacturer and the buyers. Synchronization of the production flow is essential for the control of inventory and hence for minimizing the total cost of the system. The integration approach has been researched for years. Much research has focused on this area under various assumptions and objective measures that differ from the problem proposed in this chapter.

This chapter considers integrated delivery-inventory for the supply of multi-items to more than one customer, after its production by a manufacturer. The manufacturer transfers the jobs to a customers by available transporters (Figure 5.1), in different delivery scenarios. The aim of this chapter is to determine the best way to construct an optimal scheduling for the delivery of customers orders, specifying the arrival time of each product and to develop an algorithmic approach capable of establishing solution feasibility for instances of various types and difficulty levels. We focus on single plant production (supplier) scheduling with multi-product, multi-customer delivery-storage problem. The jobs are operated in batch mode and the sequence dependent setup and cost time are considerable in the general model of this study, in the objective to study the delivery-inventory stage, with different delivery structures. In the first scenario the problem is studied in a general way, Chapter 5

Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem where a fleet of heterogeneous transporters are available at the supplier to serve the customers. Here, each transporter could serve different customers without any pre-allotment to any customer. Then in the second scenario the problem is studied with multiple homogeneous transporters without allotment also. In the third model we studied the case of multiple homogeneous transporters with pre-allotment delivery structure, where the customer will be served according to the pre-allotted proposition. In the forth model, we studied the case of one transporter available to serve one customer. The objective is to determine an optimal scheduling for the delivery of customer orders, specifying the arrival time of each product in the different scenarios. The general objective of this chapter is to analyze the efficiency of the results of the optimal delivery and inventory scheduling in the studied scenarios. A comparative study of the solutions of several numerical problems is also carried out, to validate the analytical findings and to examine the limitations of the methods used.

The organization of the remainder of this chapter is structured as follows. In Section 2, the problem definition and formulation is introduced, the notation used along this chapter are defined, then some assumptions are given. In Section 3, the problem is studied as a general model, then we proposed B&B algorithm as an exact method of resolution to solve the general model, and different extensions of the general model are formulated as Mixed-Integer-Programming Models. In section 4 and 5, we provide the experimental results and draw some conclusions of this chapter.

Problem definition and formulation

In the supplier side, a facility of multi-machines is available to produce a finite number of heterogeneous jobs (products), which prevents the supplier's storage cost assumption. Each job needs a constant processing time, however we assume that the total production time of any batch is less than the minimum round-trip delivery time for the transporters. Each round trip between the factory and each customers h requires a delivery cost η h as well as a delivery time τ h . The batches delivered from the vendor to the customers can be equal or unequal-sized batches. It is assumed that directing delivery method is used for sending the batches to the customers. Multiple transporters are considered to deliver the product from the supplier to the customers. Each transporter has a specific c t , where the total number of job belong to the same batch cannot exceed the capacity of the vehicle used. If job j of customer h is delivered before its due date d j , it is known as a early job and a cost equal to β h is incurred, where β h equal to the earliness penalty of the job j belongs to the customer h. Batching and sending several jobs in the batches will reduce the transportation costs. The cost of system includes delivery and holding costs. The objective is to determine the sequence of batches that has to be processed and scheduled of the distributions that have to be used by customers, such that the expected total cost of both vendor and customers be minimized.

Problem definition and formulation

In Figure 5.1 a general multi-customer multi-transporter model has been depicted as an example.

This chapter studies the case where a single supplier delivers a homogeneous product to a multiple customers. The customers order the product at the vendor and receive the products in batch shipments. Delivery of the product in small lots reduces the inventory cost but increases transportation cost. On the other hand, delivery in larger lots increases inventory cost but reduces the other costs, and scheduling interference results because of scarce storage capacity at both the manufacturer and the customers.

Each round trip between the factory and a customer h requires a delivery cost η bht as well as a delivery time τ bht dependent of the size of the batch b, the transporter t and the customer h. Both scenarios of the delivery structure will be discussed later. Each considered transporter has a capacity c t , where the total number of jobs belonging to the same batch does not exceed the capacity of the vehicle used. If job j of customer h is delivered before its due date d j , it is known as an early job and it incurs a cost equal to β h dependent of customer, where β h equal to the earliness penalty at the customer h. Whereas the other models will be represented along the chapter.

The objective is to determine the sequence of batches that has to be processed and scheduled of the distributions that have to be used by customers, such that the expected total cost will be minimized. The cost of the system includes delivery and storage costs.

General notations

The following terminology is used in this chapter:

Parameters

• m: number of customers,

• n: number of jobs,

• p: number of transporters,

• J = {1, 2, ..., n}: set of all jobs,

• H = {1, 2, ..., m}: set of all customers,

• T = {1, 2, ..., p}: set of all transporters,

• j: index for jobs, j ∈ J,

• h: index for customers,h ∈ H,

• t: index for customers,t ∈ T ,

• k: index for batches,

• n h : number of products by customer,

• d j : due date of the job j,

• cl j : customer destination of the job j,

• c t : capacity of the transporter t,

• τ b k ht : time for the vehicle t to deliver a batch of size b k to customer h and to return to the supplier location,

• η b k ht : delivery cost for vehicle t to deliver a batch of size b k to customer h and to return to the supplier location,

• α(k) : delivery cost of batch k,

• β j : customer earliness penalty function for job j, which may also depend from the customer.

Primary variables

• δ 1 jk = 1 if the job j belongs to the k th batch, 0 otherwise, • δ 2 kh = 1 if the batch k is delivered to the customer h, 0 otherwise, • δ 3 kht = 1 if the batch k is delivered to the customer h by the transporter t, 0 otherwise,

Secondary variables

• C j : the arrival time of job j at the customer,

• B k : the arrival time of the batch k at the customer,

• b k : size of batck k

• y k = 1 if the batch k exists and is not empty, 0 otherwise,

• u h : number of delivered batches for customer h, 100 5.3 The General studied Model

Assumptions

Apart from the assumptions already stated and in developing the models we assume the general following hereafter: 1. The system consists of m customers who are supplied by a single-supplier, multiple customers and multiple transporters available to deliver the products to the customer h to which it belongs.

2. Each customer h orders a finite number of jobs to the manufacture, {J 1 , J 2 , ..., J n } 3. The demands among the customers are independent in time.

4. The sequence and machine dependent setup time are negligible.

5. The jobs have to be ready for delivery in batches by their common contracted due date for each job.

6. Each customer estimates individual demand equal to n h , inventory costs are denoted β j .

7. The round trip time of transporters (τ h ) from the supplier to the customers depend of the size of the batch.

8. The storage cost at the customers β j is dependent of the customer and the considered job in the context of multi-product.

The General studied Model

In this section, the mathematical programming models is presented. Using the structural properties of each model, we developed different MIP models for the mentioned problems as follows:

The objective function of the studied problem is the same for the both models, and it is represented as follow:

M in Z = h∈H u h k=1 α(b k ) + n j=1 β j (d j -C j ) (5.1)
The two terms of the objective function in equation (Equation 5.1) represent on the one hand, the delivery costs h∈H u h k=1 α(b k ), and, on the other hand, the inventory costs of the jobs through β j (d j -C j ) . For ease of reference, we denote this problem: Multiple Customers-Transporters Lot Sizing Delivery Scheduling Problem (MCTLSDSP).

Chapter 5

Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem

The general model with batch size dependent time and cost

In the general model we studied the case of single-supplier/mutli-customer with multiple heterogeneous transporters available to serve the customers. Here, the capacity of transporters is different and the batch size dependent proposition is taken into consideration, which means that the delivery time and cost is dependent of the batch size and of the considered transporter. In the first time we developed a Branch and Bound method to study this problem, then a linear Mixed-integerprogramming model is proposed to study this problem. Due to the linearisation status of the MIP model, we supposed that the delivery batch size and cost of all batches is the same.

Branch and Bound Algorithm

In this section, we describe the B&B algorithm that we have developed to solve the MCTLSDSP. The objective of this B&B is to solve small and medium instances, and to be a reference for validating the efficiency of the proposed heuristic algorithms. This B&B algorithm maintains a list of subproblems (nodes) whose union of feasible solutions contains all feasible solutions of the original problem. The list is initialized with the original problem itself. In each major iteration, the algorithm selects a current subproblem from the list of unevaluated nodes. This branching seems to be natural, however the number of branches will be very large for large problems. Consequently, if this method is used in the B&B algorithm, it may take too much time to find optimal solutions, as redundant schedules would be checked repeatedly. Yet, several of the subproblems would already have been eliminated upon the generation of nodes, since the B&B tree includes redundant solutions.

At each node of the search tree, the number of products that still needs to be delivered with each transporter to each customer has to be updated. Iterations are performed until the list of subproblems to be processed is empty. The crucial part of a successful B&B algorithm is the computation of the lower bounds. Therefore, we have developed a lower bound described in the next part.

Efficient lower bound would significantly reduce the time and efforts needed for the B&B method. Based on the main feature of the problem, the lower bound value for the problem is the summation of lower bounds on the total earliness cost and the transportation cost. We assume that w is a partial batch sequence solution, z(w) is the evaluation of w, and r h (w) is the number of products remaining at the customer h for partial solution w. This notation will be used throughout this part.

In each node, the solutions are built from the last batch to the first one for each transporter and each customer. The evaluation of the partial or complete solution is processed with backward equations. The research of a solution starts by constructing a partial solution w. Then, the remainder of products is added in order to 5.3 The General studied Model get a complete solution, with the objective of achieving a minimum delivery cost. Therefore, the more the transporter will be loaded, the more this lower bound will be efficient.

Proposition 1 For a partial solution w, a lower bound for the delivery cost of the remaining products is given by:

m h=1     r h (w) max t∈T (c t )     × min t∈T (η 0ht ) (5.2)
Proof. For each customer h, if r h (w) is the number of products remaining to be delivered, the minimum number of round trips will be equal to r h (w) max t∈T (ct) , and the delivery cost of the remaining products is as denoted in equation (Equation 5.2).

We add the partial solution w to the solution found in equation (Equation 5.2) to get the lower bound of the current node under study.

Corollary 1

The lower bound LB(w) of the partial solution w is given as follows: .

LB(w) = z(w) + m h=1     r h (w) max t∈T (c t )     × min t∈T (η 0ht ) (5.3) Proof. Straightforward.
In the next section, we proposed a Mixed-integer-programming model to solve the general case of the single-supplier/multi-customer with multiple heterogeneous transporters.

The general Mixed-Integer-Programming model

The general model considered previously is non-linear, due to the assumption that the delivery costs and times are dependent of the batch size. In order to model this problem with a MIP approach, we have to linearize it and we assume that the delivery costs and times will only be dependent of the considered transporter and customer. In the remaining of this chapter, we denote :

• τ ht : time for the vehicle t to deliver a batch to customer h and to return to the supplier location,

• η ht : delivery cost for vehicle t to deliver a batch to customer h and to return to the supplier location, Chapter 5

Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem

Here we studied the general case of the single-supplier/multi-customer with multiple heterogeneous transporters with the assumption of identical batch size time and cost.

A principal important variable is used in this model with is δ 3 kht where the batch k is deliver to customer h with the transporter t. The transporter have different capacity and available to serve all the customers in the same time or progressively.

Due to the linearisation status of the MIP model, the objective fucntion of the MCTLSDSP is given by:

M in Z = t∈T m h=1 u h k=1 η ht × δ 3 kht + n j=1 β j (d j -C j ) (5.4)
Subject to: 5.15) Constraint (Equation 5.5) guarantees that, each job must be scheduled exactly in one batch, in this constraint the jobs will be batched only in the batch which it belongs. Constraints (Equation 5.6) and (Equation 5.7) indicate that, each batch must be scheduled exactly to one customer by a specific transporter t, in this constraint the batches will be delivered only to the customer which it belongs with the transporter t. Constraint (Equation 5.8) calculates the number of batches delivered to each customer and the transporter used to transport this batch. Constraint (Equation 5.9) guarantees that no empty batch is allowed. Constraint (Equation 5.10) prevents the number of jobs scheduled in one delivery batch to exceed the capacity of the transporter used. Constraint (Equation 5.11) indicates that arrival time of each job is at least equal to the contracted due date for each customer. Constraint (Equation 5.12) represents the conversion of the completion time of the products belong to the same batch C j to B k the arrival time of each batch to the customers. This constraint represented in a non-linear way in this mathematical representation to facilitate the understanding of the problem. Constraints (Equation 5.13) shows the relation between the arrival time of two consecutive batches and the delivery time which their belong and the availability of a transporter t at the supplier, to prevents the overlap between two consecutive batches in the case of two consecutive jobs delivered separately in two different batches. This constraint take into consideration the cases of: two or more consecutive batches belong to same customer and delivered with the same transporter t; two or more consecutive batches belongs to two different customers by the same transporter t; two or more consecutive customers served by two or more different transporters. Constraints (Equation 5.14) and (Equation 5.15) define the range of the variables.

n k=1 δ 1 jk = 1, j = 1, . . . , n (5.5) m h=1 p t=1 δ 3 kht ≤ 1, k = 1, . . . , n (5.6) p t=1 δ 3 k,cl j ,t ≥ δ 1 jk , j, k = 1, . . . , n (5.7) u h = n k=1 p t=1 δ 3 kht , h = 1, .., m (5.8) y k ≥ y k+1 , k = 1, ..., n -1 (5.9) n j=1 δ 1 jk ≤ m h=1 p t=1 c t × δ 3 kht , k = 1, . . . , n (5.10) C j ≤ d j , j = 1, . . . , n (5.11) 104 5.3 The General studied Model C j = n k=1 B k × δ 1 jk , j = 1, .., n (5.12) B k2 -B k1 - m h=1 (τ ht + M ) × (δ 3 k2,h,t + δ 3 k1,h,t ) ≥ -2 × M, (5.13) k 1 , k 2 = 1...n, k 2 > k 1 t = 1...p C j ≥ 0, j = 1, 2, . . . , n (5.14) δ 1 jk , δ 3 kht ∈ {0, 1}, j, k = 1, .., n ; h = 1, .., m; t = 1...p (
The general proposed MIP model and the B&B algorithm developed in the previous sections could solve the small and some medium size instances, however the time of resolution to solve the large size instances grows exponentially. In the next section, a specific models are proposed as a particular case to solve the problem rapidly and to study its performances.

Chapter 5

Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem

Specific model with homogeneous delivery structure

In the first specific model, we suppose that the transporters are homogeneous and we keep the consideration of the availability of the transporters to serve the customers without allotment. Here the parameters of the capacity of the transporters c t becomes the same to all the transporter used and it equals to c. The variable δ 3 kht equals to 1 when the batch k will be delivered to the customer h with the transporter t will be replaced here byδ 2 kh , which means that each batch k belongs to customer h without any consideration of the transporter used to serve this batch due the assumption of the homogeneous transporters specified in this section. For this model the constraints are defined as follows: subject to :

n k=1 δ 1 jk = 1, j = 1, . . . , n (5.16) m h=1 δ 2 kh ≤ 1, k = 1, . . . , n (5.17) δ 2 k,cl j ≥ δ 1 jk , j, k = 1, . . . , n; k ≤ j (5.18) u h = n k=1 δ 2 kh , h = 1, .., m (5.19) y k ≥ y k+1 , k = 1, ..., n -1 (5.20) n j=k δ 1 jk ≤ c, k = 1, . . . , n (5.21) C j ≤ d j , j = 1, . . . , n (5.22) C j = n k=1 B k × δ 1 jk , j = 1, .., n (5.23) 106 5.3 The General studied Model B k+nt -B k - m h=1 τ ht × (δ 2 k+nt,h + δ 2 k,h ) ≥ 0, (5.24) k = 1...n, , k ≤ n -nt C j ≥ 0, j = 1, 2, . . . , n (5.25) δ 1 jk , δ 2 kh ∈ {0, 1}, j, k = 1, .., n ; h = 1, .., m (5.26)
Constraint (Equation 5.16) guarantees that, each job must be scheduled exactly in one batch, in this constraint the jobs will be batched only in the batch which it belongs. Constraints (Equation 5.17) and (Equation 5.18) indicate that, each batch must be scheduled exactly to one customer, in this constraint the batches will be delivered only to the customer which it belongs. Constraint (Equation 5.19) calculates the number of batches delivered to each customer. Constraint (Equation 5.20) guarantees that no empty batch is allowed. Constraint (Equation 5.21) prevents the number of jobs scheduled in one delivery batch to exceed the capacity of the vehicle. Constraint (Equation 5.22) indicates that arrival time of each job is at least equal to the contracted due date for each customer. Constraint (Equation 5.23) represents the conversion of the completion time of the products belong to the same batch C j to B k the arrival time of each batch to the customers. This constraint represented in a non-linear way in this mathematical representation to facilitate the understanding of the problem. Constraints (Equation 5.24) shows the relation between the arrival time of two consecutive batches and the delivery time which their belong and the availability of a vehicle at the supplier, to prevents the overlap between two consecutive batches in the case of two consecutive jobs delivered separately in two different batches. Constraints (Equation 5.25) and (Equation 5.26) define the range of the variables.

Specific model with homogeneous transporters allotted to each customer

In this model, we assume that each customer h has a fleet of transporters allotted to each customer to deliver the products to its customer. We introduced the new notation called nt h , which is the number of transporters allotted to customer h, where nt h = (nt×n h ) n with h = 1, .., m. Here we supposed that all the transporter used have identical capacity equals to c. The set of batches for each customer h is

k h ∈ {n 1 , . . . , n h }, h ∈ H Chapter 5
Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem

Since they are different customers, the cumulative sum of products by customer per demand is

x h = m h=0 n h , h ∈ H and x 0 = 0 subject to :

k [cl j ] k=1 δ 1 j,k = 1, j = 1, . . . , n (5.27) m h=1 δ 2 k,h ≤ 1, k = 1, .., n & h = cl k (5.28) δ 2 k,cl j ≥ δ 1 j,k , j = 1, .., n & k = 1, .., k [cl j ] (5.29) u h = n k=1 δ 2 kh , h = 1, .., m & h = cl k (5.30) k [cl k ] j=1 δ 1 j,k ≤ c, k = 1, .., n (5.31) C j ≤ d j , j = 1, . . . , n (5.32) C j = k [cl j ] k=1 B k × δ 1 j,k , j = 1, . . . , n (5.33) B k2 -B k1 - m h=1 [(τ ht /nt[h])+M ]×(δ 2 k2,h +δ 2 k1,h ) ≥ -2×M, k 1 < k 2 & h ∈ H (5.34) C j ≥ 0, j = 1, 2, . . . , n (5.35) δ 1 jk , δ 2 kh ∈ {0, 1}, with j, k = 1, .., n, & h ∈ H (5.36)
Constraint (Equation 5.27) guarantees that, each job must be scheduled exactly in one batch, in this constraint the bounds k

cl j , x [cl j -1] + k and (k × c) -x [cl j -1] ≥ j ≥ k -x [cl j -1]
limit the combination of the number of bearable batches of job j. Constraints (Equation 5.28 and Equation 5.29) indicate that, each batch must be scheduled exactly to one customer, where each job could be scheduled in the batch k according to the proposed bounds 5.30) calculates the number of batches delivered to each customer, with h = cl k . Constraint (Equation 5.31) prevents the number of jobs scheduled in one delivery batch to exceed the capacity of the vehicle. Here, the jobs belong to the same customer is limited between (k × c) -x [cl j -1] and k -x [cl j -1] according to the proposed bounds in equation (Equation 5.31). Constraint (Equation 5.32) indicates that the arrival time of each job is at least equal to the contracted due date for each customer. Constraint (Equation 5.33) represents the conversion of the completion time C j of the jobs between (k × c) -x [cl j -1] and k -x [cl j -1] belong to the same batch k to B k the arrival time of batches. This constraint represented in a nonlinear way in this mathematical representation to facilitate the understanding of the problem. Constraints (Equation 5.34) shows the relation between the arrival time of two batches belong to the same customer (x

(k × c) -x [cl j -1] ≥ j ≥ k -x [cl j -1] . Constraint (Equation
[cl j 1 -1] + k 1 and x [cl j 2 -1] + k 2 ),
the delivery time which their belong and the availability of a vehicle belongs to this customer at the supplier, to prevent the overlap between the batches in the case of jobs delivered separately in two different batches. The conditions used in this constraint set Constraints (Equation 5.35) and (Equation 5.36) define the range of the variables.

Specific model with homogeneous one transporter allotted to one customer (h equals to p)

Here we supposed that each customer has one allotted transporter used to serve each customer. The capacity of all the transporters used is the same and equals to c.

subject to :

n k=1 δ 1 j,k = 1, j = 1, . . . , n (5.37) m h=1 δ 2 k,h ≤ 1, k = 1, .., n (5.38) Chapter 5
Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem

δ 2 k,cl j ≥ δ 1 j,k , j& k = 1, .., n (5.39) u h = n k=1 δ 2 kh , h = 1, .., m (5.40) y k ≥ y k+1 , k = 1, ..., n -1 (5.41) n j=1 δ 1 j,k ≤ c, k = 1, .., n (5.42) C j ≤ d j , j = 1, . . . , n (5.43) C j = n k=1 B k × δ 1 j,k , j = 1, . . . , n (5.44) B k2 -B k1 - m h=1 (τ ht +M )×(δ 2 k2,h +δ 2 k1,h ) ≥ -2×M, k 1 , k 2 = 1...n, & k 2 > k 1 (5.45) C j ≥ 0, j = 1, 2, . . . , n (5.46) δ 1 jk , δ 2 kh ∈ {0, 1}, with j, k = 1, .., n, & h ∈ H (5.47)
Constraint (Equation 5.37) guarantees that, each job must be scheduled exactly in one batch, in this constraint the jobs will be batched only in the batch which it belongs. Constraints (Equation 5.38 and Equation 5.39) indicate that, each batch must be scheduled exactly to one customer, in this constraint the batches will be delivered only to the customer which it belongs. Constraint (Equation 5.40) calculates the number of batches delivered to each customer. Constraint (Equation 5.41) guarantees that no empty batch is allowed. Constraint (Equation 5.42) prevents the 110 5.4 Experimental Results number of jobs scheduled in one delivery batch to exceed the capacity of the vehicle. Constraint (Equation 5.43) indicates that the arrival time of each job is at least equal to the contracted due date for each customer. Constraint (Equation 5.44) represents the conversion of the completion time C j belong to the same batch k to B k the arrival time of batches. This constraint represented in a non-linear way in this mathematical representation to facilitate the understanding of the problem. Constraints (Equation 5.45) shows the relation between the arrival time of two consecutive batches and the delivery time which their belong, to prevents the overlap in the case of two consecutive batches delivered separately to the same customer.

In this constraint we remark that the relationship is confined only between the batches and the customer to which it belongs δ 2 k,h . Constraints (Equation 5.46) and (Equation 5.47) define the range of the variables.

Experimental Results

The MIP models was solved with CPLEX solver to exactly solve the models. The computations were carried out on a desktop Intel core 2 processor operating at 2.67 GHz clock speed and 4 GB RAM. The models where run for at most one hour by instance or until the solver found the models optimal solutions or ran out of the memory, in this case we collect the best optimal solutions found. The solver was terminated when the time of resolution exceeds 3600 seconds.

The following sections describe the main results obtained from the comparison of the mathematical programming formulation proposed models with a random instance. The efficiency is the most important criterion for evaluating the results obtained from the different models. Inside it, we study the quality of solutions and the computational time in each model.

Evaluation of the quality of different models

In order to evaluate the coordination mechanisms developed in this chapter, let us solve a small problem of supplying 8 jobs to 2 different customers. The jobs are delivered by two transporters depend of the delivery structure used. The capacity of the transporters equal to 2 in all the specific proposed models, and it equals to (2 and 3) for the transporter 1 and 2 respectively, for the general model. In the customers side, the transporter delivery time and cost depend of the the distance between the supplier and each customer with (η 1t = 8, τ 1 = 11, η 2t = 10, τ 2t = 15) belongs to customer 1 and 2 respectively, and the customer cost in each side equals to (β j1 = 1, β j2 = 2) for all jobs j1 (resp. j2) requested by customer 1 (resp. 2). The first customer ordered 5 jobs and the second customer ordered 3 jobs as follows; (j 1 , j 2 , j 5 , j 6 , j 8 ) belongs to customer 1 and (j 3 , j 4 , j 7 ) belongs to customer 2, with a due dates {10010, 10020, 10050, 10060, 10080} and {10030, 10040, 10070} belongs Chapter 5

Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem to customer 1 and 2 respectively. The data of different parameters are given in Table 5.4.1. A comparative evaluation of the results of each method is given in Figure 5.2,Figure 5.3,Figure 5.4 and Figure 5.5, where an illustration of the models and the result for each proposed delivery structures is presented. Lets denote that {k; j; C j }, the notation which is used in Table 5.4.1 for a solution of one batch, where the first term k describes the batch number, the second term j describes the jobs which will be delivered in this batch and the third term C j is the arrival time of the products which are in batch k at the customer's to which it belongs.

Evaluation of the general model

For the first model which is the general model of the single-supplier multi-customer with multi-transporter. The result in Figure 5.2 shows that there is 4 batches with 2 batches for each customer with a delivery cost equals to 2×η 1t +2×η 2t = 32+40 = 72. The jobs j 1 and j 2 arrive in the first batch at 10010 by the second transporter t 2 , which incurs an inventory cost for job j 2 at the second customer equals to (5×1 = 5). Then, in the second batch the jobs 3 and 4 arrive at 10020 by the transporter t 1 , which incurs an inventory cost for job j 4 at the first customer equals to (10×2 = 20). For the third batch, the transporter t 2 delivers the jobs (j 5 , j 6 , j 8 ) at 10035, which incurs an inventory cost for job j 5 and j 8 at the customer 2 equals to (5×1+15×1 = 20). In the last batch belongs to customer 1, the job j 7 arrives on time and it is not incur any inventory cost. The total cost for general model becomes equal to 72 + 5 + 20 + 20 = 117.

Evaluation of the specific model with homogeneous transporters without allotment

For the specific model which is the multi-homogeneous delivery structure of the single-supplier multi-customer with multi-transporter. The result is depicted in Figure 5.3 shows that there is 5 batches with 2 batches belong each customer 1 and three batches belong to customer 2, which incur a delivery cost equals to 3 × η 1t + 2 × η 2t = 48 + 40 = 88. The jobs j 1 and j 2 arrive in the first batch at 10006, which incurs an inventory cost for job j 1 and j 2 at the second customer equals to (4 × 1 + 9 × 1 = 13). Then, in the second batch the jobs 3 and 4 arrive at 10020, which incurs an inventory cost for job j 4 at the first customer equals to (10 × 2 = 20). For the third batch, the jobs (j 5 , j 6 ) arrive at 10028, which incurs an inventory cost at the customer 2 equals to (7×1+12×1 = 19). In the two last batches belong to customer 1 and 2 respectively, the job j 7 and j 8 arrive on time and they not incur any inventory cost. The total cost for general model becomes equal to 88 + 13 + 20 + 19 = 140.

Chapter 5

Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem

Evaluation of the specific model with homogeneous transporters allotted to each customer

For the specific model which is the homogeneous transporters allotted to each customer. here the transporters t1 and t2 are allotted to customers 1 and 2 respectively. The result is depicted in Figure 5.4 and it shows that there is 5 batches with 2 batches belong each customer 1 and three batches belong to customer 2, which incur a delivery cost equals to 3 × η 1t + 2 × η 2t = 48 + 40 = 88. The jobs j 1 and j 2 arrive in the first batch at 10006 by the transporter allotted to this customer which is t2. The jobs j 1 and j 2 incur an inventory cost for at the second customer equals to (4 × 1 + 9 × 1 = 13). Then, in the second batch the jobs 3 and 4 arrive at 10020 by the transporter t1, which incurs an inventory cost for job j 4 at the first customer equals to (10 × 2 = 20). For the third batch, the jobs (j 5 , j 6 ) arrive at 10028 by the transporter t2, which incurs an inventory cost at the customer 2 equals to (7 × 1 + 12 × 1 = 19). In the two last batches belong to customer 1 and 2 respectively, the job j 7 and j 8 arrive in parallel on time by the transporters t1 and t2 respectively and they not incur any inventory cost. The total cost for general model becomes equal to 88 + 13 + 20 + 19 = 140.

Evaluation of the specific model with homogeneous one transporter allotted to one customer (h equals to p)

For the specific model which is the homogeneous one transporter allotted to one customer (h equals to p) scenario, the number of batches equal to 5 with three batches for customer 2 and two batches for customer 1, which mean that the delivery cost for this model equals to 3 × η 2t + 2 × η 2t = 48 + 40 = 88.

We start by the second customer where we have one transporter allotted to this customer, in the first batch belongs to this customer we have two jobs (j 1 and j 2 ) arrive at 10006 which incurs an inventory cost equals to (4 × 1 + 9 × 1 = 13). In the second batch belongs to the same customer (batch 3) jobs (j 5 and j 6 ) arrive at 10028 with 7 units of time for job j 5 and 12 units of time for job j 6 , which incurs an inventory cost at the customer 2 equals to (7 × 1 + 12 × 1 = 19). In the last batch belongs to customer 2, the job j 8 arrives on time without any inventory cost. Now, for the first customer, the first batch belongs to this customer arrives at 10020 and it includes the jobs 3 and 4, which incurs an inventory cost for job j 4 at the first customer equals to (10 × 2 = 20). The second batch belongs to this customer arrives on time at 10050, which does not incur any inventory cost for the job j 7 . The total cost for general model becomes equal to 88 + 13 + 19 + 20 = 140.

Summary of the evaluation of the quality of solutions

We observe that the inventory cost at the customers obtained in in the general model which equals to 45 is better than that obtained in the specific models which equals to 52, consistent with the delivery structure used in each model and the storage cost at the customers. The delivery cost in the general model which equals to 72 is better than that of the specific models which equals to 88, this difference is due to the efficiency of the heterogeneous transporters proposed in the general model. The total cost in the specific models is higher than the corresponding cost in the general model, and this is mainly due to the reduction in the inventory cost at the customers due to the efficient delivery structure proposed in the general model with the heterogeneous transporters.

Evaluation of the Computational Results

To test the performance of the computational time of the models discussed in this chapter we randomly generated a set of test problems and compared the computation times to the general purpose solver CPLEX. The characteristics of the case are listed in Table 5.4.2. Characteristics of orders to schedule differ by customers, transporter It is however interesting to see that an exact solution are obtained for the CPLEX solver to solve all the instances of different models in class A. In this class, the total storage cost at the customers n j=1 β j (d j -C j ), which constitute the second part from the objective function (Equation 3.1), will be less than that of the total transporter cost m h=1 η ht u h , which constitute the first part from the objective function (Equation 3.1). In this case, the problem is the least complex to solve, because the vehicles are fully loaded according to the cheapness of the storage cost at the customers.

When the MIP model was tested it became evident that it suffered from a poor linear programming (LP) relaxation (Class B and C). The poor LP relaxation leads to an increased solution time since the CPLEX solver uses the LP relaxed solution as an internal lower bound for solving the problem. If the internal lower bound is poor, it can take long time to solve the proposed model. In the solution of the instances tested in Class B we noticed that, the increase in number of batches and the decrease of the size of products by batch in the optimal solution. In this case the solver solves only the instances with 10 and 15 jobs in the most instances but with a large time of resolution very near to one hour. Then in the third cases (Class C), we observe that CPLEX could solve instance with 10 jobs, then it runs out of memory with time of resolution more than one hour. In this case, we noticed that the vehicle is very lightly loaded.

The development of the time of resolution as the number of jobs increases is studied, for different Models in each Case (A, B and C) in (Table 5.3). The results show the fastness of the (homo. Trans. with allotment) model to give an optimal solutions for small size instances. As can be seen, if the number of jobs and transporters increase, the time of resolution will increase in each model.

Conclusion

This chapter describes four models to solve an integrated batching and scheduling delivery-inventory problem where a single supplier supplies a products to multiple customers with multi-transporter considerations. In the first model, a general model with heterogeneous transporters with different capacity transfer items to the customers without allotment. A Branch and Bound algorithm is developed to solve the general model and a Mixed-Integer-Programming is proposed to solve this model. In the second model, we studied the case of multi-homogeneous-transporter without allotment, where all the transporters used have the same capacity, and a Mixed-Integer-Programming is proposed to solve this model. Third we studied the model with homogeneous transporters with allotment, where the number of transporters 5.5 Conclusion dependent of the demand of each customers, and a Mixed-Integer-Programming is proposed to solve this model.. Forth the last model, one transporter allotted to each customer with the consideration of the homogeneous transporters also, and a Mixed-Integer-Programming is proposed to solve this model.

Each transfer of batches incurs transportation cost and each product arrives at the customer before its due date incurs an inventory cost. Optimum solution techniques for all four models are presented while sensitivity analysis has also been performed to study the quality of solution of each method. In this chapter, we do not restrict the vendor to have either greater or less holding cost than everyone else in the system. The studied models in this chapter is also flexible in accommodating unequal transportation time and cost for each customer in the system, this costs dependent of the distance between the supplier and the customers. A numerical study performed on the four models presented here reveals that under similar circumstances, the first model is always more efficient in solving the integrated delivery-inventory system.

6 Conclusions and Future Extensions

Conclusions

This thesis presents some new models and resolution approaches for the batching and scheduling problem in multi-scenario supply chain management, as part of the development of a broader scheduling methodology. The primary objective of this work was to develop a general and integrated methodology for these complex, highly combinatorial problems. A real case-study from the central medical stores was used as test-bed in this research. Emphasis was given to the specific features of this industrial sector, involving a significant work to contextualize and determine how the batching and scheduling functions are performed. The key contributions of this thesis and recommendations for future research are summarized in what follows.

Summary of Contributions

Batching and Scheduling problems in supply chain have received considerable attention in the past decades due to their importance for the efficiency of operations. A variety of modeling approaches has appeared in the literature, introducing different types of formulations and involving multiple decisions and objectives. In general, there has been an effort to take into account the computational efficiency of the formulations, particularly when addressing large instances problems. Nevertheless, modeling, computational performance, and the integration of optimization methods in the real decision-making processes of companies, are still open issues that have been addressed in this study.

In general, the major contributions of this study can be summarized as follows:

In the first studied problem with singlee-supplier/multi-customer and one transporter used to serve the costumers separately, we have proposed some enhancements to the batching and the delivery of batches of the real-life studied in the central medical stores, which takes into account the different parameters related to the health care environment. Moreover, we have proposed an efficient genetic algorithm which is compared with a developed Branch and Bound algorithm and a Mixed Integer Programming model as an exact solutions. This study leads to two important advantages. First, the resolution of real world scheduling problems helped to focus Chapter 6

Conclusions and Future Extensions the research in the development of optimization models that can effectively be implemented. Thus, practical scheduling requirements have been discussed with the central medical stores and considered in the models whenever possible. Second, although the scheduling models and solution approaches developed were motivated by a case-study, they can be applied to other types of industries, as long as the scheduling problem has a similar structure.

In the second studied problem with single-supplier/single-customer and multiple homogeneous and heterogeneous transporters cases, we have assumed the batchsize-dependent delivery times and costs in order to take into account the loading and the unloading times of the transporters, this configuration has not been studied tell now, as far as we know. In a second distinguishing feature for the same studied problem, we have developed a dynamic programming algorithm based on a dominance property, which is very efficient in the identical transporters case and compared it to a mixed-integer-programming model solved by CPLEX. Then an approach method consists of an efficient genetic algorithm is developed and compared to the proposed exact methods.

In the third studied problem with single-supplier/multi-customer with multiple transporters consideration, we have proposed a general model with multiple heterogeneous transporters available to serve the customer without any allotment, then we have proposed a model with allocated transporters to each customers. For this work, we have developed branch and bound algorithm in the general case, which is compared to a MIP model solved by CPLEX.

The study presented in this chapter may be extended in several directions. First, improving the efficiency of the proposed dynamic programming method in the general case, although it is already an efficient method, in order to solve larger problem instances. For that purpose, it is possible to use a lower bound by solving a similar problem with identical transporters case. Secondly, from both theoretical and practical point of view, there exist other possible objectives of interests to be considered, to this initial model in order to be closer to the industrial reality of the considered problem. The first extension could be to consider a different schedule between the production stage and the delivery stage, which means that products may wait between the end of the production stage and the start of the delivery. The second one is to consider the multi-products case when products have different volumes. The methods presented in this chapter form a foundation for modeling and solving these extensions.

The outputs of this thesis are significant contributions for better modeling scheduling problems and for solving real industrial problems. They can also be viewed as a sound basis for the development of improved and more sophisticated decision support tools for dealing with those problems.

Possible Future Extensions

The integrated models presented here are subject to certain restrictions, which can be considered in future research. By relaxing some of those restrictions, the problem will become more complex but more realistic. However, in order to enhance the applicability and model performance, the following extensions are suggested:

The first research opportunity is related to the single-supplier/multi-customer with one transporter and could be advanced by allowing the vehicle routing with integrated delivery and storage cost. This work could be integrated into the setup time and cost into the production stage, and the volume of products into the delivery stage.

The second research opportunity is concerned with the development of single-supplier single-customer with multiple transporters case by improving the efficiency of the proposed dynamic programming method in the general case, although it is already an efficient method, in order to solve larger problem instances. For that purpose, it is possible to use a lower bound by solving a similar problem with identical transporters case. Another possible extension for this work could be related to the theoretical and practical point of view, where there exist other possible objectives of interests to be considered. The first consideration could be related to a different schedule between the production stage and the delivery stage, which means that products may wait between the end of the production stage and the start of the delivery. The second one is to consider the multi-products case when products have different volumes. The methods presented in this chapter form a foundation for modeling and solving these extensions.

The third research opportunity is associated to the single-supplier/multi-customer with multiple transporters, where we aim to develop the general case which is without allocated transporters according to an industrial study by added some new constraints of the general model. Moreover, we aim to develop an efficient approach algorithm to solve a medium and large instances due to the large time of resolution found by the proposed exact methods.

Finally

Figure 2 . 1 :

 21 Figure 2.1: Flow diagram of single supplier single customer with multiple transporters integrated supply chain

Figure 2 . 2 :

 22 Figure 2.2: Flow diagram of single supplier multiple customers with one transporters integrated supply chain

Ch a p t e r 2 Figure 2 . 3 :Figure 2 . 4 :Figure 2 . 5 :Figure 2 . 6 :Figure 2 . 7 :

 22324252627 Figure 2.3: Se r i a l p r o d u c t s t r u c t u r e

Figure 3. 1 Figure 3

 13 Figure 3.1 Figure 3.1: Single-supplier and multi-customer model

Figure 3 . 2 :

 32 Figure 3.2: Ge n e t i c a l g o r i t h m

Ch a p t e r 3

 3 Mu l t i -Cu s t o m e r w i t h Si n g l e -Tr a n s p o r t e r In t e g r a t e d Lo t Si z i n g a n d De l i v e r y Sc h e d u l i n g Pr o b l e m Th e MIP m o d e l w a s s o l v e d w i t h CPLEX s o l v e r a n d t h e p r o p o s e d a l g o r i t h m s i s c o d e d i n JAVA l a n g u a g e . Th e c o m p u t a t i o n s w e r e c a r r i e d o u t o n a d e s k t o p In t e l c o r e 2 p r o c e s s o r o p e r a t i n g a t 2.67 GHz c l o c k s p e e d a n d 4 GB RAM. Th e m o d e l w h e r e r u n f o r a t m o s t o n e h o u r b y i n s t a n c e o r u n t i l t h e s o l v e r f o u n d t h e m o d e l s o p t i m a l s o l u t i o n s o r r a n o u t o f t h e m e m o r y , i n t h i s c a s e t h e b e s t o p t i m a l s o l u t i o n f o u n d e d i s c o l l e c t e d a s n e a r o p t i m a l s o l u t i o n . Th e r e f e r e n c e o f t i m e l i m i t o f r e s o l u t i o n i s b a s e d o n t h e r e a l t i m e o f t h e p r e p a r a t i o n o f a s c h e d u l i n g i n t h e a c t u a l c a s e . As a c o m p a r i s o n , CPLEX s o l v e r i s u s e d t o e x a c t l y s o l v e t h e m o d e l w i t h s m a l l s c a l e r a n d o m i n s t a n c e s . So m e a d j u s t m e n t s a r e d o n e o n t h e p a r a m e t e r s o f r e s e a r c h i n CPLEX, i n t h e o b j e c t i v e t o a c c e l e r a t e t h e r e s e a r c h o f s o l u t i o n s . a r i f y t h e p r o b l e m , w e c o n s i d e r a s i m p l e n u m e r i c a l e x a m p l e i n (Ta b l e 3.3) a s f o l l o w . Tw o c u s t o m e r s o r d e r e d 5 j o b s a t t h e s a m e t i m e (Mo n d a y a t 8:00 a m ) a n d t h e y w o u l d r e c e i v e t h e i r p r o d u c t s a t t h e s a m e t i m e (Th u r s d a y a t 8:00 a m ), t h a t m e a n s a l l t h e p r o d u c t s h a v e t h e s a m e d u e d a t e e q u a l t o 72 hours. Th e s u p p l i e r a n d i t s c u s t o m e r s o p e n 24 hours per day. Th r e e j o b s (j = 1, 3 and 5) f o r c u s t o m e r 1 a n d t w o j o b s (j = 2 a n d 4) f o r c u s t o m e r 2. Th e v e h i c l e c a p a c i t y c = 2. Th e t r a n s p o r t e r d e l i v e r y c o s t a n d t i m e d e p e n d o f t h e c u s t o m e r ' s p o s i t i o n s w i t h (η 1 = 1000 Euro, τ 1 = 6 hours a n d η 2 = 750 Euro, τ 2 = 4 hours) b e l o n g t o c u s t o m e r 1 a n d 2 r e s p e c t i v e l y , (β 1 = β 3 = β 5 = 30 Euro/hour a n d β 2 = β 4 = 20 Euro/hour) b e l o n g t o c u s t o m e r 1 a n d 2 r e s p e c t i v e l y . Table 3.3: A n u m e r i c a l e x a m p l e Th e s o l u t i o n i s s h o w n i n (Ta b l e 3.3) f o r t h i s p r o b l e m . As i t i s s h o w n , t h e v e h i c l e m a k e s t h r e e r o u n d t r i p s a m o n g t h e m t w o t o c u s t o m e r 1 a n d o n e t o c u s t o m e r 2. Th r e e b a t c h e s k 1 = 1, k 2 = 2 a n d k 3 = 2 a r e d e n o t e d . Th e p r o d u c t s a r r i v e a t t h e c u s t o m e r i n t h e b a t c h t o w h i c h t h e y b e l o n g i n t h e c o m p l e t i o n t i m e c i t e d i n (Ta b l e 3.3). Th e t o t a l d e l i v e r y c o s t e q u a l s t o η 1 × 2 + η 2 × 1 = 2750 Euro a n d t h e t o t a l s t o r a g e c o s t a t t h e c u s t o m e r s e q u a l s t o β 1 × [(d 1 -C 1 ) + (d 3 -C 3 ) + (d 5 -C 5 )] + β 2 × [(d 2 -C 2 ) + (d 4 -C 4 )] = 30 × [20 + 0 + 0] + 20 × [10 + 10] = 1000 Euro. Th e a m o u n t o f t h e o b j e c t i v e f u n c t i o n i s 3750 Euro. Ac c o r d i n g t o t h e c o n fi d e n t i a l i t y o f t h e d a t a b a s e o f t h e r e a l -l i f e d a t a o f t h e s y s t e m u n d e r s t u d y , a s e v e r a l c l a s s e s o f p r o b l e m h a v e b e e n c o n s i d e r e d f o r w h i c h s e v e r a l i n s t a n c e s h a v e b e e n g e n e r a t e d r a n d o m l y .

  hours. The due dates (d j ) j=1..n are uniformly separated with values randomly generated. Chapter 3 Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery Scheduling Problem

(

Figure 4 . 1 :

 41 Figure 4.1: Th e c a s e o f o p t i m a l s o l u t i o n (o p t i m a l c o s t = 1750.24)

Figure 4 . 2 :

 42 Figure 4.2: Th e c a s e o f f u l l y l o a d e d s o l u t i o n ( Co s t = 2158)

Figure 4 . 3 :

 43 Figure 4.3: An example of the dominance relation

Figure 4 . 4 :

 44 Figure 4.4: An example of the dominance relation in the identical transporters case

Figure 4 . 5 :

 45 Figure 4.5: A s i m p l e GA fl o w c h a r t

92 4 . 5

 45 Experimental and Computational results

Figure 5 .

 5 Figure 5.1 illustrates the general model for the delivery consideration. It represents the case where a fleet of transporters could serve all the customers without allotment.Whereas the other models will be represented along the chapter.

Figure 5 . 1 :

 51 Figure 5.1: Multi-customer Multi-transporter general model

Figure 5 . 2 :

 52 Figure 5.2: Illustration of models for different delivery structures

Figure 5 . 3 :

 53 Figure 5.3: Illustration of models for different delivery structures

Figure 5 . 4 :

 54 Figure 5.4: Illustration of models for different delivery structures

Figure 5 . 5 :

 55 Figure 5.5: Illustration of models for different delivery structures

  2.

	Algorithm 3.1 The Lot Sizing Scheduling Algorithm
	for j ← 0 to n do
	currentJob ← n -j + 1 ;
	jobDest ← cl[CurrentJob] ;
	nbrP artsDelivered [jobDest]++ ;
	for level ← 0 to j do
	if (T estOf Capacity()) then
	currentSol ← GetBestSol(level) ;
	for h ← 1 to m do
	if (T estQuantityDeliv()) then
	AddBatch(currentSol) ;
	end if
	end for
	Evaluate(currentSol) ;
	Improvement(currentSol) ;
	CompareAndU pdate(currentSol) ;
	end if
	end for
	end for
	bestSolution ← GetBestSol n ;

  cl 1 ; 1150), (1; cl 2 ; 1100)]}, then the two potential joint solutions are compared and the good solution is kept, which is [(1; cl 2 ; 1100), (1; cl 1 ; 1150)].3. Setn = 3. For j = {3,2, 1}, based on the delivery scheme of the first step, the new delivery schemes are {[(1; cl 1 ; 1150), (1; cl 2 ; 1100), (1; cl 1 ; 1000)] and [(1; cl 1 ; 1150), (1; cl 1 ; 1000), (1; cl 2 ; 1100)]}. Then, two solutions could be obtained according to the swap operation which are {[(1; cl 2 ; 1100), (1; cl 1 ; 1000), (1; cl 1 ; 1150)] and [(1; cl 1 ; 1000), (1; cl 2 ; 1100) (1; cl 1 ; 1150)]}, then the four potential joint solutions are compared and the good solution is kept, which is [(1; cl 1 ; 1000), (1; cl 2 ; 1100), (1; cl 1 ; 1150)]. after that, based on the delivery scheme of the second step, the delivery scheme on this step is [(1; cl 2 ; 1100), (1; cl 1 ; 1150), (1; cl 1 ; 1000)]. In the improvement phase, a new solution could be obtained which is [(1; cl 1 ; 1000), (1; cl 2 ; 1100), (1; cl 1 ; 1150)]. The two potential joint solutions are compared and the good solution is kept, which is [(1; cl 1 ; 1000), (1; cl 2 ; 1100), (1; cl 1 ; 1150)]. Finally, the two potential joint solutions kept in each level are compared and the best final solution is recovered,

	3.5 Genetic Algorithm
	[(1;
	The potential delivery scheme is equal to [(1; cl 1 ; 1150),
	(1; cl 2 ; 1100)]. Due to the improvement phase, two solutions could be obtained
	according to the swap operation which are {[(1; cl 2 ; 1100), (1; cl 1 ; 1150)] and
	54

which is [(1; cl 1 ; 1000), (1; cl 2 ; 1100), (1; cl 1 ; 1150)].

Table 3 . 4 :

 34 Main characteristics of the test cases

	Case n	h	β h (Euro)	η h (Euro)	τ h (Hours)
		10 2, 3, 4
	A	20 2, 3, 4 30 2, 3, 4	[1; 5]	[1000; 1500]	[3; 5]
		40 2, 3, 4
		10 2, 3, 4
	B	20 2, 3, 4 30 2, 3, 4	[10; 50]	[1000; 1500]	[3; 5]
		40 2, 3, 4
		10 2, 3, 4
	C	20 2, 3, 4 30 2, 3, 4	[100; 500] [1000; 1500]	[3; 5]
		40 2, 3, 4

Table 3 .

 3 5, Table 3.6 and Table 3.7 show the solution time obtained for each method.

Table 3 . 5 :

 35 Computational results forβ h ∈ [1, 5] Euro

		h)→	2	3	4
		(n)↓ CpuT (s) CpuT (s) CpuT (s)
	CPLEX		0.644	0.505	1.660
	B&B LSS	10	0.006 0.015	0.005 0.013	0.019 0.012
	GA		7.1	7.2	7.3
	CPLEX		53.67	45.31	43.25
	B&B LSS	20	0.046 0.026	0.385 0.031	0.891 0.041
	GA		7.5	7.6	8.1
	CPLEX		144.842 197.274 288.585
	B&B LSS	30	0.221 0.044	1.749 0.064	20.934 0.103
	GA		8.2	8.8	8.2
	CPLEX		420.495 429.103 467.098
	B&B LSS	40	1.785 0.069	40.361 308.997 0.121 0.193
	GA		9.4	10.3	8.6

Table 3 . 6 :

 36 Computational results for β h ∈ [10, 50] Euro constitutes the first part from the objective function (Equation

				CpuT (s) CpuT (s)
	CPLEX		3.439	2.106	4.753
	B&B LSS	10	0.006 0.015	0.006 0.013	0.023 0.012
	GA		7.2	7.5	8.0
	CPLEX		462.669 515.522 474.654
	B&B LSS	20	0.149 0.025	1.133 0.031	6.161 0.042
	GA		7.9	8.1	8.7
	CPLEX		> 3600	>3600	>3600
	B&B LSS	30	1.471 0.045	63.433 0.061	>3600 0.101
	GA		9.1	9.5	8.9
	CPLEX		>3600	>3600	>3600
	B&B LSS	40	24.229 0.068	>3600 0.110	>3600 0.186
	GA		9.3	9.8	10.7

Table 3 . 7 :

 37 Computational results for β h ∈ [100, 500] Euro

	Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery
	Chapter 3				Scheduling Problem
	Class of			Class C
	Problem→
		(h)→	2	3	4
		(n)↓ CpuT (s) CpuT (s) CpuT (s)
	CPLEX		15.208	18.749	29.442
	B&B LSS	10	0.008 0.014	0.008 0.013	0.020 0.013
	GA		7.0	6.9	7.6
	CPLEX		>3600	>3600	>3600
	B&B LSS	20	0.301 0.026	2.882 0.031	32.497 0.036
	GA		7.8	7.8	7.8
	CPLEX		>3600	>3600	>3600
	B&B LSS	30	6.602 0.046	241.455 >3600 0.069 0.110
	GA		8.2	8.5	8.9
	CPLEX		>3600	>3600	>3600
	B&B LSS	40	78.240 0.074	>3600 0.135	>3600 0.213
	GA		8.4	8.9	9.6

  parameters depicted in Table3.6.2, we tested 36 situations of the problem. For each situation, we randomly generated 25 problem instances for the performance test of the GA. The performance results with β h ∈ [1, 5],[10, 50], [100, 500] Euro for three classes respectively

	Multi-Customer with Single-Transporter Integrated Lot Sizing and Delivery
	Chapter 3				Scheduling Problem
	Considering the different Class of			The Error Ratio
	Problem↓		ER=(E GA -E B&B )/E B&B
		(h)→	3	4	5
		(n)↓
		10	0.00% 0.00% 0.00%
	Case A	20 30	0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
		40	0.00% 0.00% 0.00%
		10	0.00% 0.00% 0.00%
	Case B	20 30	0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
		40	0.00% 0.00% 0.00%
		10	0.00% 0.00% 0.00%
	Case C	20 30	0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
		40	0.00% 0.00% 0.00%
	Table 3.9:

  the last and first jobs of batch k, respectively.

	Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery
	Chapter 4	Scheduling Problem

Table 4

 4

	.3, we observe that GDP which is supported

Table 4 . 4 :

 44 Results of instances with heterogeneous transporters with β =[1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF]

			10		20		30
		vehicles(m)↓
		2	0.756	0.027	106.745	0.086	>3600	0.115
	Case B	3	1.098	0.035	402.299	0.11	>3600	8.341
		4	2.417	0.114	>3600	7.204	>3600 100.047

Table 4 . 5 :

 45 Results of instances with heterogeneous transporters with β =

	Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery
	Chapter 4					Scheduling Problem
	Class of		CPLEX	GDP	CPLEX	GDP	CPLEX	GDP
	Problem↓		CpuT (s) CpuT (s) CpuT (s) CpuT (s) CpuT (s) CpuT (s)
		Size(n)→	10		20		30
		vehicles(m)↓
		2	2.511	0.036	>3600	0.133	>3600	0.310
	Case C	3	12.080	0.138	>3600	6.210	>3600	8.517
		4	27.466	2.083	>3600	95.570	>3600 1300.24

Table 4 . 6 :

 46 Comparison of the quality of the solutions found by the GA and the GDP

Table 4 . 7 :

 47 The due dates (d j ) j=1..n are uniformly separated with values randomly generated Chapter 4 Single-Customer with Multi-Transporter Integrated Lot Sizing and Delivery Scheduling Problem from the uniform distribution with range [0, 50]. The transporters costs η h are randomly generated from the uniform distribution with range [100, 250].The storage cost at the manufacturer varies in every case, where β is randomly generated from the uniform distribution with ranges [0.01, 0.05],[1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF] and[10, 50] in the three different cases A, B and C, respectively. For each combination, 25 problem instances are randomly generated and the average Cpu time for both methods of resolution CPLEX solver and the GDPid is calculated and denoted in (Table4.7). Results of small-medium instances with identical transporters

	The results of the MIP model is compared with that of the dynamic programming
	(GDPid ) with the dominance relation of the identical transporters (theorem 3).
	The results are shown in (Table 4.7).
	Class of		CPLEX GDPid CPLEX GDPid CPLEX GDPid
	Problem↓		CpuT (s) CpuT (s) CpuT (s) CpuT (s) CpuT (s) CpuT (s)
		Size(n)→	10		20		30
		vehicles(m)↓
		2	0.093	0.021	3.219	0.041	46.209	0.095
	Case A	3	0.198	0.017	5.264	0.06	48.295	0.134
		4	0.182	0.017	11.807	0.056	49.231	0.105
		Size(n)→	10		20		30
		vehicles(m)↓
		2	0.146	0.019	80.932	0.047	122.657	0.097
	Case B	3	0.807	0.016	135.759	0.051	92.750	0.228
		4	0.977	0.015	>3600	0.078	61.618	0.468
		Size(n)→	10		20		30
		vehicles(m)↓
		2	2.050	0.018	>3600	0.061	>3600	0.188
	Case C	3	23.643	0.025	>3600	0.224	>3600	3.153
		4	73.338	0.029	>3600	0.794	>3600	35.203

Table 4

 4

	.7), with 25, 50, 75 and 100 products, it is called case
	B . Three scenarios are considered, beginning with two transporters in use, then

Table 4 .8:

 4

Table 4 . 9 :

 49 Results of large instances with identical transporters

			GDPid GDPid GDPid	GDPid
	Problem↓		CpuT (s) CpuT (s) CpuT (s) CpuT (s)
		Size(n)→	25	50	75	100
		vehicles(m)↓
		2	0.212	1.157	14.992	24.733
	Case B	3	0.514	28.727 435.240 1152.733
		4	0.738	207.290 >3600	>3600

Table 5 . 1 :

 51 Data for a single-supplier and 2-customers problem , j 2 , j 5 , j 6 , j 8 j 3 , j 4 , j 7 d j {d 1 , d 2 , d 5 , d 6 , d 8 } {d 3 , d 4 , d 7 } {10010, 10015, 10035, 10040, 10050} {10020, 10030, 10050}

	Parameters	Customer 1	Customer 2
	τ ht	11	15
	η ht	16	20
	β j	1	2
	n h	5	3
	j = 1, ..., n	j 1

Table 5 . 3 :

 53 Total computational time for the three classes

	Class A

Table 5 .

 5 3 shows the solution time obtained for each model. illustrate the computational time solution for each model with 3 customers, respectively. As can be seen, increasing the number of jobs in different models leads to increase the time of resolution. During the resolution, CPLEX runs out of memory and could not solve the instances of the general model more than 10 jobs in Case B, and the instances with 20 jobs in models (one trans. to each cust. (p equals to h)) and (homo. Trans. without allotment) in Case B with 3 Transporters. In the Case B with 4 Chapter 5 Multi-Customers/Transporters Integrated Lot Sizing and Delivery Scheduling Problem Transporters, CPLEX could solve the instances with 10 and 15 jobs for the model of homo. Trans. with allotment. Then, in Case C CPLEX runs out of memory with n more than 10 jobs for all the models.

Mots clefs: Modèles intégré; Production et distribution; Distribution et stockage; models intégrés; Planification de la chaîne logistique; Meta-Heuristique; Lots; Programmation dynamique; Methodes de coupe (Séparation et évaluation); Programmation en nombres entiers mixte

Acknowledgments

Acknowledgments

Ariane GLATIGNY for her help with administrative matters.

In the first class (A), η ht is bigger than β j , where η ht and β j are randomly generated from the uniform distribution with ranges [10, 60] and [0.1, 0.5], respectively. In the second class (B), η ht are generated in the same way and with the same distribution with ranges [10, 60] and β j of the first class are multiplied by 10, where β j are randomly generated from the uniform distribution with ranges [1,[START_REF] Hammoudan | A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem[END_REF]. In the third class (C), we kept the same value of η ht and we changed β j by multiplying the ranges of the first class by 100, where β j are randomly generated from the uniform distribution with ranges [10.0, 50.0]. For each class under resolution the number of customers equal to 3, and each case is tested with 3 or 4 transporters. The results of the solution time obtained for each model can be seen in Table 5.3. empirical analysis. International Journal of Production Economics,112(2):919-933.