OPTIMISATION DES SEQUENCES DE CHARGEMENT D’UNE CHAINE LOGISTIQUE ELEMENTAIRE PAR SEPARATION ET EVALUATION

30/09/2017
Publication e-STA e-STA 2004-3
OAI : oai:www.see.asso.fr:545:2004-3:20055
DOI :

Résumé

OPTIMISATION DES SEQUENCES DE CHARGEMENT D’UNE CHAINE  LOGISTIQUE ELEMENTAIRE PAR SEPARATION ET EVALUATION

Métriques

11
5
109.36 Ko
 application/pdf
bitcache://4a0244676d98c8f4b7a1251ed3cc213cae6b69e4

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2004-3/20055</identifier><creators><creator><creatorName>S.E. Merzouk</creatorName></creator><creator><creatorName>O. Grunder</creatorName></creator><creator><creatorName>M. El Bagdouri</creatorName></creator></creators><titles>
            <title>OPTIMISATION DES SEQUENCES DE CHARGEMENT D’UNE CHAINE  LOGISTIQUE ELEMENTAIRE PAR SEPARATION ET EVALUATION</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 30 Sep 2017</date>
	    <date dateType="Updated">Sat 30 Sep 2017</date>
            <date dateType="Submitted">Tue 15 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">4a0244676d98c8f4b7a1251ed3cc213cae6b69e4</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34072</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

OPTIMISATION DES SEQUENCES DE CHARGEMENT D’UNE CHAINE LOGISTIQUE ELEMENTAIRE PAR SEPARATION ET EVALUATION. A BRANCH & BOUND PROCEDURE TO OPTIMIZE LOADING SEQUENCES OF A SIMPLE SUPPLY CHAIN UNDER APERIODIC DEMAND S.E. Merzouk, O. Grunder and M. El Bagdouri Laboratory S.e.T. University of Technology Belfort Montbéliard, France UTBM, site de Belfort 90000, Belfort Cedex. Phone : +33(0)3 84 58 33 19 Fax : +33(0)3 84 58 3342 {salah-eddine.merzouk, olivier.grunder, mohammed.elbagdouri}@utbm.fr Résumé : L’objectif de cet article est de proposer une procédure exacte pour optimiser l’ordonnancement des livraisons de lots d’une chaîne logistique dans un contexte de juste à temps. Ce problème est caractérisé principalement par le fait que les produits doivent être livrés chez le client avant leurs dates dues et aussi tard que possible. Quelques propriétés mathématiques intéressantes sont démontrées pour ce problème dans le cas où un seul transporteur livre les biens. Ces résultats particuliers sont ensuite utilisés pour accélérer de façon considérable la recherche de la solution optimale par une procédure appropriée de séparation évaluation progressive. Des résultats expérimentaux comparatifs illustrent l’efficacité de l’algorithme proposé. Abstract: The purpose of this paper is to propose an exact procedure to optimize the lots delivery scheduling in a simple supply chain under just in time sitting. This problem is mainly characterized by the fact that the products have to be delivered to the customer before given due dates and as late as possible. Some interesting mathematical properties are given for this problem in case of there is a single transporter to deliver the goods. These results greatly improve the search of the optimal solution by an appropriate branch and bound procedure. Comparative experimental results illustrate the efficiency of the proposed algorithm. Keywords: optimal load flows, optimization problem, scheduling algorithm, optimal control, synchronization, transportation control, tree search. 1. INTRODUCTION The Supply Chain can be defined as a set of actors (suppliers, producers, distributors…) which contribute to manufacture, sale and provision of finished products for the customers. The logistic is the management of business operations, such as the acquisition, storage, transportation and delivery of goods along the supply chain. In today’s increasing global and competitive marketplace, it is imperative that members of supply chain work together in an effort to minimize overall times and costs of production and transportation (F.E. Vergara & al, 2002). Thus, the problem of optimization production and transport sequences was largely studied these last years. Indeed, the Economic Lot and delivery Scheduling Problem (ELDSP) was studied by (J. Hahm & C. A Yano, 1992) and an extension of the problem is introduced to hold account the capacity of the transporter. The purposed model was also used in (F.Elizabet Vergara et al., 2002). They generalized this model to a linear supply chain (customers and suppliers in cascade) and they developed a genetic algorithm to find the best scheduling sequence of various products flows through the production line. (M. Khouja, et al. 1998) also used the genetic algorithms to solve the sequences of production scheduling problem of several products in the same production line. In (M.A Hoque & S.K Goyal, 2000), a delivery policy of batches with equal and non equal sizes was developed under a constant demand. (S.Y Chou & S.L Chang, 2001) developed heuristics to find the minimal cost in the context of only one order of production and several deliveries. A dynamic programming was introduced by (K. H Kim & J. B Kim, 2002) in order to select a model for trucks transporting components between two members of logistic chain. However, all of this research maintained the assumption of a deterministic and constant logistic demand. In (I. Elmahi, et al., 2002), a max-plus algebra based model is proposed to control a simple supply chain under the assumption that the load sequence of the transporter is given. If the load sequence become an input variable of the model, all the possible load sequences have to be considered to find the optimal one. The purpose of this paper is to propose an exact procedure to optimize the lots delivery scheduling in a simple supply chain under just in time sitting. The main contribution of this work is to demonstrate some interesting mathematical properties for this problem in case of there is a single transporter to deliver the goods. These results greatly improve the search of the optimal solution by an appropriate branch and bound procedure. This paper is organized as follow: In section 2, we present the studied system and the constraints related to its dynamic. The mathematical model of this system and its properties are provided in section 3. We propose in the following section an efficient Branch and Bound Procedure to find the optimal solution of the studied problem. Comparative experimental results show the efficiency of the proposed algorithm in section 5. Section 6 wraps up the paper with conclusions and perspectives 2. PROBLEM STATEMENT The system studied in this work is a simple supply chain made up of three actors: one supplier, one customer and one transporter (Fig. 1). The customer needs a number of products which must be available in its stock at given due dates, that is to say that the products can arrive eventually earlier compared with their due dates but never later. The products are manufactured by the supplier who has to respect the requirements of the customer. Once manufactured, they can be transported from the supplier toward the customer by the transporter. Several parameters characterize the transporter such as the capacity of loading, the travel duration between the customer and the supplier and the loading time and unloading time of each product from the transporter. Fig. 1. The studied system. The purpose of this study is to optimize the lots delivery scheduling in this chain under just in time sitting. This problem is mainly characterized by the fact that the products have to be delivered to the customer before given due dates and as late as possible. Under these assumptions, one has to find the optimal lot sequence that minimizes the global advance of the products, that is to say the sum of the differences between the due date and the real arrival date for all products. The following section gives a mathematical model of this system and its properties. 3. MATHEMATICAL MODEL The notations used in this paper are given as follows: • np : total number of the requested products • max ch : loading capacity of the vehicle. • g t : travel duration from supplier to customer. • r t : time duration to return back at the supplier. • r g t t T + = : transport time. • l t : loading time per product. • u t : unloading time per product. • d Y : vector of due dates, where : ( ) ( ) np k k y Y d d L , 1 , = = ) (k yd : the due date of the th k product. • r Y : vector of the real arrival dates, where: ( ) np k k y Y r r L , 1 , ) ( = = ) (k yr : the real arrival date of the th k product. If the th k and th k 1 + products are in the same lot, we have: u r r t k y k y + = + ) ( ) 1 ( • p s : partial sequence for the last p products. { } k p p p p s s s s , , , 2 1 L = i p s : number of loaded products in the th i lot of p s . • ( ) p g s A : the global advance of the partial sequence p s • ( ) p av s A : the average advance of the partial sequence p s 3.1 Definitions Definition 1: We define a loading sequence np s as a series ( ) np i i np s , 1 = which satisfies: a) [ ] max 0 , , 1 ch s np i i np ≤ ≤ ∈ ∀ . b) [ ] ( ) ( ) 0 , 0 , 1 = > ∀ ⇒ = ∈ ∃ j np i np s i j s np i c) np s np i i np = ∑ =1 . Definition 2: A partial sequence p s is a sequence of p products such as np p < . The products of any partial sequence always correspond to the last ones required by the customer. Thus, the first product of the partial sequence p s corresponds to the product 1 + − p np needed by the customer. Definition 3: The global advance of a given partial sequence is defined as the sum of the differences between the due date and the real arrival date for all products. ( ) ( ) ( ) ( ) ∑ + − = − = np p np k r d p g k y k y s A 1 Definition 4: The average advance for a given partial sequence p s is defined as: ( ) 1 ) ( + + = p A s Ag s A b p p av with: ( ) ( ) ( ) [ ] l p u r d b t s t T p np y p np y A . 1 1 − − − + − − − = The next section provides the expressions of the real arrival dates for each product and a proposition to compare partial sequences of this problem. 3.2 Model analysis We first formulate the real arrival dates of the last lot of a partial sequence with the following lemma. Lemma 1 Given a partial sequence p s , the real arrival date of the first product of the last lot is: [ ] u k p r s i k p r t i i s np y s np y k p × − − + − = + − = ) 1 ( ) ( min ) 1 ( 1 Proof: The real arrival dates of the last lot have to satisfy: ( ) ( ) ( ) ( ) ( ) ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ + − ≤ + − + − ≤ + − np y np y s np y s np y s np y s np y d r k p d k p r k p d k p r M 2 2 1 1 ( ) ( ) ( ) ( ) ( ) ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ ⋅ − + + − + − ≤ + + − + − ≤ + − ⇒ np y t s s np y s np y t s np y s np y s np y d u k p k p r k p d u k p r k p d k p r ) 1 ( 1 2 1 1 1 M Consequently, we have: ( ) ( ) ( ) ( ) ( ) ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ⋅ − − ≤ + − − + − ≤ + − + − ≤ + − u k p d k p r u k p d k p r k p d k p r t s np y s np y t s np y s np y s np y s np y ) 1 ( 1 2 1 1 1 M [ ] u k p d s i k p r t i i s np y s np y k p × − − + − ≤ + − ⇒ = ) 1 ( ) ( min ) 1 ( 1 The real arrival dates of other products in this lot are obtained by adding the unloading time u t . From this result, we give the expression of the real arrival dates of the previous lots in the following lemma: Lemma 2 Given a partial sequence { } k p p p p s s s s , , , 2 1 L = , the real arrival date for the 1st product in j p s (j This means that: ( ) ( ) ( ) ( ) p g g p s s A q A s q ' , * > ∈ ∀ ζ The sequence ( ) p s s ' * is made up of two parts: the first one is the partial sequence p s' . The second one is another partial sequence which composed of lots i p np sc − necessary to satisfy the total request of the customer (fig 2). We note this last one p np sc − with { } l p np p np p np p np sc sc sc sc − − − − = , , , 2 1 L . Fig. 2. loading sequence ( ) p s s ' * . We complete the partial sequence p s with the partial sequence p np sc − as shown in figure 3. We note this obtained sequence np r . Fig. 3. Completion of partial sequences. The lemma 3 applied to np r and ( ) p s s ' * gives: [ ] ( ) ( ) i y i y p np i r r ' , , 1 ≥ − ∈ ∀ Then: ( ) ( ) ( ) ( ) i y i y i y i y r d r d ' − ≤ − ( ) ( ) ( ) ( ) ( ) ( ) ∑ ∑ − = − = − ≤ − ⇒ p np i r d p np i r d i y i y i y i y 1 1 ' ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) p g np g p g p np i r d p g p np i r d s s A r A s A i y i y s A i y i y ' ) ( ' ' * 1 1 < ⇒ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ + − ≤ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ + − ⇒ ∑ ∑ − = − = The last inequality means that we find one sequence belonging to ( ) p s ζ whose the global advance is smallest than ( ) ( ) p g s s A ' * . Hence, the assumption of ( ) ( ) ( ) ( ) p g p g s s A s s A ' * * > was false. Consequently, we have: ( ) ( ) ( ) ( ) p g p g s s A s s A ' * * ≤ The mathematical model given above allows to compute the latest real arrival dates for a given sequence. If the load sequence become an input variable of the model, all the possible load sequences have to be considered to find the optimal one. As the size of problem increases exponentially with the number of products, it becomes impossible to explore all search space. We propose in the following section, a Branch and Bound procedure based on the above results which allows, in addition, to find the optimal sequence in very reducing time. 4. BRANCH AND BOUND PROCEDURE The BBP belongs to the exact resolution methods which thus guarantee the optimality of the found solution. The BBP has techniques to detect the failures as soon as possible and thus obtaining a considerable gain in computing time. It allows to reduce the search space by an implicit enumeration of complete branches of tree search (Hao J.K, et al., 1999). The tops of the tree search correspond to subsets which are divided into levels. There is only one top with level zero which represents the root of the arborescence. A minimal evaluation of the branch (called limit) is needed to construct the tops of the other levels. Otherwise say, all the other tops which obtained from the current node will have an evaluation greater or, at best, equal to this limit. The BBP is based on two elementary techniques which act considerably on the quality and the speed of the algorithm: The first one is the evaluation of the solution during its construction. The second one is the separation which consists in stopping the construction of a solution as soon as the evaluation of this last one become greater than the limit evaluation. The loading sequences optimization problem can be modelled in the shape of tree search. Each node models the quantity of products loaded in a given lot. With each node, we associate an evaluation corresponding to the advance of the partial sequence of products delivered until this top. The algorithm has to be able to stop as soon as possible the construction of a branch which will end inevitably to a bad solution. The proposition 1 is used by the developed BBP to explore the search arborescence and find the optimal loading sequence. In following section, we explain how the BBP proceeds to choose the best lot among the various possibilities in the same level. 4.1 Branching scheme The search arborescence holds at most np levels corresponding to the maximal number of trips necessary to satisfy the customer request. In each level, all the nodes that correspond to the various possibilities of loading remaining products, are considered. Thus, the first level of tree contains 1 n nodes where ( ) max 1 , min ch np n = . These nodes correspond to the last lot in the sequence. In the next levels, the number of nodes depends of the path from the root node to the parent node of the previous level. So on, in each level, the number of choices is calculated using: ( ) max , ' min ch np n j j = with ∑ − = − = k j l l np j s np np 1 ' For the last lot, we have to select among a set of nodes the best one. Thus, the corresponding average advance is calculated for each loading. This advance is computed using definition 4. Hence, the selected loading is the one with the smallest average advance. The following bounding scheme is used by the BBP to stop the exploration of a given branch. It is based essentially on the proposition 1 given above. 4.2 Bounding scheme If the choice of the last lot is equal to k np s , the best partial sequence to deliver the last k np s products is to group them in the same lot. Indeed, to calculate the average advance for a given partial sequence, we need to calculate the global advance for this partial sequence and then, the real arrival date for product preceding the sequence. In proposition 1, we have proved that for a same number of products, the partial sequence with the smallest global advance and greatest real arrival date will give inevitably the optimal solution. Thus, it is not necessary to explore the other possibilities for the same number of products. Otherwise say, this partial sequence is the best manner to deliver that number of products. Once the last loading is chosen, we obtain with the same manner the previous loading. The different average advances for the partial sequences k np k np s s − −1 are computed where 1 − k np s is the different possibilities of loading remaining products ( ) [ ] max 1 , min , 1 ch s np s k np k np − ∈ − . And so on, all the other previous lots are obtained. During the exploration of tree search, the best partial sequence of each number of products is registered. The best global advance and the latest real arrival dates are compared with the global advance and real arrival date of the current branch. If they not satisfy the two conditions of the proposition 1, the exploration of this branch will stop immediately. Otherwise, the current branch becomes the new best partial sequence. So on, we obtain the best loading sequence for all products. To explain this scheme, the following example is given: Let to deliver 8 products ( 8 = np ) from the supplier to the customer. The vehicle capacity is 5 max = ch and the vector of due dates is: { } 132 , 131 , 130 , 122 , 120 , 102 , 101 , 100 = d Y The temporal parameters are: 1 , 10 5 = = = ⇒ = = u l r g t t T t t We start by finding the last lot. So, the supplier can deliver 1, 2, 3, 4 or 5 products. For 1 product, the real arrival date is 132 ) 8 ( = r y , then, the average advance is: ( ) ( ) ( ) ( ) [ ] 2 . 8 7 ) 1 ( 1 l u r d av t t T y y Ag A − − − − + = ( ) ( ) [ ] 5 . 5 2 1 1 10 132 131 0 1 = − − − − + = av A Thus, in the same manner, we obtain the following table 1: Table 1 global and average advance for the different sizes of the last lot. We conclude that the best manner to deliver the last three products is to take them on the same lot. Then the last trip is equal to 3. Products number Real arrival dates Global advance Average advance 2 132 ) 8 ( 131 ) 7 ( = = r r y y 0 4 3 132 ) 8 ( 131 ) 7 ( 130 ) 6 ( = = = r r r y y y 0 1.5 4 125 ) 8 ( 124 ) 7 ( 123 ) 6 ( 122 ) 5 ( = = = = r r r r y y y y 21 6.8 5 124 ) 8 ( 123 ) 7 ( 122 ) 6 ( 121 ) 5 ( 120 ) 4 ( = = = = = r r r r r y y y y y 25 3.8 In the previous trip, we repeat the same process to calculate the number of loaded products. The selected partial sequence is 3 2 − and the average advance corresponding is ( ) 66 . 1 3 2 = − av A . So on, we find finally that the best sequence to deliver the 8 products is 3 2 3 − − . The global advance for this sequence is 11 ) 3 2 3 ( = − − g A . The following figure 4 resumes the different leafs explored by the BBP and the corresponding average advance for each one. Fig. 4. Explored nodes for the example. We see that we didn’t explore all possibilities in each level. Indeed, the average advance for each leaf allows algorithm to choice the way to follow during the exploration of tree search. The proposition 1 makes it possible to stop the construction of a given branch as soon as its evaluations end inevitably to a bad solution. 5. EXPERIMENTAL RESULTS To test the performance of the developed BBP, we have considered several problems with different sizes and different parameters. For each problem size, 10 problem instances with different data ( ,... , max T ch ) are generated. The minimum, the maximum and the average computation times of the branch and bound algorithm are reported in the table 2, as well as the computation time needed for an enumeration procedure. Table 2 Average run time for enumeration procedure and BBP. Run time BBP Products number Min time Max time Average time BBP 20 15 ms 16 ms 15 ms 30 ms 30 15 ms 16 ms 15 ms 14 mn 48sec 40 15 ms 32 ms 20 ms >1 day 50 15 ms 47 ms 25 ms >150 days 80 31 ms 157 ms 88 ms > 8.105 yrs 100 47 ms 1.15 sec 250 ms > 109 yrs 200 187 ms 46.4 sec 16.7 sec > 1029 yrs 300 2.12 sec 1.2min 34.5 sec > 1049 yrs Note that these results are obtained with a computer which has a P4 processor with a frequency equal to 2.66GHz. In addition, it is interesting to note the difference between running time of the BBP as opposed to the enumeration procedure. As the table shows, as the problems become larger, the BBP quickly becomes much faster than the enumeration procedure. For example, for 40 products, the BBP took on average 20 ms versus more than one day for the enumeration procedure. However, we note that the running time for a given number of products differs of a problem to another. It is explaining by the fact that data ( ,... , max T ch ) differ of a problem to another. This BBP is also applied to problem with large size in order to find the limit of the procedure. We find that problems of 1000 products can be resolved easily by this BBP. The running time to find the optimal solution is very tolerable. That time which borders 48mn 11sec is roughly the same one as that carried out by heuristics like the "genetic algorithms" to find an approached solution. 6. CONCLUSION In this paper, we have proposed a very efficient optimization procedure for the lots delivery scheduling problem in a simple supply chain under a just in time criterion. This problem is mainly characterized by the fact that the products have to be delivered to the customer before given due dates and as late as possible. Under these assumptions, one has to find the optimal lot sequence that minimizes the global advance of the products. Some interesting mathematical properties are given for this problem which act considerably on the speed of the algorithm. Indeed, these results applied to a branch and bound procedure, allow to find the optimal solution of this problem in a very reducing computing time. We have provided some comparative experimental results which illustrate the efficiency of the proposed algorithm. Indeed, this BBP open the field to ensure the exactitude of the found solution of problems with large size. However, this study has to be generalized to take in account supply chains with several suppliers and customers and large fleet of transporters. The transport, the loading, the unloading and the holding costs has also to be integrated in the evaluation function. REFERENCES Chou S.Y, Chang S.L & Yang W.D (2001). Optimal multiple delivery schedule for demand in logistic model. Int. Journal of production Economics. Vol 73, p 241 – 249. Elizabet Vergara F., Khouja M.& Michalewicz Z. (2002). An evolutionary algorithm for optimizing material flow in supply chains. Computers & Industrial Engineering. Vol 43 p 407 – 421. Elmahi I., Grunder O. & Elmoudni A. (2002). A Petri net approach for the evaluation and command of supply chain using the Max-Plus algebra. Proceedings of the 2002 IEEE International Conference on Systems, Man and Cybernetics. 6-9 October 2002, IEEE SMC 2002. Tunisie. Hahm, J and Yano C. A. (1992). The economics lot delivery scheduling problem: The single item case. Int. Journal of production Economics. 28. pp 235-252. Hao, J. K Galinier, P., Habib M. (1999). Méthaheuristiques pour l’optimisation combinatoire et l’affectation sous contraintes. Revue d’Intelligence Artificielle. Hoque, M.A and Goyal, A. (2000). An optimal policy for a single-vendor single-buyer integrated production-inventory system with capacity constraint of the transport equipment. Int. Journal of production Economics. 65. pp 305- 315. Kim, J.B and Kim K.H. (2002) Determining load pattern for the delivery of assembly components under JIT systems. Int. Journal of Production Economics. 77. pp 25-38. Khouja M., Michalewicz Z., Wilmot M. (1998). The use of genetic algorithms to solve the economic lot size scheduling problem. European Journal of Operation research. Vol 110. p 509-524. ACKNOWLEDGMENTS A first version of this paper was published at IFAC Workshop on Discrete Event Systems, WODES'04, 22-24 September 2004.