We study new generalizations of the classical capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capacity in each time period is the summation of capacities of a subset of n available modules (machines or vehicles) of different capacities. We refer to this problem as Multi-module Capacitated Lot-Sizing Problem without or with Subcontracting, and denote it by MCLS or MCLS-S, respectively. These are NP-hard problems if n is a part of the input and polynomially solvable for n = 1. In this paper, we address an open question: Does there exist a polynomial time exact algorithm for solving the MCLS or MCLSS with fixed n ≥ 2?. We present exact fixed-parameter tractable (polynomial) algorithms that solve MCLS and MCLS-S in O(T2n+3) time for a given n ≥ 2. We also present exact algorithms for two-generalizations of the MCLS and MCLS-S: (a) a lot-sizing problem with piecewise concave production cost functions (denoted by LS-PC-S) that takes O(T2m+3) time, where m is the number of breakpoints in these functions, and (b) two-echelon MCLS that takes O(T4n+4) time. We perform computational experiments to evaluate the efficiency of our algorithms for MCLS and LS-PC-S and their parallel computing implementation, in comparison to Gurobi 9.1. The results of these experiments show that our algorithms are computationally efficient and stable. Furthermore, our algorithm for MCLS-S also addresses another open question related to the existence of a polynomial time algorithm for optimizing a linear function over n-mixing set (a generalization of the well-known 1-mixing set).
Citation
Report#07122019, Virginia Tech, July 2019