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

Brüggemann W, Jahnke H (2000)
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 124(3): 511-528.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Brüggemann, W; Jahnke, HermannUniBi
Abstract / Bemerkung
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. (C) 2000 Elsevier Science B.V. All rights reserved.
Stichworte
manufacturing; DLSP; batch availability; complexity; simulated annealing; scheduling
Erscheinungsjahr
2000
Zeitschriftentitel
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Band
124
Ausgabe
3
Seite(n)
511-528
ISSN
0377-2217
Page URI
https://pub.uni-bielefeld.de/record/1619805

Zitieren

Brüggemann W, Jahnke H. The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. 2000;124(3):511-528.
Brüggemann, W., & Jahnke, H. (2000). The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 124(3), 511-528. doi:10.1016/S0377-2217(99)00190-3
Brüggemann, W., and Jahnke, H. (2000). The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 124, 511-528.
Brüggemann, W., & Jahnke, H., 2000. The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 124(3), p 511-528.
W. Brüggemann and H. Jahnke, “The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol. 124, 2000, pp. 511-528.
Brüggemann, W., Jahnke, H.: The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. 124, 511-528 (2000).
Brüggemann, W, and Jahnke, Hermann. “The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability”. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 124.3 (2000): 511-528.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar