Exact algorithms for multi-module capacitated lot-sizing problem, and its generalizations with two-echelons and piecewise concave production costs

Kartik Kulkarni and Manish Bansal

IISE Transactions, 2023, vol. 55, issue 12, 1187-1202

Abstract: We study new generalizations of the classic 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 article 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(T2n+3) time for a given n≥2. It generalizes algorithm of Atamtürk and Hochbaum [Management Science 47(8):1081–1100, 2001] for MCLS-S with n = 1. 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. The former reduces run time of algorithm of Koca et al. [INFORMS J. on Computing 26(4):767–779, 2014] for LS-PC-S by 93.6%, and the latter generalizes algorithm of van Hoesel et al. [Management Science 51(11):1706–1719, 2005] for two-echelon MCLS with n = 1. 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. Our algorithm for MCLS-S 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).

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2022.2153948 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:55:y:2023:i:12:p:1187-1202

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2022.2153948

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().