1. Introduction

Lot Sizing Problem (LSP) is a pivotal optimization challenge in the realms of production planning and inventory management. Since Harris's introduction of the Economic Order Quantity (EOQ) model in 1913, which was the first quantitative model for lot sizing balancing ordering and inventory costs to determine the optimal order quantity. But the model only optimized for continuous demand and static consumption and inventory costs [1]. Wagner and Whitin proposed a mixed-integer programming model to optimize for varying discrete demands and costs in 1958, which was the most classical and intuitive model for LSP [2].

LSP is designed to ascertain the optimal timing and quantities of production within a planning horizon, with the goal of optimizing key performance metrics. Primarily, this involves minimizing total costs while ensuring that both demand requirements and capacity limitations are met. The LSPs are tailored to various application scenarios and are classified accordingly. Key differentiators include whether the production capacity is limited (capacitated) or not (uncapacitated), the nature of the products involved (single-item versus multi-item), and the complexity of the production system, which can range from single-level to multi-level configurations.

LSP stands as a critical and complex challenge within the realm of production planning, particularly within the medium-term planning horizon. It plays a crucial role in industries characterized by a singular production process or those where multiple processes can be integrated into a unified operation, exemplified by the medical and chemical sectors. LSP is instrumental in strategizing production activities, including forging and molding, where precise production scheduling is essential for efficiency and cost-effectiveness [2].

These traditional LSP models assume deterministic or probabilistic demand, which may not reflect the inherent unpredictability of market demands. In real-world scenarios, the actual future demand is usually unavailable and its frequency cannot be assumed to be known or stable. This uncertainty means that future demand cannot be accurately represented as a random variable, thereby challenging the applicability of probabilistic models. Consequently, there is a need for alternative modeling approaches that can better address the volatility and ambiguity of market demands.

In the absence of sufficient observational data, it is necessary to refer to the opinions of domain experts to make them consistent with the actual situation. Uncertainty theory, a well-defined supplement of classic probability theory, offers a rigorous mathematical framework for incorporating expert opinions into decision-making processes. This paper adopts uncertainty theory to model market demand as independent uncertain variables for each future time period. Furthermore, a confidence constraint is introduced within the uncertainty theory framework, ensuring that the firms' ability to meet demand during a specific period is not less than a predetermined confidence level. This approach leads to the formulation of an uncertain programming model.

2. Basic theory and literature review

Considering the discrepancy between theoretical probability distributions and actual observed frequencies, Liu proposed uncertainty theory in 2007. This theory provides a mathematical framework for quantifying the belief degree in an event through the concept of uncertain measure [4]. Uncertainty theory is built on a new axiomatization system that includes Normality, Monotonicity, Self-Duality and Countable Subadditivity. And it involves key concepts including uncertain measure, uncertainty space, uncertain variable, and uncertainty distribution, offering a distinct approach to dealing with imprecise information that deviates from traditional probabilistic methods.

Based on uncertain variable and uncertainty distribution, Liu proposed the notion of uncertain programming, a theory of optimization in uncertain environments in 2009 [5]. At present, uncertain programming has found extensive applications across various domains, including Facility Location, Machine Scheduling, Vehicle Routing, Problem Scheduling, and Supply Chain Management, among others [6].

In 2012, Gao applied uncertain programming to address the single facility location problem on network. He considered the demand of each vertex as a non-negative Zigzag uncertain variable. And he further introduced the concept of satisfaction degree, which quantifies how well the allocated product quantity meets the demand at each vertex [7].

Ning et al. tackled the parallel machine scheduling problem by employing uncertain programming in 2017. They regarded the processing times of jobs and release dates as independent uncertain variables, each with a known uncertainty distribution. They established an uncertain multi-objective programming model with dual optimization objectives: the primary goal was to minimize the maximum completion time, and the secondary goal was to minimize the maximum delay time. Afterwards, they employed a genetic algorithm to solve this model [8].

Addressing the capacity planning challenges in the semiconductor manufacturing industry, Chien et al. in 2018 formulated an uncertain multi-objective programming model. Recognizing the inherent uncertainty in demand and capacity, they modeled these factors as uncertain variables. Their model aimed to optimize the complex trade-offs involved in semiconductor production by minimizing potential costs associated with oversupply, shortage, and technology migration [9]. This comprehensive approach provides a strategic framework for decision-making under uncertainty, which is a common scenario in the dynamic semiconductor industry.

In 2019, Majumder et al. addressed the solid transportation problem by incorporating uncertainty theory. They posited that key parameters—such as unit transportation costs, fixed charges, transportation times, supplies at origins, demands at destinations, conveyance capacities, and budgets at destinations—were all subject to uncertainty and thus modeled as uncertain variables. Then they developed three distinct models, each transformed into an equivalent deterministic form to account for budgetary limitations [10].

In 2021, Yang et al. approached the home healthcare routing and scheduling problem by integrating uncertain programming. They identified travel time between locations and service time at client sites as uncertain variables, reflecting the unpredictable nature of these parameters in home healthcare settings. And they formulated an optimization model with three key objectives: to minimize routing costs, enhance service consistency, and balance the workload among care providers. To tackle this complex multi-objective problem, they proposed an enhanced multi-objective artificial bee colony metaheuristic [11].

3. Model formulation

3.1. Traditional LSP model

The LSP model is fundamentally concerned with determining production quantities over a defined planning horizon, which is segmented into discrete time periods. Each period is characterized by a specific market demand that the producer must satisfy. The production process entails both fixed and variable costs. Fixed costs, also known as setup costs, are incurred whenever production commences, while variable costs depend on the levels of production and inventory. The unit variable cost encompasses both the cost of producing a single unit and the cost of holding inventory. The challenge for enterprises is to devise a production plan for each time period within the planning horizon that minimizes the total cost, while ensuring that market demand is met. This involves strategic decisions on when to initiate production and the optimal quantity to produce in each period.

Uncapacitated Single Item Lot Sizing Problem (USILSP) serves as the foundational model in LSP, frequently emerging as a key subproblem in the resolution of more complex production planning scenarios. This paper provides the basic mathematical expression of USILSP.

Notation:

• T=1,2,...,m: planning horizon.

• d_t: the demand for the product during time period t∊T.

• s_t: the setup cost for the product during time period t∊T.

• p_t: the unit product production cost during time period t∊T.

• h_t: the unit inventory cost during time period t∊T.

The objective of the problem is to minimize the aggregate costs associated with production, which encompass setup costs, production costs, and inventory costs. The mathematical formulation of USILSP is presented as follows:

Decision variables:

\( {y_{t}}=\begin{cases} \begin{array}{c} 1,if the product is produced in period t∈T \\ 0,otherwise \end{array} \end{cases} \)

\( {x_{t}}:the production amount in period t∈T \)

\( {q_{t}}:the inventory at the end of period t∈T \)

To further refine the relationship between setup and production costs, an additional binary decision variable, denoted as y_t, is incorporated. The USILSP model, which integrates this 0-1 variable, is formulated as follows:

\( min \sum _{t∈T}({s_{t}}{y_{t}}+{p_{t}}{x_{t}}+{h_{t}}{q_{t}}) \) (1)

subject to:

\( {q_{t}}={q_{t-1}}+{x_{t}}-{d_{t}}(∀t∈T) \) (2)

\( {q_{0}}=0 \) (3)

\( {x_{t}}≤{M_{t}}{y_{t}} (∀t∈T) \) (4)

\( {y_{t}}∈\lbrace 0,1\rbrace (∀t∈T) \) (5)

\( {x_{t}}≥0 (∀t∈T) \) (6)

\( {q_{t}}≥0 (∀t∈T) \) (7)

Among the above constraints, the Eq. (2) is the inventory balance constraint, ensures that the sum of production and inventory in each time period satisfies the current demand. The Eq. (3) sets the initial inventory level at the beginning of the planning horizon to zero, establishing a starting point for the model. The M_t in the Eq. (4) represents a sufficiently large number, usually taken \( { M_{t}}=\sum _{k=t}^{m}{d_{k}} \) . This constraint enforces that if production is not initiated during a time period (i.e., y_t=0), then the production volume for that period must also be zero. Lastly, the Eq. (5), Eq. (6) and Eq. (7) respectively constrain the permissive range of decision variables.

3.2. Uncertain programming model for USILSP

This section begins by revisiting some theorems related to uncertain programming.

Theorem 1 (Liu 2015) [12] Assume the objective function f(x, ξ₁, ξ₂, · · · , ξ_n) is strictly increasing with respect to ξ₁, ξ₂, ··· , ξ_m and strictly decreasing with respect to ξ_m+1, ξ_m+2, ··· , ξ_n. If ξ₁, ξ₂, ··· , ξ_n are independent uncertain variables with uncertainty distributions Φ₁, Φ₂, · · · , Φ_n, respectively, then the expected objective function E[f(x, ξ₁, ξ₂, · · · , ξ_n)] is equal to

\( \int _{0}^{1}f(x,Φ_{1}^{-1}(α),···,Φ_{m}^{-1}(α),Φ_{m+1}^{-1}(1-α),···,Φ_{n}^{-1}(1-α)) \) (8)

Theorem 2 (Liu 2015) [12] Assume the constraint function g(x, ξ₁, ξ₂, · · · , ξ_n) is strictly increasing with respect to ξ₁, ξ₂, ··· , ξ_k and strictly decreasing with respect to ξ_k+1, ξ_k+2, · · · , ξ_n. If ξ₁, ξ₂, · · · , ξ_n are independent uncertain variables with uncertainty distributions Φ₁, Φ₂, · · · , Φ_n, respectively, then the chance constraint

\( M\lbrace g(x,{ξ_{1}},{ξ_{2}},···,{ξ_{n}})≤0\rbrace ≥α \) (9)

holds if and only if

\( g(x,Φ_{1}^{-1}(α),···,Φ_{k}^{-1}(α),Φ_{k+1}^{-1}(1-α),···,Φ_{n}^{-1}(1-α))≤0 \) (10)

In the context of the USILSP model with demand uncertainty, the demand d_t for each time period t∊T is modeled as an uncertain variable characterized by a known uncertainty distribution Φ_t. And the inverse uncertainty distribution is denoted as Φ_t^-1. From Eq. (2), the inventory q_t is expressed as a linear function of q_t-1, x_t and d_t. With the initial condition that q₀=0, and the following recursive equation exists:

\( {q_{t}}={q_{t-1}}+{x_{t}}-{d_{t}} \)

\( {q_{t-1}}={q_{t-2}}+{x_{t-1}}-{d_{t-1}} \)

… (11)

\( {q_{2}}={q_{1}}+{x_{2}}-{d_{2}} \)

\( {q_{1}}={x_{1}}-{d_{1}} \)

Accordingly, q_t is also an uncertain variable. And it is easy to obtain from the above recurrence relation equation that \( {q_{t}}=\sum _{i=1}^{t}({x_{i}}-{d_{i}}) (∀t∈T) \) .

Liu pointed out in 2009 that since an objective function with uncertain variables cannot be minimized directly, we may need to minimize its expected value [5]. The expression of Eq. (1) is modified here by modifying the objective function to minimize the expected cost:

\( min E[\sum _{t∈T}({s_{t}}{y_{t}}+{p_{t}}{x_{t}}+{h_{t}}{q_{t}})] \) (12)

equivalent to:

\( min E\lbrace \sum _{t∈T}[{s_{t}}{y_{t}}+{p_{t}}{x_{t}}+{h_{t}}\sum _{i=1}^{t}({x_{i}}-{d_{i}})]\rbrace \) (13)

The primary goal of LSP is to minimize costs while satisfying the market demand. However, in the uncertain programming model, the complete satisfaction of market demand is not guaranteed due to its inherent uncertainty. To address this, it is assumed that the production x_t and the inventory from the previous period q_t-1 can meet the current period’s demand d_t with a confidence level α. In other words, the model requires that the belief degree of x_t+q_t-1≧d_t is greater than or equal to the confidence level α. Within the framework of uncertainty theory, this requirement is expressed as a chance constraint:

\( M\lbrace {x_{t}}+{q_{t-1}}≥{d_{t}}\rbrace ≥α (∀t∈T) \) (14)

equivalent to:

\( M\lbrace {{d_{t}}-x_{t}}-{q_{t-1}}≤0\rbrace ≥α (∀t∈T) \) (15)

It is obtained from recurrence relation Eq. (11) that \( {q_{t}}=\sum _{i=1}^{t}({x_{i}}-{d_{i}}) (∀t∈T) \) . Substituting \( {q_{t-1}}=\sum _{i=1}^{t-1}({x_{i}}-{d_{i}}) \) into Eq. (15), upon rearrangement, the following equation is derived:

\( M\lbrace \sum _{i=1}^{t}({d_{i}}-{x_{i}})≤0\rbrace ≥α (∀t∈T) \) (16)

The complete uncertain programming model is as follows:

\( min E\lbrace \sum _{t∈T}[{s_{t}}{y_{t}}+{p_{t}}{x_{t}}+{h_{t}}\sum _{i=1}^{t}({x_{i}}-{d_{i}})]\rbrace \) (13)

subject to:

\( M\lbrace \sum _{i=1}^{t}({d_{i}}-{x_{i}})≤0\rbrace ≥α (∀t∈T) \) (16)

\( {y_{t}}∈\lbrace 0,1\rbrace (∀t∈T) \) (5)

\( {x_{t}}≥0 (∀t∈T) \) (6)

Traditional numerical optimization and heuristic algorithms are not directly applicable to uncertain programming problems. To bridge this gap, in 2015, Liu gave a method for converting uncertain programming models into their crisp mathematical programming equivalents, thereby enabling the use of conventional algorithms to solve problems [12].

According to Liu’s theorem, the above uncertain programming is equivalent to the follow crisp mathematical programming:

\( min \sum _{t∈T}[{s_{t}}{y_{t}}+{p_{t}}{x_{t}}+{h_{t}}\sum _{i=1}^{t}{x_{i}}]-\int _{0}^{1}[\sum _{t∈T}{h_{t}}\sum _{i=1}^{t}Φ_{i}^{-1}(1-α)]dα \) (17)

subject to:

\( \sum _{i=1}^{t}[Φ_{i}^{-1}(α)-{x_{i}}]≤0 \) \( (∀t∈T) \) (18)

\( {y_{t}}∈\lbrace 0,1\rbrace (∀t∈T) \) (5)

\( {x_{t}}≥0 (∀t∈T) \) (6)

3.3. Solution method

The transformed model becomes a standard constrained optimization problem, amenable to a variety of optimization methods to find either the global optimum or a near-optimal solution. Among the widely utilized algorithms are the Gradient Descent Method, Newton's Method, Genetic Algorithm, and Simulated Annealing Algorithm, etc.

The Gradient Descent Method is an iterative optimization algorithm that updates variables in the direction opposite to the gradient of the objective function, making it well-suited for optimizing simple, continuously differentiable, convex functions. The Newton's Method is based on second-order derivatives, approximating the current point as the extremum of a quadratic function and then moving to the extremum of the quadratic function. This method requires calculating both first and second order partial derivatives and solving a linear system, which is ideal for problems with smooth second order derivatives. The Genetic Algorithm is a heuristic search and does not depend on any particular problem characteristics but perform optimization directly on the objective function. The method simulates natural selection and genetic mechanisms to iteratively evolve candidate solutions through selection, crossover and mutation operations. The Simulated Annealing Algorithm draws inspiration from the annealing process in metallurgy, where a system is gradually cooled to minimize its energy. This method treats the problem as a physical system and minimizes the objective function by gradually decreasing the temperature of the system. This approach helps the algorithm to escape local minima, enabling a broader exploration of the solution space.

Selecting the most suitable solution method depends on the specific characteristics of the problem at hand, particularly the expression of the uncertainty distribution Φ_t associated with the demand d_t. It is crucial to evaluate these factors to determine which algorithm will most effectively address specific problems.

4. Conclusion

This paper presents an integrated approach to Lot Sizing Problem (LSP) for production processes, accounting for setup, production, and inventory costs. It focuses on the foundational Uncapacitated Single Item Lot Sizing Problem (USILSP), aiming to minimize total costs. Innovatively, this paper applies uncertainty theory to address the unpredictability of future demand, a critical factor in production planning. Furthermore, it develops an uncertain programming model for USILSP and transforms it into a deterministic equivalent, paving the way for effective solution strategies using conventional optimization techniques.

Future research can be extended by focusing on the following areas. Firstly, specifying the uncertainty distributions for real-world problems will allow for the application of various algorithms to solve USILSP under uncertainty. This will facilitate a comparative analysis of algorithmic efficiency, leading to the optimization of solution methods. Secondly, extending the study to more complex variants of the LSP, such as Capacitated Single Item Lot Sizing Problem (CSILSP) and Capacitated Multi Item Lot Sizing Problem (CMILSP). Formulating uncertain programming models for these variants will broaden the scope of practical applications and enhance the versatility of such models across diverse industrial settings.