Solving discrete lot-sizing and scheduling by simulated annealing and mixed integer programming

We consider the discrete single-machine, multi-item lot-sizing and scheduling problem and we propose a Simulated Annealing (SA) approach together with a statistically-principled tuning procedure to solve it. We compare our solver with the state-of-the-art methods based on Mixed Integer Programming (MIP), both on publicly-available instances and on a set of new, more challenging ones. In addition, we propose a hybrid SA/MIP method that combines the advantages of the pure methods on the challenging instances. The outcome is that our solver is able to find near-optimal solutions in short time for all instances, including those that are not solved by MIP methods. Instances and solutions are made available on the web for inspection and future comparisons.