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

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

0.00 Avg rating0 Votes
Article ID: iaor20011138
Country: Netherlands
Volume: 124
Issue: 3
Start Page Number: 511
End Page Number: 528
Publication Date: Aug 2000
Journal: European Journal of Operational Research
Authors: ,
Keywords: combinatorial analysis, optimization: simulated annealing
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.