|
Article Excerpt
We consider the planning and scheduling of production in a multitask/multistage batch manufacturing process typical of industries such as chemical manufacturing, food processing, and oil refining. We allow instances in which multiple sequences of tasks may be used to produce end products. We formulate the problem as a mixed-integer linear program and show that the linear programming relaxation has a large integrality gap and requires significant computational effort to solve to optimality for large instances. Using echelon inventory, we construct a new family of valid inequalities for this problem. The formulation with the additional constraints leads to a significantly tighter linear programming relaxation and to greatly reduced solution times for the mixed-integer linear program.
Subject classifications: production planning/scheduling; echelon inventory; integer programming.
Area of review: Optimization.
History: Received July 2004; revisions received May 2006, May 2007; accepted May 2007.
1. Introduction
We consider the planning and scheduling of production in a multitask/multistage batch manufacturing process typical of industries such as chemical manufacturing, food processing, and oil refining (see Figure 1). We first consider a system with a single processing unit. The processing unit is capable of carrying out several tasks, each consuming one or more inputs and producing one or more outputs. Inputs for each task might consist of raw resources (feeds) or semifinished products (intermediates). Similarly, outputs from each task may consist of intermediates or finished products. It is possible for the same intermediate or finished product to be produced via more than one task. Consequently, each intermediate or finished product can be the result of one or more sequences of tasks. Each task is associated with a variable batch size, a variable production cost, a fixed processing time, and a task-specific setup time and setup cost.
We consider an environment in which time is divided into discrete uniform periods. A period is chosen sufficiently small to allow the modeling of start and end times of each task (e.g., the length of a time period is a common divisor to all task processing times). In each period, there may be external demand for one or more finished products or intermediates. To meet demand while satisfying capacity constraints, the plant may choose to produce ahead of demand and hold inventory. In that case, a holding cost per unit of inventory per period is incurred. All costs, including production, inventory holding, and setup costs, could vary from period to period.
Our objective is to develop production schedules that specify production quantities and production start times that minimize the sum of production, setup, and inventory holding costs while meeting demand on time and satisfying constraints on production capacity and processing unit availability. We adopt a representation scheme similar to the state-task-network formalism introduced by Kondili et al. (1993), where a system is described by a set of states (i.e., feeds, intermediates, and finished products) and a set of tasks that transform material from one state to another. We allow for the possibility of multiple tasks being carried out on the same unit and for those tasks to have overlapping sets of inputs and outputs. We also allow for the possibility of multistep processing, where a material can undergo a series of tasks on the same units. We refer to our problem as the multitask/multistage production planning and scheduling problem (MPSP).
We formulate the MPSP as a mixed-integer linear program (MILP). We observe that the formulation leads to an NP-hard problem with a large integrality gap (gap between the optimal solution of the MILP and the optimal solution of the linear programming relaxation). We use the notion of echelon inventory to construct new valid inequalities (cutting planes) for the formulation. We show that the formulation with the additional constraints leads to a significantly tighter LP relaxation and to much-reduced solution times for the MILP. We compare the impact of echelon inventory constraints with that of single-stage inventory constraints that have been used in related settings such as capacitated lot-sizing problems (see Wolsey 1997). We show that echelon constraints can significantly outperform single-stage constraints. Based on an extensive numerical study, we highlight cases where echelon inventory constraints are particularly useful. We first treat the case of systems with a single processing unit. Then, we extend the formulation and the additional valid inequalities to systems with multiple processing units.
The MPSP is related to the large body of literature on production planning and scheduling in process industries, as well as to the capacitated lot-sizing problem (CLSP) in discrete manufacturing. However, in contrast to the CLSP, there is not necessarily a one-to-one correspondence between tasks and input/output materials in the MPSP. This makes the scheduling problem considerably more difficult because the manufacturing of one material could affect the availability of several others. The complexity of the problem can be further compounded by the reentrant nature of the flows and the possibility of producing the same material via alternative routes. Because the problem is a generalization of the CLSP, we expect solutions to large problems to be difficult to find.
[FIGURE 1 OMITTED]
The rest of this paper is organized as follows. In [section]2, we provide a brief review of the related literature. In [section]3, we present the problem formulation of the MPSP and discuss modeling assumptions. In [section]4, we describe the notion of echelon inventory and use it to construct valid inequalities. In [section]5, we extend our results to systems with multiple processing units. In [section]6, we report on numerical results. In [section]7, we provide a summary and a brief discussion of various extensions.
2. Related Literature
There is an extensive literature on production planning and scheduling in process industries. Recent reviews can be found in Kallrath (2003), Pekny (2002), Shah (1998), and Applequist et al. (1997). In process industries, two modes of production can be distinguished: continuous and batch. Continuous production is adopted when there are few products with similar routings and relatively stable demand. Batch production is adopted when the number of products is large and demand for each product varies with time. Batch production in process manufacturing differs from batch production in discrete manufacturing in that each operation could require multiple inputs and could produce multiple outputs. In contrast to discrete manufacturing, the quantities of both inputs and outputs are typically continuous. The output from a process might revisit the same process several times for further processing. Hence, there can be significant reentrant flows.
An important development in the modeling of planning and scheduling in process manufacturing has been the state-task network (STN) representation introduced by Kondili et al. (1993). The STN framework uses materials (states) and tasks as building blocks for the process description, with each task consuming and producing materials while using equipment. An enhancement to the STN representation is the resource-task network (RTN) proposed by Pantelides (1994), which unifies the treatment of both equipment and materials as resources that are consumed (produced) at the start (end) of a task.
Although the boundaries are overlapping, the existing literature can be classified as pertaining to either planning or scheduling. For planning, time is typically discretized into planning periods where only aggregate capacity is taken into account and the primary decisions are the quantities produced of each material in each period. Examples of recent papers include Papageorgiou and Pantelides (1996a) and van den Heever and Grossman (1999). Formulations with continuous-time representation can be found in Schilling and Pantelides (1996), Zhang and Sargent (1996), and Mockus and Reklaitis (1999). A review can be found in Maravelias and Grossman (2003a). Planning problems are typically formulated as linear programs and can be solved relatively efficiently using standard methods. For scheduling, time is either finely discretized or treated as a continuous parameter. In addition to production quantities for each material, decisions in a scheduling problem include the start and end time of individual tasks on specific production units. Scheduling problems are typically formulated as MILPs. In most cases, the formulation leads to an NP-hard problem. Recent examples include Maravelias and Grossman (2003b), Majozi and Zhu (2001), and Neumann et al. (2003). To cope with problem complexity, several papers propose decomposition approaches, where the original problem is decomposed into a series of subproblems with smaller time horizons (see, for example, Elkamel et al. 1997 and Lin et al. 2002). Others develop reformulations that are relatively easier to solve (see, for example, Sahinidis and Grossman 1991, Shah et al. 1993, and Ierapetritou and Floudas 1998).
Planning and scheduling in process industries can be seen as a generalization of the CLSP in discrete manufacturing. The CLSP has been widely studied. Review of the literature and recent advances can be found in Wolsey (2002), Miller and Wolsey (2003), and Atamturk and Munoz (2004). The CLSP, which is NP-hard, can be formulated as an MILP and solved via standard branch and bound for relatively small problems. Reformulations and the introduction of valid inequalities have been successful in reducing solution times in some cases for larger problem instances. For example, Barany et al. (1984) proposed the so-called (l, S) inequalities. Several other authors have found valid inequalities for other variations of the CLSP; for example, see Magnanti and Vachani (1990), Constantino (1996), Bel-vaux and Wolsey (2000, 2001), and Miller et al. (2003).
The literature on the CLSP with multiple stages is more limited. The problem is computationally harder than the simple CLSP. Therefore, the solution of large problems invariably involves heuristic approaches; see Katok et al. (1998), Tempelmeier and Destroff (1996), Stadtler (2003), and the references therein. The notion of echelon inventory first introduced by Clark and Scarf (1960) has been used to reformulate the CLSP with multiple stages and improve computational efficiency; see, for example, Afentakis and Gavish (1986), Pochet and Wolsey (1991), and Belvaux and Wolsey (2000).
3. Formulation
We first introduce a formulation for the MPSP with just a single processing unit. The MPSP can be described in terms of a set of tasks, N, a set of materials, R, and a set of periods, T, over which demand is known. The demand in period t for material r is denoted by [d.sub.t.sup.r]. We allow demand to occur for both finished and intermediate products. Each task consumes a set of inputs in fixed proportions, with [[rho].sup.i, r] being the proportion of input to task i due to material r. Each task produces a set of outputs also in fixed proportions, with [[sigma].sup.i, r] being the proportion of output from task i in the form of material r. We denote the set of tasks for which material r is an input by I(r) and the set of tasks from which material r is an output by O(r). Each task requires a fixed processing time of [[alpha].sub.i] periods.
The process incurs a variable production cost [p.sub.t.sup.i] per unit of production quantity undertaken by task i in period t and a fixed setup cost [g.sub.t.sup.i] if task i is...
|
