Scheduling Internal Operations in Post-Distribution Cross Docking Systems

This paper deals with the novel and complex problem of scheduling the internal operations in post-distribution cross docking systems (PDCDSs), i.e., a kind of cross docking terminal where the operations of good allocation are performed. More precisely, internal operations of the PDCDS consist in deconsolidating inbound cases, sorting products according to customer requests, and consolidating outbound cases. The problem is determining the optimal schedule of the internal operations with the objective of minimizing the makespan. The contribution of this paper is twofold. First, the PDCDS scheduling problem is characterized and the corresponding NP-hardness is proved. Second, in order to address the complexity of the problem, two mixed integer linear programming (MILP) models and a heuristic algorithm are presented. In particular, the mathematical programming formulations are solved by using symmetry breaking constraints and objective function perturbations. Moreover, the lower bounds of the start times of operations are evaluated in order to strengthen the formulations. A set of test results compare the formulation performances and a case study shows the effectiveness of the proposed heuristic algorithm to schedule the operations of an half work day of an Italian company of cloth retail stores.