Paper Info
Title
The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability
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 (SA) heuristic is suggested for solving the DLSP in the case of batch availability. Numerical results are presented for different problem classes.
Year
DOI
Venue
2000
10.1016/S0377-2217(99)00190-3
European Journal of Operational Research
Keywords
Field
DocType
Manufacturing,Scheduling,DLSP,Batch availability,Complexity,Simulated annealing
Simulated annealing,Mathematical optimization,Heuristic,Job shop scheduling,Scheduling (computing),Computer science,Context of computational complexity,Schedule,Sizing,Linear programming,Operations management
Journal
Volume
Issue
ISSN
124
3
0377-2217
Citations 
PageRank 
References 
9
0.71
7
Authors
2
Name
Order
Citations
PageRank
Wolfgang Brüggemann1101.05
hermann jahnke2353.77