Warehousing has been found as an essential issue by the industry in the last few years, being a key part of the supply chain management. It mainly focuses its attention on moving and storing materials in warehouses by performing different activities such as shipping, receiving, and picking operations. The profits obtained by warehouse management systems strongly depends on how customer orders, containing a set of goods, are collected. This picking process consists in collecting goods (items) before shipment to satisfy the orders of the customers. The Order Batching and Sequencing Problem (OBSP) involves the process of collecting orders in a warehouse by grouping orders into batches with a maximum fixed capacity. In the context of the OBSP, each order has a certain due date, i.e., it must be collected before a specific time. Otherwise, it has associated a tardiness penalty. The problem then consists in grouping orders into batches, sequencing the batches and finding a route to collect each batch, in such a way that the total tardiness is minimized. In this paper we propose a heuristic approach based on the Variable Neighborhood Search methodology to address the problem. Additionally, we provide an extensive experimental comparison between our procedure and the best previous method found in the related literature. The experimentation reveals that our algorithm improves the state of the art in both, quality and computing time. This fact is finally confirmed by non-parametric statistical tests.