Optimization Online


Exact Algorithms for Lot-Sizing Problems with Multiple Capacities, Piecewise Concave Production Costs, and Subcontracting

Kartik Kulkarni (kartikrf***at***vt.edu)
Manish Bansal (bansal***at***vt.edu)

Abstract: In this paper, we introduce a new generalization of the classical capacitated lot-sizing problem with concave production, holding, and subcontracting costs, denoted by CLSP-S, in which the total production capacity in each time period is the summation of binary multiples of n different capacities. We refer to this problem as multi-capacitated lot-sizing problem (with subcontracting), and denote it by MCLS-(S). We present a dynamic programming approach to optimally solve the MCLS and MCLS-S, for a given n, in polynomial time. Note that for n = 1, the MCLS-S reduces to the CLSP-S and therefore, our algorithm generalizes the algorithm of Atamturk and Hochbaum [Management Science 47(8):1081-1100, 2001] for CLSP-S. We also develop another dynamic programming algorithm for the MCLS-S with piecewise concave production costs and no capacity constraint, i.e. n = 0, denoted by LS-PC-S. Furthermore, we perform computational experiments to evaluate the efficiency of our algorithms and their parallel computing implementations for solving instances of MCLS and LS-PC, in comparison to CPLEX 12.7 and the only known algorithm for LS-PC-S by Koca, Yaman, and Akturk [INFORMS J. on Computing 26(4):767-779, 2014]. The results of these experiments show that our algorithms are computationally efficient and their solution times are stable.

Keywords: multi-capacitated lot-sizing, piecewise concave production cost, dynamic programming, concave subcontracting costs, production planning

Category 1: Integer Programming (0-1 Programming )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Category 3: Other Topics (Dynamic Programming )

Citation: Report#07122019, Virginia Tech, July 2019

Download: [PDF]

Entry Submitted: 07/17/2019
Entry Accepted: 07/17/2019
Entry Last Modified: 07/19/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society