  The two-dimensional non-oriented bin packing problem with due dates packs a
set of rectangular items, which may be rotated by 90 degrees, into identical
rectangular bins. The bins have equal processing times. An item's lateness is
the difference between its due date and the completion time of its bin. The
problem packs all items without overlap as to minimize maximum lateness Lmax.
  The paper proposes a tight lower bound that enhances an existing bound on
Lmax for 24.07% of the benchmark instances and matches it in 30.87% cases. In
addition, it models the problem using mixed integer programming (MIP), and
solves small-sized instances exactly using CPLEX. It approximately solves
larger-sized instances using a two-stage heuristic. The first stage constructs
an initial solution via a first-fit heuristic that applies an iterative
constraint programming (CP)-based neighborhood search. The second stage, which
is iterative too, approximately solves a series of assignment low-level MIPs
that are guided by feasibility constraints. It then enhances the solution via a
high-level random local search. The approximate approach improves existing
upper bounds by 27.45% on average, and obtains the optimum for 33.93% of the
instances. Overall, the exact and approximate approaches identify the optimum
for 39.07% cases.
  The proposed approach is applicable to complex problems. It applies CP and
MIP sequentially, while exploring their advantages, and hybridizes heuristic
search with MIP. It embeds a new lookahead strategy that guards against
infeasible search directions and constrains the search to improving directions
only; thus, differs from traditional lookahead beam searches.
