Remarks on: “Some Extensions of the Discrete Lotsizing and Scheduling Problem”
指出Salomon等人关于离散批量与调度问题NP完全性的部分证明有误，因为其变换将原像问题的数据值映射到结果实例的数据数量，不是多项式时间变换。
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.