|
Article Excerpt
1. Introduction
In this paper, we develop an approach based on composite variable models and a novel corresponding algorithm to solve challenging problems in production planning. We use the problem of scheduling presslines in an automotive stamping facility as a demonstrative example.
The motivation for this research stems in part from frustrations that we have experienced, and that we have heard voiced by colleagues in both academia and industry, over the challenges encountered in applying traditional Mathematical Programming (MP) tools to production planning problems. On the one hand, MP has proven to be a powerful tool for solving real-world planning problems in areas such as passenger aviation (Gopalan and Talluri, 1988), freight transportation (Crainic, 2002) and military logistics (Eom et al., 1998)--problems that, similar to production planning, contain large numbers of decisions interacting in complex ways. On the other hand, production planning problems often have, at their core, structures that seem to defy conventional MP techniques. Even the seemingly simplistic case of scheduling a pure blocking flow shop has proven to be tremendously difficult, not only in the theoretical sense (Sriskandarajah and Hall, 1996) but also in practice, where even small, non-pathological instances can fail to converge. Thus, an enormous literature has evolved that seeks to solve this challenging problem (for example, Baker (1975), McCormick et al. (1989), Glass and Potts (1996) Sriskandarajah and Hall (1996), Caraffa et al. (2001), and Hejazi and Saghafian (2005)). At the same time, however, criticism has been raised, both by industry and from within the academic community (Dudek et al., 1992; Portougal and Robb, 2000), that this problem is too simplistic to have real-world relevance. In fact, despite several decades of research, many basic production planning problems such as this still cannot be solved to optimality without using simplifying assumptions or considering only small problem instances in order to achieve tractability.
Composite Variable Modeling (CVM)--using models in which variables capture multiple decisions simultaneously, thereby embedding system complexity--has been successful in improving realism and tractability for many real-world applications in transportation and logistics (for example, Appelgren (1969), Crainic and Rousseau (1987), Caraffa et al. (2001), Armacost et al. (2002), Barnhart et al. (2002), Cohn and Barnhart (2007), Barnhart et al. (2009) and Colin et al. (2007)) but has had little exposure in production planning. In this research, we set out to determine whether CVM can in fact address some of the challenges found in production planning problems as well.
As a demonstrative example, we consider (in collaboration with Ford Motor Company) the question of how to schedule presslines in automotive stamping facilities--facilities that convert coils of sheet metal into body parts such as hoods and door panels in preparation for automotive assembly. A pressline is a sequence of dies that act like giant "cookie cutters," punching out the shapes of the part types produced on that line. The planning problem is to schedule the production of these part types on each individual pressline--what order to sequence the parts in, how much to produce each time and when to changeover between part types.
This problem is difficult to solve not only because of the general challenges found in most machine scheduling problems, but additionally because of the specific operational requirements placed on the changeovers from one part type to another in this problem (described in detail in Section 2). Modeling these requirements in a traditional MP approach yields an intractable number of constraints and variables, even if time is discretized and the granularity is coarse. We have developed an alternative approach in which, instead of defining variables to represent the assignment of jobs to machines or tasks to points in time, each Composite Variable (CV) represents the decision of whether or not to select a specific, predefined schedule for a given shift in the planning horizon (we refer to these as shift schedules). This enables us to embed much of the operational complexity within the individual variables themselves, rather than through the use of complicating constraints. Furthermore, this variable definition allows us to not require that batch sizes, number of changeovers, labor availability or sequencing of part types be restricted or predefined in order to achieve tractability, as is the case in most of the machine scheduling literature. Finally, we are able to allow sequence-dependent changeover times and demand-specific due dates, also an enhancement over much of the literature.
The primary contributions of this research are three-fold. First, through the example of automotive pressline scheduling, we show that the benefits enabled by CVM for solving complex transportation and logistics problems can also be achieved in production planning problems. In particular, we introduce CVs that represent entire schedules for individual shifts within the planning horizon. By defining variables in this way, we can capture significant operational complexity; we can also provide greater flexibility in setting production parameters such as sequence-dependent changeover times.
The benefits of a CVM approach typically come at the cost of a very large number of binary variables and/or restrictions on the solution space such as the discretization of time. The second contribution of our research is in recognizing that the vast majority of the feasible shift schedules in our model can be represented as a convex combination of a small, select subset of specialized shift schedules. This enables us to formulate an enhanced model that exhaustively captures all possible schedules (i.e., we do not need to discretize time or in any other way limit the set of schedules considered) while keeping the number of CVs small. As an added benefit, because we are seeking convex combinations of shift schedules, we can relax the integrality of the remaining CVs, leaving only a small set of auxiliary variables restricted to be integer.
Although we are able to solve most of the problem instances provided by Ford using this enhanced model, we nonetheless observe that many of the run times are negatively impacted by the same challenges of a weak Linear Programming (LP) relaxation that plague most machine scheduling problems. Our third contribution is the development of a new algorithm to overcome this challenge. Rather than solving the problem as a single (difficult) optimization problem, we demonstrate how solving a small number of (easy) feasibility problems allows us to significantly reduce run time while still finding optimal or near-optimal solutions.
The paper is organized as follows. In Section 2, we describe the pressline planning problem. We review the related literature in Section 3. We develop a basic CV model for the pressline scheduling problem in Section 4. Section 5 contains the enhanced formulation along with initial computational results. These results motivate the development of the new algorithm, presented in Section 6 with revised computational results. We conclude in Section 7 with a summary of our results and some suggested areas for future research.
2. The pressline planning problem
Automotive stamping plants produce parts used to construct vehicle frames, such as hoods and door panels. The process begins by inserting large rolls of sheet steel into a blanking press. This press cuts the sheet steel into pieces that are slightly larger than the final part (blanks). The blanks are then passed to a pressline made up of matching upper and lower dies. As a blank moves through the pressline, the dies shape it into a three-dimensional part. After passing through the pressline, some parts are shipped to downstream facilities while others continue on to subassembly and/or assembly workstations within the stamping facility. An average pressline produces on the order of five to 15 distinct part types.
In this research, we focus on the scheduling of the presslines. This is the bottleneck operation, with the most binding capacity constraints. For a single pressline, the decisions are two-fold: what order to sequence the part types in and how much of each part type to build during these runs. The key modeling challenges in this problem stem from the requirements governing changeovers between two part types. Two things must happen when changing the pressline from the production of part A to that of part B.
First, the dies for part B must be prepared. This offline preparation can take place while part A is being produced, but it cannot begin before production of part A starts. During off-line preparation, tools from the previous changeover are moved off the bolsters and to their storage location and/or cleaning and maintenance area. Then, the next set of tools to be set are picked up and moved onto the bolsters, the tools are visually checked and all automation arms, if required, are pre-set.
Second, once the off-line preparation (which can take as much as 2 hours) has been completed and after the production of part A ends, the changeover to the dies for part B must take place. Specifically, once the production of a set of tools has been completed, the presses are locked out, the area is cleaned and the dies for part A are unclamped or unbolted and secured. The old tools are moved out, and the new tools (for part B) are moved in and secured and the automation arms are attached and then inspected. During this period (which, depending on the technology used, can take from as little as 30 minutes to as much as several hours), no parts can be produced on the pressline.
Two important operational policies must be adhered to when scheduling changeovers. First, given parts A and then B are to be produced in sequence on the same pressline, it is strongly preferred that as soon as the changeover to begin production of part A is completed, the off-line preparation for part B begins. This is to ensure that the pressline can be switched over from part A to part B as quickly as possible if there is a problem with the production of part A. Second, both the changeover to part A and then the subsequent off-line preparation time for part B should be fully contained within a single shift (there are three 8-hour shifts per day). This is so a single group of workers maintains full responsibility over the pair of activities. We model both of these policies as hard constraints.
It is also relevant to note that workers (both direct laborers, operating the presslines, and indirect labor crews, preparing for and conducting the changeovers) must be hired for the entire 2-week period within a given shift. Thus, the daily staffing level for a given shift type (first, second or third) is the maximum labor requirement across all such shifts in the 2-week period.
We make the following assumptions.
Assumptions
1. The problem is static, deterministic and repeating. Our goal is to develop a 2-week schedule, to be repeated over an extended period of time, comprised of at most three shifts per weekday, with weekend shifts used as-needed to accommodate spikes in demand. Although demand may vary from day to day over the 2-week horizon, it is assumed that the inventory levels at the start and end of this period are the same. (This final assumption can be easily relaxed.)
2. All daily demand requirements must be met. The stamping facility feeds the downstream final assembly plants and service facilities. It is essential that these final assemblies not be disrupted due to lack of materials from the stamping facilities.
3. Adequate raw materials are always available. It is assumed that the pressline is the bottleneck operation--blanks are always available to feed the pressline.
4. Adequate buffer is always available. It is also assumed that there are no capacity limitations for storing completed output from the presslines.
5. Daily demand is due at the end of each day's third shift. This is also the time at which inventory calculations are made.
6. Changeover operating policy preferences are enforced. In any feasible solution, the changeover for one part type must immediately be followed by the...
|
