The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability

The discrete lot-sizing and scheduling problem (DLSP) has been suggested for the simultaneous choice of lot sizes and production schedules. In the context of computational complexity, it turns out that literature results for the DLSP are incorrect. Therefore, we prove that the decision version of the DLSP is NP-hard in the strong sense. The common assumption of instantaneous availability of the manufactured units is not satisfied in practice if the units arrive in inventory only in one batch after the whole lot has been completed. Therefore, additional constraints are presented for this case of batch availability on a single machine. The resulting modified DLSP is formulated as a mixed-integer linear program. This problem can be shown to be NP-hard again using ideas similar to the item-availability case. Hence, a two-phase simulated-annealing heuristic is suggested for solving the DLSP in the case of batch availability. Numerical results are presented for different problem classes.