Warehousing is a key part of supply chain management. It primarily focuses on controlling the movement and storage of materials within a warehouse and processing the associated transactions, including shipping, receiving, and picking. From the tactical point of view, the main decision is the storage policy, that is, to decide where each product should be located. Every day a warehouse receives several orders from its customers. Each order consists of a list of one or more items that have to be retrieved from the warehouse and shipped to a specific customer. Thus, items must be collected by a warehouse operator. We focus on situations in which several orders are put together into batches, satisfying a fixed capacity constraint. Then, each batch is assigned to an operator, who retrieves all the items included in those orders grouped into the corresponding batch in a single tour. The objective is then to minimize the maximum retrieving time for any batch. In this paper, we propose a parallel variable neighborhood search algorithm to tackle the so-called min–max order batching problem. We additionally compare this parallel procedure with the best previous approach. Computational results show the superiority of our proposal, confirmed with statistical tests.