The vertical lift module is an automated storage and retrieval system widely used in warehouses. The performance of a warehouse with vertical lift modules is highly correlated with the efficiency of the order picking. Order batching, namely regrouping customers’ orders into batches to be collected from the module, constitutes a critical decision impacting the picking efficiency. In this paper, we provide optimization models for order batching, with the objective of minimizing total completion time, that is, the time required to collect a given set of customers’ orders. We first consider the case of one vertical lift module and then extend our approach to study a warehouse with several modules. We use real data from two companies operating in different sectors in order to test and validate our models. Numerical experiments show that our models perform much better than the batching method currently used by these companies. For complex cases that cannot be solved within a reasonable timeframe with Cplex, we develop a metaheuristic approach, which generally yields very good solutions in less than one minute. This paper investigates problems that are firmly grounded in practice. Our batching models and metaheuristic approach have been implemented in practice and are currently used by some companies.