Three-stage hybrid-flowshop model for cross-docking

Adrien Bellanger (1) , Said Hanafi (1) , Christophe Wilbaut (1)

1 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

This paper deals with the optimization of a cross-docking system. It is modeled as a three-stage hybrid flowshop, in which shipments and orders are represented as batches. The first stage corresponds to the receiving docks, the second stage corresponds to the sorting stations, and the third stage corresponds to the shipping docks. The objective of the problem is to find a schedule that minimizes the completion time of the latest batch. In order to obtain good quality feasible solutions, we have developed several heuristic schemes depending on the main stage considered, and several rules to order the batches in this stage. Then, we propose a branch-and-bound algorithm that takes into account the decomposition of the problem into three stages. To evaluate the heuristics and to reduce the tree size during the branch-and-bound computation, we also propose lower bounds. Finally, the computational experiments are presented to demonstrate the efficiency of our heuristics. The results show that the exact approach can solve instances containing up to 9–10 batches in each stage (i.e., up to 100 jobs). In addition, our heuristics were evaluated over instances with up to 3000 jobs, and they can provide good quality feasible solutions in a few seconds (i.e., less than 2 s per heuristic).

Mots clés: Cross-docking; Hybrid flowshop; Batching machines; Heuristic; Branch-and-bound

Domaines: Informatique [cs]

Adrien Bellanger, Said Hanafi, Christophe Wilbaut. Three-stage hybrid-flowshop model for cross-docking. Computers and Operations Research, 2013, 40 (4), pp.1109-1121. ⟨10.1016/j.cor.2012.11.009⟩. ⟨hal-03472230⟩