یک روش برنامه ریزی پویا محدود به عملیات های برنامه در یک پلت فرم اتصال متقابل

Cross docking is a logistic technique employed to reduce the inventory holding, order picking, transportation costs as well as the delivery time. Products arriving to the cross dock are unloaded from inbound trailers, possibly reconsolidated with other products arriving from different destinations and loaded into outbound trailers within less than 24 h. In this study, we consider a multiple receiving and shipping door cross dock environment. The objective is to find optimal (for reasonably small cross docks) or near optimal (for larger cross docking facilities) scheduling policies which minimizes the total costs related to the transshipment operations at the facility.

A platform of cross docking is a consolidation point of inbound products and offers short cycle times. Materials arriving to the cross dock from suppliers are unloaded from the inbound trailer, sorted according to their destinations, possibly consolidated with other products to the same destination and reloaded into an outbound trailer within less than 24 h. Therefore, this technique is mainly used in the transportation industries or in the distribution of the perishable products. In the literature on cross docking, we can find studies dealing with problems either on the strategical or the operational level. The solutions for strategical problems often require an investment and the decisions taken are not frequently modifiable. For instance cross dock network design (see Chen et al., 2006, Donaldson et al., 1998 and Ratliff et al., 1998) or the layout of cross docking platforms (see Bartholdi and Gue, 2002, Bartholdi and Gue, 2004 and Gue, 1999) make part of this category of problems. The problems which are handled in the operational level are mainly on the real-time control of the cross docking platforms and hence the decisions are modified on a real-time basis. In this category of problems, we can cite the dock assignment problems, the objective of which is the assignment of inbound and outbound trucks on the docks in order to optimize a criterion (see Tsui and Chang, 1990 and Tsui and Chang, 1992 for the minimization of the weighted distance between inbound and outbound trucks; see (Bartholdi & Gue, 2001) for the minimization of the congestion within the cross docking platform.) Scheduling of transshipment operations inside the cross docking platforms are also in this group of problems (see Alpan et al., 2008, Baptiste and Maknoon, 2007, Baptiste et al., 2007, Boysen, 2009, Boysen et al., 2008, Chen and Lee, 2009, Chen and Song, 2009, Larbi et al., 2007, Larbi et al., 2009, McWilliams et al., 2005, Sadykov, 2009, Song and Chen, 2007 and Yu and Egbelu, 2008). These recent studies seek to find the best schedule of trucks so that either the time or the cost related performance measures of the cross dock is optimized. Among these studies, (Baptiste and Maknoon, 2007, Baptiste et al., 2007, Boysen et al., 2008, Chen and Lee, 2009, Larbi et al., 2007, Sadykov, 2009 and Yu and Egbelu, 2008) consider the case where there is a single receiving and a single shipping dock. These studies give interesting insights on the solution structure for scheduling problems at the cross docking facilities, however no practical application is possible. In practice a cross docking facility has several receiving and shipping docks. The largest facilities can have several hundreds of docks. Therefore, for implementation purposes, it is important to study the multi door cross docking settings. To the best of our knowledge, the scheduling problems in multi door cross docks are studied in Alpan et al., 2008, Boysen, 2009, Chen and Song, 2009, Larbi et al., 2009, McWilliams et al., 2005 and Song and Chen, 2007. Chen and Song (2009) presents the cross docking scheduling problem as a two-stage flow shop problem with parallel machines. Each stage corresponds to either inbound or outbound side of a cross dock, the machines and the set of jobs are analogous to inbound or outbound docks and the trucks to unload or load, respectively. Indeed, this analogy was first established by Chen and Lee (2009) where each stage of the problem contained only a single machine (i.e. single inbound and outbound dock). They show that the problem is NP-hard in the strong sense. An extended version is proposed by Chen and Song (2009). In this later study, at least one of the stages is allowed to have more than one machine. In these studies, the objective is to find the best schedule of inbound and outbound trucks so that the makespan of operations is minimized. The same authors have studied a similar, yet simplified version of the same scheduling problem in Song and Chen (2007). The industrial context may impose specific constraints on the cross docking operations. McWilliams et al., 2005 and Boysen, 2009 hence consider some specific industrial settings. McWilliams et al. (2005) present the parcel hub scheduling problem common in parcel delivery industries such as the postal services. The objective of this study is very similar to the scheduling problems in multi door cross docking facilities, i.e. finding the best schedule of inbound trucks so that the makespan of the parcel transfer operations is minimized. However, the environmental setting has some specificities. One of the characteristics of a parcel hub compared to a classical cross docking platform is the type of materials handling system utilized. In a parcel hub, the flow of the materials is supported by a network of fixed conveyor belts. Temporary storage of pallets are not considered. The main focus is on the congestion of the fixed conveyor belts by the untimely unloading of the incoming parcels. Therefore, we consider the parcel hub scheduling as a special case of cross docking. Another special case is studied in Boysen (2009) for a food industry cross docking facility. In this case, the inventory holding is strictly forbidden. The author presents a dynamic programming approach as well as heuristics based on simulated annealing to schedule the inbound and outbound trucks. Three time-related objective functions are considered: minimization of total processing time, total flow time and the total tardiness. The current article is an extended version of a previous study presented at the 38th International Conference on Computers and Industrial Engineering (Alpan et al., 2008). The cross docking environment under study is a multi receiving and shipping dock setting. In this paper, similar to the above presented literature, we would like to determine the best schedule of outbound trucks which should be present at the shipping doors at any given time, given a known sequence of inbound truck arrivals. Our problem differs from the previous work in two aspects: (i) In all of the previous work, the objective function is a time-related one, such as the minimization of makespan, or total tardiness. This is rather classical in scheduling and is an indirect way of considering operational costs. In this paper, we will directly focus on operational costs related to temporary storage of merchandize inside the cross dock and the costs related to pre-emption of loading operations at the docks. (ii) The second difference comes from the problem structure. Here we allow, pre-emption of loading operations which is not allowed in previous work. Furthermore, we explicitly model the temporary storage, which is either forbidden or not modeled explicitly in the existing literature on multi dock cross-dock scheduling problems. We note that in practice, temporary storage or pre-emption are solutions to increase the flexibility of cross docking operations. The rest of the article is organized as follows. In Section 2 we will give a detailed description of the problem with the basic assumptions and the related input data to the problem. In Section 3, we will briefly present the dynamic program used for the resolution as well as some properties taken into consideration during the resolution phase (Alpan et al., 2008). This section will also include the performance limits of the DP model illustrated by numerical results. Section 4 is dedicated to the presentation of some bounds on the DP model in order to reduce its complexity. Performance of the resultant bounded dynamic programs are illustrated by numerical experiments in Section 5. And finally concluding remarks are given in Section 6.

In this article, we proposed a bounded dynamic programming approach to schedule the internal operations in a cross docking facility. The contributions are two-fold. First of all, using dynamic programming technique, we propose an optimal truck schedule to minimize the cost of operations in a multiple-dock cross docking facility. Secondly, we have seen through experimental results that by generating intelligent bounds, we can solve scheduling problems much faster than a classical DP model without much degrading the solution. This opens up new possibilities for scheduling of internal operations in larger cross docking facilities. The numerical results on bounds have shown that the parameters of bounding procedures affects considerably the final solution. For instance, in the case of H stock, the procedure seems to be well performing when 0.2 ⩽ α ⩽ 0.3. On the other hand for View the MathML sourceHnodesβ, β ⩾ 0.7 seems to be not very restrictive for certain cases. Unfortunately, it is difficult to provide a general procedure or closed-formula which give the best or most reasonable parameter values. Indeed, α and β are very much dependent on the input data. We believe that these parameters can be included in a long term decision process. Usually, the global flow of materials (e.g. number of pallets per hour or day) which can be handled and/or usually handled are known. Based on historical data, the supervisor can use our method, to observe a window of best performing α and β values specific for their platform. These parameters can then be used on a real-time basis. New bounding procedures can also be tested. As we have explained in Section 4.1, set of outbound destinations Z t contributes to the complexity of the problem as well. We may impose, for instance, f destinations to be already present in the set Z t depending on the density of products in a portion of the input sequence. Such a procedure, will put a bound on the number of nodes generated since the possible combinations for Z t will be C (D − f , O − f ), instead of C (D , O ). Similarly, hybrid bounds may be tested such as View the MathML sourceHstock+Hnodesβ. Finally, in this study, we have considered that input sequence is fixed. It will be interesting to allow a flexible input sequence. That is, the supervisor has the possibility to reschedule the inbound trucks. To this end, the techniques developed in this paper can be combined with some metaheuristics which modify the input sequence. We believe that, this may considerably reduce the solution space generated by the DP model.