Exact Algorithms for Multi-Module Capacitated Lot-Sizing Problem, and its Generalizations with Two-Echelons and Piecewise Concave Production Costs*

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 MCLS-S with fixed n ≥ 2 ? . We present exact fixed-parameter tractable (polynomial) algorithms that solve MCLS and MCLS-S in O ( T 2 n +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 ( T 2 m +3 ) time, where m is the number of breakpoints in these functions, and (b) two-echelon MCLS that takes O ( T 4 n +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).