Remarks on: “Some Extensions of the Discrete Lotsizing and Scheduling Problem”

Saloman et al. (Salomon, M., L. G. Kroon, R. Kuik, L. N. Van Wassenhove. 1991. Some extensions of the discrete lotsizing and scheduling problem. Management Sci. 37 801–812.) claim the NP-completeness of different variants of the discrete lot-sizing and scheduling problem (DLSP) which are differentiated by using a six-field notation. However, some of the given proofs are incorrect because the transformations employed map certain data values of the preimage problem to the number of data in the resulting instance and are hence not polynomial. As an example, we concentrate here on the 1/*/SI/G/A-optimization problem (Salomon et al. [Salomon, M., L. G. Kroon, R. Kuik, L. N. Van Wassenhove. 1991. Some extensions of the discrete lotsizing and scheduling problem. Management Sci. 37 801–812.], Theorem 3). Similar arguments pertain to the 1/*/A/G/SI-DLSP, too.

• 저널Management Science · 43(1) · 122–122
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.43.1.122
• 저자Wolfgang Brüggemann, Hermann Jahnke