|
Article Excerpt
1. Introduction
We consider a lot sizing problem with multiple items where the objective is to determine when and how much of each item should be produced over a finite planning horizon so as to minimize the sum of production, inventory holding and setup costs. The choice of a production plan is constrained by the need to satisfy all the demand that arises in each period for each item. The problem we consider has multiple levels (or stages), where an item might serve as an input in the production of one or more other items and may itself be the output of production involving one or more other items. In this paper, we consider systems where the production sequences (the series of tasks and the set of input items for each task) used in producing an item can be flexible. Furthermore, we allow for the possibility of multiple flexible machines that may be able to perform one or more tasks. Hence, our treatment of lot sizing with multiple items, multiple levels and multiple machines is general and includes structures such as series, assembly and distribution systems, among others.
In contrast to standard multi-level lot sizing problem formulations, our treatment differentiates between items and production tasks, which allows for the possibility of alternate bills of materials or recipes. This allows us to model potential input substitutions, where it is possible to substitute one component with another (typically of a higher quality). Component substitution is a common practice in industries, such as computer manufacturing, where it is used as a strategy for mitigating inventory shortages or to take advantage of differences in component costs from period to period. For example, Dell, which manufactures computers in an assemble-to-order fashion, is known to resort to component substitution (e.g., substituting a lower grade chip with one of higher grade) in order to fulfill customer orders
within the quoted lead-time. Our formulation also allows us to model settings where there is strong commonality in the input items of various tasks. Such commonality arises in settings, such as electronics manufacturing, where many components are shared among different end products. Finally, our formulation permits the modeling of production processes with flexible machines, a common feature in industries such as metal cutting, printed circuit board assembly and chemical manufacturing.
We formulate the problem as a Mixed-Integer Linear Program (MILP). We use the notion of echelon inventory to construct a set of valid inequalities (cuts) and show via numerical results that they can significantly improve solution time and solution quality. In addition to being strong and valid for the flexible production case, we also show that our inequalities are at least as strong as those proposed by Belvaux and Wolsey (2001) for the multi-level fixed production case.
There is an extensive literature on the lot sizing problem. A survey of important results and solution approaches can be found in Pochet and Wolsey (2006); see also Miller and Wolsey (2003). The literature on lot sizing with multiple levels is relatively less extensive. A review of recent advances can be found in Stadtler (2003).
For uncapacitated systems (systems with no constraints on production capacity), Afentakis et al. (1984) consider assembly structures and propose a solution approach using decomposition. Afentakis and Gavish (1986) extend these results to systems with general production structures. For capacitated systems, the problem is NP-hard, and even finding a feasible solution can be computationally challenging; see Pochet and Wolsey (2006). Consequently, several researchers have proposed heuristics. Simpson and Erenguc (1998) propose a neighborhood search method to merge multiple smaller lots into larger lots in cases where the reduction in setup cost due to batching is sufficient to justify the increased holding cost. Tempelmeier and Derstroff (1996) decompose the multi-level structure into single-level problems using a Lagrangian relaxation. Harrison and Lewis (1996) propose a heuristic for capacitated serial systems based on repeatedly solving Linear Programming (LP) subproblems and modifying constraint coefficients to implicitly account for capacity consumption. Afentakis (1987) proposes a relaxation which decomposes the problem into T (time horizon) stages, where the set of feasible solutions at stage t (t [member of] {1, ..., T}) is limited by the variables already fixed in stages 1, ..., t - 1 (for periods 1, ..., t - 1). This method works well for uncapacitated problems, but can result in infeasibilities for capacitated problems. Katok et al. (1998) apply LP-based rounding procedures to multi-level capacitated problems, where setup variables are iteratively fixed based on the output of previous LP-relaxations.
In addition to heuristics, there has been progress in solving some problems to optimality by adding strong valid inequalities to the MILP formulations of these problems. Many of the inequalities, such as those proposed by Pochet and Wolsey (1991), are extensions of inequalities derived for single-level problems, such as the (l, S) inequalities of Barany et al. (1984). These single-level inequalities can be extended to the multi-level case via a reformulation of the problem in terms of echelon inventory (see, for example, Afentakis and Gavish (1986), Belvaux and Wolsey (2000), Belvaux and Wolsey (2001) and Wolsey (2002)). Such reformulations have their origin in the seminal paper by Clark and Scarf (1960), who first introduced the notion of echelon inventory.
In problems where production capacity in each period is an integer multiple of some fixed level, Pochet and Wolsey (1993) derive facet-defining (k, l, S, I) inequalities. Constantino (1996) derives extended (k., l, S, I) and supermodular inequalities for a version of the single-item capacitated case and applies these inequalities as cutting planes for the multi-item case. Miller et al. (2003a) derive cover and reverse cover inequalities for the multi-item capacitated case with setup times, again applying polyhedral results obtained for structured problem relaxations in order to strengthen their initial formulation; additional results can be found in Miller et al. (2003b). Miller and Wolsey (2003) derive tight problem formulations for various discrete lot sizing problems, many of which result in equivalent integral LP formulations. Belvaux and Wolsey (2000) describe a software implementation, bc-prod, designed to solve many common lot sizing problems to optimality.
Although the models and inequalities we develop in this paper have similar intuition and flavor as some of the above literature, the fundamental difference is the inclusion in our work of flexible production sequences, which complicates the calculation of echelon inventory. This added complexity requires special consideration in the development of the model formulation and valid inequalities in this paper, and prevents the direct extension of inequalities developed in previous work. Gaglioppa et al. (2008) do consider a problem with flexible production sequences and use a similar notion of echelon inventory to construct valid inequalities, but their setting is different. They treat a "small-bucket" problem where they determine the exact timing of tasks. Furthermore, in their case, tasks are associated with variable production quantities and these quantities are decision variables. Their problem is motivated by applications in process industries while ours is more appropriate for discrete manufacturing where the production quantities associated with individual tasks tend to be fixed.
The rest of the paper is organized as follows. In Section 2, we formulate our problem as a MILP for the case of a system with a single machine. In Section 3, we describe the notion of echelon inventory and use it to derive valid inequalities. In Section 4, we extend our formulation and inequalities to the multi-machine case. In Section 5, we present computational results. In Section 6, we provide a brief summary and suggestions for future research.
2. Description and model formulation: the single-machine case
We shall refer to our multi-level flexible production lot sizing problem as the MLFP. We first consider a system consisting of a single machine and a set of items, R, which are produced via a set of tasks, N. Each task may require multiple items as input, but each task has a single-item output. This assumption, while not necessary for the validity of the problem formulation below, is needed for the validity of the cuts we develop in Section 4 (see also discussion in Section 6). We let [[rho].sup.[i,r]] denote the number of units of item r required to initiate one unit of task i, [[sigma].sup.[i,r]] the number of units of item r produced by one completion of task i and [[alpha].sub.i] the processing time of task i. We assume no direct product recycling, thus for any task i and item r, [[rho].sup.[i,r]] and [[sigma].sup.[i,r]] cannot both be positive. We use this assumption to simplify the proof of Theorem 5, but note that if [[rho].sup.[i,r]] and [[sigma].sup.[i,r]] were truly both positive for a manufacturing process, then we could use [[^.[sigma]].sup.[i,r]] = [[sigma].sup.[i,r]] - [[rho].sup.[i,r]] and [[^.[rho]].sup.[i,r]] = as the input and output parameters, respectively. Capacity may vary from period to period and we let [C.sub.t] refer to the available production capacity (in units of time) in period t, where t = 1. ..., T is the planning horizon. External demand for each item may vary from period to period and we refer to external demand for item r in period t as [d.sub.t.sup.r]. Each time a task is initiated, we incur a production cost [f.sub.t.sup.i]. In addition, a setup cost [g.sub.t.sup.i] is incurred if task i is performed during period t. We assume that a task could be carried out multiple times during a period, but this number is constrained by the available capacity. Although the production cost is incurred each time a task is carried out, the setup cost is incurred only the first time the task is initiated in each period.
We assume that periods are sufficiently long so that tasks initiated in a period are always completed in that period. Also,...
|
