operation research homework

This article was downloaded by: [132.174.254.97] On: 25 February 2017, At: 11:25 Publisher: Institute for Operations Research and the Management Sciences (INFORMS) INFORMS is located in Maryland, USA Interfaces Publication details, including instructions for authors and subscription information:

http://pubsonline.informs.org Ford Motor Company Implements Integrated Planning and Scheduling in a Complex Automotive Manufacturing Environment Ada Y. Barlatt, Amy Cohn, Oleg Gusikhin, Yakov Fradkin, Rich Davidson, John Batey, To cite this article:

Ada Y. Barlatt, Amy Cohn, Oleg Gusikhin, Yakov Fradkin, Rich Davidson, John Batey, (2012) Ford Motor Company Implements Integrated Planning and Scheduling in a Complex Automotive Manufacturing Environment. Interfaces 42(5):478-491. http:// dx.doi.org/10.1287/inte.1120.0650 Full terms and conditions of use: http://pubsonline.informs.org/page/terms-and-conditions This article may be used only for the purposes of research, teaching, and/or private study. Commercial use or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher approval, unless otherwise noted. For more information, contact [email protected]. The Publisher does not warrant or guarantee the article’s accuracy, completeness, merchantability, fitness for a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, or inclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, or support of claims made of that product, publication, or service. Copyright © 2012, INFORMS Please scroll down for article—it is on subsequent pages INFORMS is the largest professional society in the world for professionals in the fields of operations research, management science, and analytics.

For more information on INFORMS, its publications, membership, or meetings visit http://www.informs.org Vol. 42, No. 5, September–October 2012, pp. 478–491 ISSN 0092-2102 (print) —ISSN 1526-551X (online) http://dx.doi.org/10.1287/inte.1120.0650 © 2012 INFORMS Ford Motor Company Implements Integrated Planning and Scheduling in a Complex Automotive Manufacturing Environment Ada Y. Barlatt Department of Management Sciences, University of Waterloo, Waterloo N2L 3G1, Ontario, Canada, [email protected] Amy Cohn Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, Michigan 48109, [email protected] Oleg Gusikhin, Yakov Fradkin Research and Advanced Engineering, Ford Motor Company, Dearborn, Michigan 48121, {[email protected], [email protected]} Rich Davidson Information Technology, Ford Motor Company, Allen Park, Michigan 48101, [email protected] John Batey Stamping Business Unit, Ford Motor Company, Woodhaven, Michigan 48183, [email protected] Ford Motor Company has designed, developed, and implemented a collective system of decision support tools, supply chain visualization methods, and optimization techniques to aid its planning and scheduling in a complex automotive manufacturing environment. Although originally developed particularly for stamping plants, the system can also be applied in other manufacturing environments where setup times play a dominant role. By enabling substantial improvements in workplace planning and production scheduling, the implementation of this system has resulted in signi cant reductions in premium freight charges, overtime wages, and inventory costs.

Key words : cyclic schedule; manufacturing; heuristic; integer programming; workforce planning. A utomotive stamping plants produce vehicle body parts, such as hoods and door panels. Stamping is one of the most complex operations in the automo- tive supply chain, supplying hundreds of part types to dozens of assembly plants and service facilities.

In this paper, we present decision support tools and optimization techniques to solve stamping planning (SP), workforce planning, and production scheduling problems. The motivation for this research stems from Ford's need to improve the ef ciency of its stamping oper- ations. Ford's stamping business unit had recognized this need for a long time; over the years, it made sev- eral attempts (at considerable cost to the company) to address the need. Those attempts failed because they did not capture the complexity of the opera- tional requirements. SP scheduling is dif cult because of (1) the general challenges found in most machine scheduling problems and (2) stamping-speci c oper- ational requirements, as we describe in the following sections.

Stamping Plant Operations The automotive stamping process begins by inserting a large roll of sheet steel into a blanking press. This press cuts the sheet steel into pieces, called blanks, that are slightly larger than the nal parts. The blanks are then passed to a stamping pressline that contains matching upper and lower dies. As a blank moves through the stamping pressline, the dies shape the blank into a three-dimensional part. These parts may then move onto subassembly and (or) assembly work- stations within the stamping plant, or be shipped 478 Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment Interfaces 42(5), pp. 478–491, © 2012 INFORMS 479directly to other manufacturing facilities for use in the nal assembly. This research focuses on creating effective cyclic workforce plans for the pressline stage of production.

Our goal is to develop a two-week schedule, to be repeated over an extended period. The pressline stage of production is the bottleneck operation because it has the most binding capacity constraints. Labor costs are the dominant costs in this system. Thus, our pri- mary objective in creating the production plan is to minimize the labor costs, subject to satisfying part demand downstream.

Solution Approach To address these challenges, we built a decision support tool, the just-in-time execution and dis- tribution information system (JEDI); Gusikhin and Klamp (2012) and Gusikhin and Rossi (2004) pro- vide more details of its structure. JEDI acquires sup- ply chain and plant oor data and integrates these data into the planning and scheduling information for visualization, decision support, and optimization (Gusikhin and Rossi 2005). In its initial implementa- tion, JEDI focused on collecting stamping plant infor- mation, presenting this information in an intuitive way, and providing decision support capabilities to enable what-if analyses for interactive production and distribution scheduling. Even with only these funda- mental capabilities, JEDI enabled schedulers to make better decisions, leading to reductions in overtime and premium freight during its rst full pilot study.

Furthermore, the underlying JEDI structure enabled and supported its subsequent enhancement with a series of novel models and algorithms that collec- tively form the stamping scheduling optimizer (SSO).

SSO generates initial high-quality production plans via JEDI and provides them to schedulers, who can make additional modi cations and conduct what-if analyses using the interactive JEDI tools. At its core, SSO uses composite variables (CVs).

CVs encapsulate multiple discrete decisions simul- taneously within a single variable, enabling certain problem constraints to be captured within the variable de nition. For example, we use CVs to represent feasible sequences of events that can be scheduled within a given shift. This enables many of the complex rules governing feasible changeovers to be embed- ded within the variables. We refer to these CVs as shift schedules, because each CV represents the com- plete activities for a feasible shift within the stamping facility. CV modeling successfully improved realism and tractability for many real-world applications with complex operational constraints in transportation and logistics; Appelgren (1969), Armacost et al. (2002), Barnhart et al. (2009, 2002), Caraffa et al. (2001), Cohn and Barnhart (2006), Cohn et al. (2007), and Crainic and Rousseau (1987) provide examples. This research, including our previous work, Barlatt et al. (2008 and 2010), is among the rst research projects to use CVs in production planning.

Results In 2004, the research team successfully transferred the JEDI system to Ford's information technology (IT) group for production implementation and full deployment across Ford's North American stamping facilities. Based on the success of this deployment, many other Ford manufacturing locations worldwide are currently evaluating JEDI. The manufacturing operations of automotive sup- pliers are often complex and highly unstable; auto- motive suppliers operate under conditions of extreme competitive pressure. In this environment, opera- tional ef ciency is essential to being successful. JEDI has helped to address these challenges. It has led to reductions in scheduled weekend overtime (e.g., an average reduction of 30 percent within the rst year) and helped schedulers best utilize available capacity (e.g., a reduction of 40 percent in excess transportation costs within the rst year, saving more than $1 million in some plants).

Stamping-Speci c Operational Requirements Each stamping pressline is assigned a speci c set of part types to produce. The key challenge in schedul- ing production for a given pressline is the changeover between dies (i.e., the setup time incurred when mov- ing from the production of one part type to another).

A changeover consists of both an external preparation and an internal dieset to change the pressline from the production of part type Ato that of type B.

First, the dies for part type Bmust be prepared. This external preparation can take place while part type ADownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment 480 Interfaces 42(5), pp. 478–491, © 2012 INFORMSis being produced, but it cannot begin before produc- tion of part type Astarts. Second, once the external preparation (which can take several hours) has been completed and after the production of part type Ahas ended, the internal dieset to the dies for part type B may take place. This can take from as little as a few minutes to as much as several hours, depending on the technology used; during this period, no parts can be produced on the pressline. This changeover pro- cess uses the concept of single-minute exchange of die (SMED) (Shing o 1996), which strives to reduce the internal changeover time (i.e., the time required to stop production of one part type and start produc- tion of another part type) by, for example, converting internal setup operations to external ones. External preparation can be done without stopping the line, whereas internal diesets require stopping it. Although the internal dieset setup time may become practi- cally negligible, the external preparation time contin- ues to be a major complicating factor in production planning. Two key operational policies govern changeovers at Ford. First, the internal dieset to Ashould be fully contained within a single shift. Second, the subse- quent external preparation time for Bshould also be fully contained in a single shift, because a single group of workers maintains full responsibility over each activity. Figure 1 illustrates proper and improper external preparation and internal dieset scheduling across two shifts, nand nC 1. The ãrepresents an internal dieset, a letter denotes production of a particular part type, and the dots represent an exter- nal preparation. We note that the workforce costs dominate all other costs in the facility. The pressline uses two types of workers: direct laborers are responsible for operating Figure 1: The external preparation denoted with the dotted lines and the internal die set changes 4ã5should be fully contained within a shift. the presslines, and indirect labor crews are responsi- ble for the external preparation and conducting the internal diesets. Each part type requires a speci c number of direct laborers to be present during pro- duction. One indirect labor crew is required dur- ing external preparation and internal dieset. Laborers must be hired for the entire planning horizon within a given shift type (i.e., rst, second, or third shift of the day). Therefore, the daily direct labor staf ng level for a given shift type is the maximum direct labor requirement across all such shifts in the plan- ning horizon, and the daily indirect labor staf ng level for a given shift type is the maximum indirect labor requirement across all such shifts in the plan- ning horizon.

Stamping Press Schedules The sequence of the part types and the time during which each part type is produced de nes a pressline schedule. Each schedule has a corresponding work- force allocation.

Table 1 illustrates a two-day sample pressline schedule. This table includes the shift number and type, the tasks completed in the shift, the number of direct laborers required (denoted by D Req.), the number of indirect labor crews (denoted by I Req.), the number of direct laborers scheduled in the shift (denoted by D Sched.), and the number of indirect crews (denoted by I Sched.). In the shift tasks column, the letter indicates the part type; “idle” indicates that the pressline is set up to produce a part type, but the workers are currently idle; ã AB indicates the time to complete the internal dieset from part type Ato part type B.

In this example, part type Arequires three direct laborers for production, Brequires four, and C requires one. Each changeover requires one indirect labor crew. The planning horizon begins by produc- ing part type Cfor eight hours in shift 1, followed by a completely idle shift; however, the pressline remains set up for part type C. The third shift produces C for one hour, then is set up to produce A.A is pro- duced for all of shift 4. In shift 5, the pressline is set up to produce B; the remainder of the shift is used for production. Bis also produced for the rst half hour of shift 6, after which the pressline is set up to produce C, which takes up the remainder of the shift.ShiftnShiftn + 1 A B A B ∆ A X X ∆ A B ∆ A B ∆∆ Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment Interfaces 42(5), pp. 478–491, © 2012 INFORMS 481Table 1: The number of direct laborers required during a shift is the maximum number of laborers for each part produced during the shift. One indirect labor crew is required for each changeover. The number of laborers scheduled for each shift type is the maximum number of laborers required across all shifts for that shift type.

Let 8d0 1 d 0 2 d 0 3 0 0 0 —i0 1 i0 2 i0 3 0 0 09 represent the labor requirements in the production schedule. Then the labor requirements for the production schedule for this example are 81 0 3 3 4 4 —0 0 1 0 1 1 9.

Using this information, we can determine the work- force allocation. Recall that the number of laborers for each shift type is the maximum across all shifts in that shift type. Let 6d 1d 2d 3 — i 1 i 2 i 3 7 represent a workforce allocation with d 1 direct laborers ( i 1 indirect labor crew) in the rst shift type, d 2 direct laborers ( i 2 indi- rect labor crew) in the second shift type, and d 3 direct laborers ( i 3 indirect labor crews) in the third shift type. Thus, the workforce allocation for this example is 63 4 4 —0 1 1 7.

The objective of the pressline workforce planning problem is to minimize the cost of labor subject to the following constraints.

1.Three eight-hour shifts operate each day.

2.All daily demands must be met on time.

3.Production of a given part type can only take place when the pressline is set for that part.

4.Changeover operating policy constraints are enforced. The internal dieset for a given part type cannot occur until the external preparation has been completed. External preparation for a pressline cannot begin until the prior internal dieset on the pressline has been completed. Production for a pressline can- not occur while an internal dieset is taking place on the pressline. Each internal dieset must be conducted completely within a single shift. Each external prepa- ration must be conducted completely within a single shift. 5.Labor requirements are enforced. Production cannot occur unless the correct number of direct laborers are present at the pressline. Internal diesets and external preparation cannot occur unless the cor- rect number of indirect labor crews are present at the pressline.

6.Laborers must be hired for the entire planning horizon within a given shift type.

7.Laborers are shared among the machines in the pressline zone, which is a department within the stamping plant that shares a crew of direct and indi- rect laborers among several presslines.

Assumptions The assumptions for the stamping workforce plan- ning problem are as follows: •Adequate raw materials are always available.

Because the pressline is the bottleneck operation, blanks are always available to feed the pressline.

•Adequate storage space is always available. We also assume no capacity limitations for storing com- pleted output from the presslines.

•Initial inventories can be decision variables or input parameters. We do not require inventory levels to be speci ed as inputs. We allow the user the option of specifying the inventory values as inputs or as vari- ables, allowing the model to determine the inventory levels. •The problem is static, deterministic, and repeat- ing. The goal is to develop a two-week schedule, to be repeated over an extended period, composed of at most three shifts per weekday. Although demand Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment 482 Interfaces 42(5), pp. 478–491, © 2012 INFORMSmay vary from day to day over the two-week hori- zon, we assume that the inventory levels at the start and end of the planning horizon are the same. The production environment is not fully de- terministic— uctuations in daily demand and yield, machine failures, and other disruptions will occur.

Thus, SSO is used to create an initial basic schedule, and the scheduler modi es this schedule within JEDI daily to recover from minor deviations resulting from daily variability.

Challenges A stamping production plan has two components:

the workforce allocation (i.e., the number of labor- ers of each type available during each shift type in the planning horizon) and the workforce utilization (i.e., the production schedule). Solving the workforce allocation and utilization problem simultaneously is challenging for three reasons. The rst is the com- plexity of the rules regarding when and how part type changeovers can occur. The second relates to the rules requiring laborers for one shift to be hired for all shifts of that type across the planning horizon.

The third is the sharing of laborers across multi- ple presslines. These challenges introduce tremendous computational complexity into traditional mathemat- ical programming modeling and solution techniques.

In the next section, we present our approaches to overcoming the challenges.

Solution Approach As we quickly discovered when we began this re- search, using a traditional mixed-integer program- ming (MIP) approach for even a single pressline is intractable because of the inherent weakness of the linear program (LP) relaxation, which is common to many machine scheduling problems, and the com- plexities associated with modeling the changeover requirements.

Therefore, we instead developed SSO, which con- tains of a series of four phases solved in succession, with the solution from each phase providing a useful bound for the subsequent phases.

This approach builds upon two ideas developed in Barlatt et al. (2008): shift schedule variables and test and prune (T&P). We will rst give some background information on these two ideas before explaining how they are applied within the four SSO phases. Shift Schedule Variables A shift schedule variable is a variable that represents an entire feasible shift of production. For example, we de ne one shift schedule to represent workers pro- ducing part type Afor eight hours. Another shift schedule represents workers producing part type B for the rst hour, changing over to part type A, and then producing Afor the remainder of the shift. Note that this variable de nition allows us to not require that batch sizes, number of changeovers, labor avail- ability, or sequencing of part types be restricted or prede ned to achieve tractability, as is often the case in most machine scheduling literature. In addition, we are able to allow sequence-dependent changeover times and demand-speci c due dates, which are also enhancements over much of what is in the literature. When using CVs, the goal is to embed complexity within the variable de nition to simplify the objec- tive function and (or) complicating constraints. In the stamping scheduling problem, the complexity is largely shift speci c. For example, changeovers must be fully contained within a shift, and workforce cal- culations are also made at the shift level. Therefore, we de ne CVs for this problem to represent a feasi- ble set of ordered tasks that can be completed in an individual shift. By de ning the variables in this way, many of the constraints are automatically enforced—a shift schedule is not de ned if it does not satisfy the operational rules associated with changeovers.

Additionally, each shift schedule has associated char- acteristics (e.g., tasks worked on, duration of tasks, number of changeovers) that can be used in con- straints, and the objective function; see Figure 2 for some feasible examples. Of course, the number of possible shift schedule variables is in nitely large. One way to overcome this challenge, similar to that seen in much of the CV literature, is to limit the number of candidate vari- ables by discretizing time. For example, we might only consider production in half-hour increments and then enumerate the corresponding set of valid shift schedules. However, because of the combinatorial aspect of scheduling more than one job in a shift, this number might still be quite large. Thus, this dis- cretization might result in the need for delayed col- umn generation. Furthermore, this restriction of theDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment Interfaces 42(5), pp. 478–491, © 2012 INFORMS 483Figure 2: Shift schedule variables represent an entire feasible shift of pro- duction. A shift schedule is not de ned if it does not satisfy the operational rules associated with changeovers. We de ne a small number of extreme shift schedules in the model. Convex combinations of extreme shift sched- ules represent every feasible shift schedule.

solution space can decrease the quality of the result- ing schedule. In Barlatt et al. (2008), we show that we only require a few speci cally designed variables, which we refer to as extreme shift schedules, to capture the entire feasible region; we can easily capture the other oper- ational requirements with linear constraints. The con- vex combination of extreme shift schedules de nes the entire feasible region. Using the extreme shift schedules reduces the number of variables, allows the extreme shift schedules to be continuous rather than integer, and re nes the granularity. By using these extreme shift schedules, we both decrease the num- ber of variables (relative to this proposed, discretized- time approach) and increase the solution quality by implicitly incorporating all possible shift schedules. For example, a shift schedule in which part type A is run for four hours, followed by four hours of idle time, can also be represented by taking the average of two shift schedules, one with eight hours of pro- ducing Aand the other with eight hours of idle time (during which the pressline is set for part A). Any combination of production of Aplus idle time can be found by taking a convex combination of these two extreme shift schedules. We can identify extreme shift schedules when more than one part type is also pro- duced in a shift. By using this approach, we achieve three bene ts that are critical in achieving tractability. 1.A convex combination of extreme shift sched- ules is also feasible and captures all the complex changeover constraints. Thus, the number of variables is greatly reduced. Each shift has only two extreme shift schedules per part type (one with eight hours of production and one with eight hours of idle but set for production) and four extreme shift schedules for each ordered pair of part types. Thus, an instance with 10 part types would have only 380 extreme shift schedules. We contrast this with other CV models, which often have variables numbering in the millions or even billions (e.g., the airline crew pairing prob- lem), as Crainic and Rousseau (1987) discuss. 2.The solution set is exhaustive. We do not need to discretize, which would decrease solution quality, to ensure tractability. We can represent the entire feasible region with a small set of variables in the model at the start, thus negating the need to generate any columns. 3.The extreme shift schedule variables become continuous, greatly reducing the number of integer variables in the model and the corresponding amount of branching. This approach also has a signi cant implementation bene t—we can use a commercial integer program- ming solver (e.g., CPLEX) directly instead of coding the algorithm, as is required with column generation within a branch-and-bound framework. This makes the extreme schedule approach faster to implement and solve than a column generation approach.

The nal implementation bene t of this approach is that we can further limit the extreme shift schedules included in the model if the user has speci c require- ments of the solution. For example, if the user does not want part type Ato be followed by part type B within a shift, we can simply remove the extreme shift schedules that correspond to that situation.

Test and Prune Despite the bene ts of the using shift schedule vari- ables to capture the changeover constraints, and extreme shift schedules to reduce the number of vari- ables, signi cant fractionality still exists with regard to the remaining auxiliary variables in the model, leading to signi cantly long run times for several instances. As an alternative solution approach, we developed T&P, a new algorithm for solving resource allocation and utilization problems. To motivate this algorithm, con- sider the following two observations. 1.The number of possible workforce allocations is nite. Although an in nite number of distinct feasi- ble sequences and durations of production runs exists,A A∆ AB ∆AB ∆BA BB A-idle B-idle Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment 484 Interfaces 42(5), pp. 478–491, © 2012 INFORMSthe number of unique workforce allocations is dis- crete, nite, and often quite small. Many feasible production schedules will correspond to a common workforce allocation, which in turn determines the solution cost.

2.When the workforce allocation is xed, the remaining problem is a feasibility problem. If we know the workforce allocation, then the problem that remains is nding a feasible production plan that does not exceed the allocated workforce. Computational experiments for the stamping case studies show that this feasibility problem is typically easy to solve. The basic concept behind T&P is to iteratively search over all possible workforce allocations; in each iteration, we test the feasibility of a speci c workforce allocation (e.g., can we meet the demand if we hire 10 workers for the rst shift type, 8 for the second, and 6 for the third?). If a feasible production sched- ule exists, we can reduce the set of allocations that must be tested by disregarding any allocation with higher cost, because such allocations will all be sub- optimal. If a feasible production schedule does not exist for a given workforce allocation, we can reduce the search space by removing any allocation with fewer resources in each shift type because such alloca- tions will also be infeasible. Any allocation with fewer resources will also be infeasible. We found that T&P can yield provably optimal solutions much faster than branch and bound.

Stamping Scheduling Optimizer Based on the background information above, we can describe the four phases in JEDI's SSO. In Phase 1, we nd an upper bound on the overall problem, solv- ing each pressline independently to nd the mini- mum workforce allocation needed for that machine.

Note that this neglects the possible synergies that can be found by sharing workers across presslines.

In Phase 2, we improve upon this upper bound by solving the rotation model (see Rotation Modelin the appendix), which loops through all potential starting points for each (cyclic) schedule to leverage syner- gies across presslines and reduce costs. In Phase 3, we establish a lower bound via the aggregate work- force model (see Aggregate Workforce Model in the appendix), which aggregates the demands for indi- vidual part types into general bounds on the amount of labor needed. In some cases, the optimal solution to the aggregate workforce model is also operationally feasible. In these cases, we are nished and the SSO returns the solution to the aggregate workforce model to JEDI. However, when the optimal solution to this model is not operationally feasible, we enter Phase 4, the multiple machine feasibility algorithm.

This heuristic makes the operationally infeasible solu- tion to the aggregate workforce model problem feasi- ble by adding additional workers. Figure 3 provides an overview of the approach. In the next sections, we will use a pressline zone example with two presslines, and ‚, to illustrate our approach. Assume that pressline produces part types A,B, C , and D, and pressline ‚produces part types Eand F. Table 2 summarizes the key informa- tion about the machines and products. We assume a planning horizon of four days (12 shifts).

Phase 1: Set Upper Bound Recall that we can use T&P and the single-machine model to obtain an optimal workforce allocation for each pressline, assuming no sharing of labor across presslines. After nding the optimal solution for each machine individually, we can quickly establish an upper bound on the pressline zone by simply sum- ming together these workforce allocations. Figure 4 depicts optimal schedules for machines and ‚. The optimal workforce allocation found for machine is 66 6 3 —0 1 0 7, and the optimal alloca- tion for machine ‚is 62 3 0 —0 1 0 7. The upper bound established at the end of the rst phase is therefore 6 8 9 3 —0 2 0 7.

Phase 2: Reduce Upper Bound The second phase uses the single pressline solutions as input and looks to reduce the upper bound estab- lished in the previous phase by rotating the produc- tion schedules. Recall that the two-week planning horizon is cyclic; we can thus rotate each individ- ual pressline's schedule to try to reduce the over- all cost for the pressline zone. The rotation model is an MIP with variables z mn , which equal 1 if shift n on machine mis rotated to be the rst shift, and 0 otherwise.

Figure 5 illustrates this example for presslines and ‚, showing the original schedules for presslinesDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment Interfaces 42(5), pp. 478–491, © 2012 INFORMS 485Figure 3: At each of the solution approach's four phases, we establish or improve bounds to determine a solution to the problem.

and ‚and the rotated schedule (denoted as ‚0 ).

The resulting pressline zone workforce allocation after using this rotation model is 66 8 3 —0 2 0 7, requiring two fewer direct laborers in the rst shift type and one fewer in the second shift type compared to the result of Phase 1. To obtain this lower-cost solution, ‚was rotated, moving what had been shift 7 to shift 1.

Phase 3: Establish Lower Bound In this phase, we take a new perspective to establish a lower bound on the optimal workforce allocation.

Number of Product name Machine Total demand (hrs) workers required A 0075 2 B 18055 3 C 5093 6 D 806 2 E ‚ 703 3 F ‚ 3205 2 Table 2: The table summarizes key data for a ctional pressline zone to illustrate the solution approach. The ctional pressline zone has two presslines. Pressline produces part types A, B, C, and D; pressline ‚ produces part types Eand F. Rather than looking at each part type individually, we aggregate all part types that have a common labor requirement (i.e., that require the same number of direct laborers). Table 3 illustrates this aggregation for our simple example.

Within the aggregate workforce model, we use the shortest sequence-dependent setup time between aggregate part types to establish a lower bound. For example, on pressline , we determine the internal dieset time when changing from the aggregate part type of all parts requiring two direct laborers to the aggregate part type associated with all part types requiring three direct laborers, by taking the mini- mum between ã AB and ã DB . We do the same with the external preparation time. The aggregate workforce model has shift schedule variables that represent changing from one aggregate part type to another. We use these variables in an integer programming formulation. In the constraints, we ensure that the aggregate demand is met and that at least one changeover occurs for every part type that requires that number of workers (e.g., there must be at least two changeovers to the aggregate part type requiring two workers on pressline ). Because the0 Solution cost∞ Single machine model Rotation model Multiple machine feasibility Aggregate workforce model Phase 4:

Make lower bound feasible (if necessary) Phase 3:

Establish lower bound Phase 2:

Reduce upper bound Phase 1:

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment 486 Interfaces 42(5), pp. 478–491, © 2012 INFORMSFigure 4: The gure illustrates the initial solution to Phase 1 of the approach for the pressline zone example.

Figure 5: The gure illustrates the Phase 2 solution for the pressline zone example. This new rotated solution (denoted machines and ‚0 ) requires two fewer direct laborers in the rst shift type and one fewer in the second shift type compared to the result of Phase 1 (denoted machines and ‚).Shift Machine Machine 1 2 3 4 5 6 7 8 9 10 11 12 B C C C- idle ∆CA ∆DC ∆BD A A-idle A-idle ∆AB B B E-idle E F F F C-idle F D D C-idle ∆FE ∆EF E F F F-idle F-idle F-idle F-idle E-idle ShiftMachine Machine 1 2 3 4 5 6 7 8 9 10 11 12 B C C C-idle A ∆AB ∆CA B B E F F F ∆DC C-idle F D ∆BD ∆FE ∆EF D C-idleE-idle E-idle F-idle F-idle F-idle E F F Machine F F F F E F E ∆EF ∆FE F F-idle F-idle F-idle F-idle E-idle E-idle A-idle A-idle F-idle Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment Interfaces 42(5), pp. 478–491, © 2012 INFORMS 487Number of workers required (aggregate part type) Machine Total demand (hrs) Part types (s) 2 0075 C806 D 9035 A1 D 3 18.55 B 6 5.93 C 2 ‚7.3 F 3 ‚32.5 E Table 3: This table displays the aggregate part types for the pressline zone example. Part types are aggregated by the number of direct laborers required.

number of distinct direct labor requirements is quite small compared to the number of parts produced on the pressline, the number of aggregate products is also quite small, enabling us to concurrently consider all presslines within a zone. Table 4 highlights the differences between the prob- lems solved in Phases 1 and 3. First, Phase 1 pro- vides an upper bound, whereas Phase 3 provides a lower bound. Second, Phase 1 nds the optimal workforce allocation for each pressline independently, without considering any other presslines in the zone.

Phase 3 simultaneously considers all the presslines in the zone. Third, in Phase 1, the shift schedule vari- ables represent actual part types; in Phase 3, they rep- resent aggregate part types. A disadvantage of Phase 3 is that the production schedule solution might not be operationally feasible.

Therefore, we end this phase by checking if the pro- duction schedule that it produced is feasible for the original problem. If not, we move to Phase 4 to mod- ify the solution, ensuring feasibility. We note that the performance of Phase 3 can be greatly enhanced by using good upper bounds found in Phases 1 and 2. Table 5 illustrates the Phase 1 Phase 3Provides: An upper bound A lower bound Math model considers: Each machine All machines in the individually zone simultaneously Shift schedules represent: Actual products Aggregate products Operationally feasible Yes Maybe solution:

Table 4: This table compares the differences between the models solved in Phases 1 and 3. Zone with Presslines and ‚ ve presslines Total number of allocations 27,000 1,061,208 With Phases 1 and 2 upper bound 404 18,692 Table 5: This table compares the number of workforce allocations that must be considered by the T&P algorithm with and without Phases 1 and 2. The table shows that using the bounds from Phases 1 and 2 eliminates a signi cant number of possible solutions.

computational impact of using the Phases 1 and 2 upper bounds on Phase 3 performance.

Phase 4: Make Lower Bound Feasible We use the multiple machine feasibility algorithm to convert an infeasible workforce aggregate produc- tion schedule to a feasible one. In this algorithm, we look at the labor requirements in the production schedule—the number of workers (both direct and indirect) assigned to each pressline during each shift in the planning horizon. We de ne the slack as a situ- ation in which the workforce allocation provides more laborers than the production schedule requires during that shift. Let us assume that the lowest-cost alloca- tion found during Phase 3 is 66 6 3 —0 2 0 7. Assume also that the labor requirements in the production sched- ule for are 83 2 2 0 6 0 6 2 0 3 3 0 —0 1 0 0 1 0 0 1 0 0 1 0 9and the labor requirements in the production schedule for machine ‚are 82 2 0 2 0 0 0 0 3 0 2 0 —0 0 0 0 0 0 0 1 0 0 1 0 9.

All shifts, except shifts 5, 7, and 9, have direct laborer slack. For example, the number of direct laborers required in shift 1 is 5 43 C 25; therefore, a slack of one direct laborer exists. Shift 2 and shift 5 are the only shifts with indirect laborer crew slack; these shifts only require one indirect labor crew, but two are available.

We can then use the single-machine model to check if this allocation of workers to each shift (plus any slack in that shift) in the planning horizon is feasible. If we nd a feasible production schedule, we update the slack based on the number of required workers in the production schedule and move to the next pressline; otherwise, we increment the number of workers allo- cated to that pressline. We keep adding workers until we can nd a feasible production schedule or we reach the bound provided by Phase 2.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment 488 Interfaces 42(5), pp. 478–491, © 2012 INFORMS1.For the labor requirements for the ith machine in the zone, check if a schedule that can be made with the workforce allocated from the aggregate workforce model (plus any remaining slack) is feasible; (a)If feasible, update the slack and go to Step 3; (b)If infeasible, increase the workers available and go to Step 2.

2.Check to see if the current workforce allocation has lower cost than the upper bound provided in Phase 2; (a)If yes, go to Step 1; (b)If no, stop.

3.If iD the number of presslines in the zone, stop; else, increment iand go to Step 1.

Implementation Figure 6 presents an overview of how JEDI creates and displays productions plans. When creating production plans, the scheduler interacts with two JEDI user interfaces: the produc- tion planning interface and the scheduling interface.

The scheduler sets the optimization parameters (e.g., the presslines to consider) in the production planning interface. The information on the JEDI server and from the production planning interface is then passed to the central optimization server and the SSO begins.

The result of the SSO optimization is then passed back to the scheduler 's workstation and displayed via the scheduling interface. The scheduling interface, which is interactive, allows the scheduler to view and edit the schedule. Figure 6: High-level JEDI architecture: JEDI has three main elements: (1) the JEDI server where the corporate business data (e.g., material require- ments planning (MRP) data and plant oor data (e.g., changeover time and production rates)) are collected and consolidated, (2) decision support user interfaces accessed via the scheduler's workstation, and (3) the SSO. Gusikhin and Klamp (2012) provide more details on the JEDI architecture. It provides a block diagram, similar to a Gantt chart, for the schedule representation. This chart displays the changeover start time, changeover duration, and production run time for each batch of parts. Once the SSO solution has populated the scheduling inter- face, the scheduler can analyze and manually adjust the schedule. Once this analysis (and modi cations) is complete, the schedule is accepted and is passed back to the JEDI server for use in updating the MRP system and the requirements of the upstream supply chain.

It is important to note that the scheduler can set restrictions on the schedule before initiating the SSO in JEDI's scheduling interface. By limiting the extreme shift schedule variables used within the optimization, we enforce these restrictions within SSO (see the Shift Schedule Variables section).

Use Cases JEDI can be used to create production plans for two use cases: 1.Pressline zone optimization, which is this paper 's focus, is used for resource planning over long plan- ning horizons (i.e., of at least four weeks). Pressline zone optimization is also necessary when new prod- ucts are introduced and (or) customer demand requirements have changed substantially. To solve these problems, we use all four phases of the SSO.

2.Individual pressline optimization is used for operational decision analysis (e.g., within two weeks).

It provides schedules for a pressline to get back on plan after a disruption or to make adjustmentsJEDI server Corporate business data Plant floor dataCentral optimization server Decision support user interface Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment Interfaces 42(5), pp. 478–491, © 2012 INFORMS 489because of minor changes in the customer demand requirements. Individual pressline optimization is particularly useful for presslines that have a large number of jobs with signi cantly different labor requirements. To solve these problems, we use only Phase 1 of the SSO.

Bene ts In the previous sections, we focused on the SSO's technical components and its implementation within JEDI. However, perhaps the synergies gained by the integration of SSO within the JEDI environment might be even more important. Production schedul- ing algorithms (including SSO) typically assume xed and known input data; this assumption is usually necessary to ensure computational tractability. How- ever, real manufacturing environments are dynamic and constantly changing. Given the high-quality ini- tial production plans generated by SSO, the other capabilities of JEDI then allow the user great exi- bility and power in adjusting the initial schedule in response to such changing circumstances as disrup- tions and variations in demand. Furthermore, once a change has been made, SSO provides a mecha- nism for quickly recovering from the current state back to the original production plan. It is also worth noting the various levels of planning for which the SSO within the JEDI system can be used. For exam- ple, long-term production and workforce plans can be created to determine the resources required for an extended period. In addition, more tactical plans can be developed based on the resources allocated in the long-term plan. JEDI, a collective system of decision support tools, supply chain visualization methods, and optimiza- tion techniques has provided signi cant bene ts to Ford, including substantial nancial savings associ- ated with reductions in premium freight, labor costs, and inventory. In addition, it has provided less tangi- ble bene ts associated with improved scheduling and manufacturing execution control. Although the spe- ci c nancial bene ts of JEDI depend on the complex- ity of the given plant environment, the savings that have typically been observed after the rst year of a JEDI launch include a 30 percent average reduction of overtime labor costs and a reduction of premium transportation costs by 40 percent, thus saving more than $1 million per year at some plants. JEDI has been used successfully to manage complex automo- tive stamping operations at multiple locations for several years, facilitating sustained improvements in operating performance.

Finally, we conclude by noting that JEDI's bene ts are not limited to stamping. The JEDI model, in com- bination with SSO, is built on general concepts of the automotive supply chain. Other operations in Ford's global network are exploring and piloting this system.

Appendix. Rotation Model Sets • M: the set of presslines.

• N: the set of shifts.

• H: the set of shift types.

Parameters • mn : the number of direct laborers for each shift n2 N on pressline m.

• — mn : the number of indirect labor crews for each shift n 2 N on pressline m.

• h n: the shift type of shift n2 N (e.g., h415 D h445 D h4 75 D rst).

• cd h : the cost of direct laborers assigned to shift type h.

• ci h : the cost of indirect laborers assigned to shift type h.

Variables • q mn D 1 if the rst and —for pressline mstarts on shift n.

• yd h : the number of direct laborers assigned to shift type h.

• yi h : the number of indirect labor crews assigned to shift type h.

Objective minX h 2 H y d h cd h C X h 2 H y i h c i h 0 (1) Constraints q00 C q 01 C q 02 D 11 (2) X n 2 N q mn D 1 8m 2M 1 (3) X m 2M 1 n 0 2 N 2 n 0 n m4n ƒn0 C 15q mn C X m 2M 1 n 0 2 N 2 n 0 >n m4 —N —ƒ nƒ n0 ƒ 15q mn yd h 8 n 2 N 1 (4) X m 2M 1 n 0 2 N 2 n 0 n— m4n ƒn0 C 15q mn C X m 2M 1 n 0 2 N 2 n 0 >n — m4 —N —ƒ nƒ n0 ƒ 15q mn yi h 8 n 2 N 1 (5) q mn 2 80 11 90 (6)Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Constraint 2 limits the rotation of the pressline to only the rst three shifts; this reduces symmetry in the formulation.

Constraint 3 assigns one shift to be the rst shift for each pressline in the zone. Constraints 4 and 5 determine the number of direct laborers and indirect labor crews needed on each shift based on the number of shifts rotated.

Aggregate Workforce Model Sets • M: the set of presslines in the zone.

• J m :

the set of aggregate labor shift schedules for pressline m; this is the number of direct laborers assigned to each shift during the day. • K m:

the number of possible direct laborers on pressline m (e.g., for pressline ‚in the example, this is 80 1 21 39).

• N: the set of shifts.

• H: the set of shift types.

Parameters • p mk : the number of products that require kdirect labor- ers on pressline m.

• d mk : the total demand for knumber of direct laborers (hours) on pressline m.

• ai h : the number of indirect labor crews assigned within the given workforce allocation. • ad h : the number of direct laborers assigned within the given workforce allocation.

• f mj k D 1 if kdirect laborers are required to start the shift in aggregate labor shift schedule jon pressline m.

• l mj k D 1 if kdirect laborers are required to end the shift in aggregate labor shift schedule jon pressline m.

• „ mj D 1 if aggregate labor shift schedule jincludes a changeover on pressline m.

• q mj k : the duration of time assigned to kdirect laborers in aggregate labor shift schedule jon pressline m.

• h n: the shift type of shift n8n 2 N (e.g., h415 D h445 D h4 75 D rst).

Variables •0 z mnj 1 is the proportion of aggregate labor shift schedule jassigned to shift non machine m.

• vf mnk D 1 if kdirect laborers are assigned to start shift n on pressline m, 0 otherwise.

• vl mnk D 1 if kdirect laborers are assigned to end shift n on pressline m, 0 otherwise.

• ƒ mn D 1 if shift nhas a changeover on pressline m, 0 otherwise. • u mnk D 1 if kdirect laborers are used on pressline m during shift n, 0 otherwise. Constraints X j 2 J m z mnj D 1 8m 2M 1 n 2N 1 (7) X n 2 N X j 2 J m q mj k z mnj d mk 8 m 2M 1 k 2K m1 (8) X j 2 J m f mj k z mnj D vf mnk 8 m 2M 1 n 2N 1 k 2K m1 (9) X j 2 J m l mj k z mnj D vl mnk 8 m 2M 1 n 2N 1 k 2K m1 (10) X j 2 J m „ mj z njm D ƒ mn 8 m 2M 1 n 2N 1 (11) v l mnk D vf m4n C15k 8 m 2M 1 k 2K m1 n 281 0 0 0 —N — ƒ 191 (12) v l m —N —k D vf m 1k 8 m 2M 1 k 2K m1 (13) X m 2M ƒ mn ai h n 8 n 2 N 1 (14) X m 2M X k 2 K m ku mnk ad h n 8 n 2 N 1 (15) X n 2 N X j 2 J m 2 l mj k D 1 and „ mj D 1z mnj p mk m 2M 1 k 2K m1 (16) v f mnk 1 vl mnk 1 u mnk 1 ƒ mn 2 80 1 190 (17) Constraint 7 assigns an aggregate labor shift schedule to each shift in the planning horizon. Constraint 8 enforces that each schedule must meet the demand. Constraints 9 and 10 determine how many direct laborers are assigned to each pressline to start and end its shift. Constraint 11 deter- mines if a changeover is completed during each shift in the planning horizon on each pressline. Constraint 12 ensures that the number of direct laborers assigned to the end of shift nequals the number of direct laborers who begin shift n C 1; this ensures that the production schedule will ow properly. Constraint 13 ensures that the schedule is cyclic by stipulating that the number of direct laborers required at the end of the last shift is equal to the number of direct laborers required at the beginning of the rst shift. Con- straints 14 and 15 enforce the workforce allocation given by T&P; these constraints limit which aggregate labor shift schedules can be assigned to shifts based on the number of laborers required. Constraint 16 enforces the fact that there should be at least one changeover for each product that the aggregate product represents in the schedule. Note that this formulation has no objective because it is a feasibility prob- lem within T&P.

Acknowledgments We would like to acknowledge the contribution from many people at Ford Stamping, Material Planning and Logistics, and Information Technology (IT) for their continual sup- port of this project. Speci cally, we would like to acknowl- edge Edward Zvoch, James Higgins, Craig Morford, Mark Catri, and Robert Quick from Stamping, Kasey KasemodelDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.

Barlatt et al.:

Planning and Scheduling in a Complex Manufacturing Environment Interfaces 42(5), pp. 478–491, © 2012 INFORMS 491and Serguei Vassiliev from IT, and Giuseppe Rossi and Erica Klamp from Ford Research and Advanced Engi- neering, for their invaluable contributions. We also grate- fully acknowledge the work of Kamal Aman and Willie Cheong at the University of Waterloo in implementing the test version of the code. This work was supported by the Ford–University of Michigan Alliance, the National Sci- ence Foundation, and the Natural Sciences and Engineering Research Council of Canada.

References Appelgren LH (1969) A column generation algorithm for a ship scheduling problem. Transportation Sci.3(1):53–68.

Armacost A, Barnhart C, Ware K (2002) Composite variable for- mulations for express shipment service network design. Trans- portation Sci. 35(1):1–29.

Barlatt A, Cohn A, Guisikin O (2010) A hybridization of mathe- matical programming and dominance-driven enumeration for solving shift-selection and task-sequencing problems. Comput.

Oper. Res. 37(7):1298–1307.

Barlatt A, Cohn A, Guisikin O, Fradkin Y, Morford C (2008) Using composite variable modeling to achieve realism and tractability in production planning: An example from automo- tive stamping. IIE Trans.41(5):421–436. Barnhart C, Farahat A, Lohatepanont M (2009) Airline eet assign- ment with enhanced revenue modeling. Oper. Res.57(1):

231–244.

Barnhart C, Kniker T, Lohatepanont M (2002) Itinerary-based air- line eet assignment. Transportation Sci.36(2):199–217.

Caraffa V, Ianes S, Bagchi T, Sriskandarajah C (2001) Minimizing makespan in a blocking owshop using genetic algorithms.

Internat. J. Production Econom. 70(2):101–115.

Cohn A, Barnhart C (2006) Composite-variable modeling for service parts logistics. Ann. Oper. Res. 144(1):17–32.

Cohn A, Root S, Wang A, Mohr D (2007) Integration of the load matching and routing problem with equipment balancing for small package carriers. Transportation Sci.41(2):238–252.

Crainic T, Rousseau K (1987) The column generation principle and the airline crew scheduling problem. INFOR25(2):136–151.

Gusikhin O, Klamp E (2012) JEDI: Just-in-time execution and dis- tribution information support system for automotive stamping operations. Armbruster D, Kempf KG, eds. Decision Policies for Production Networks (Springer, London), 119–142.

Gusikhin O, Rossi G (2004) Improving automotive supplier oper- ations through information logistics. Sandkuhl K, Smirnov A, Weber H, eds. The Knowledge Gap in Enterprise Information Flow (Jonkoping University, Jonkoping, Sweden), 81–90.

Gusikhin O, Rossi G (2005) Well-connected: MES data integration in the automotive supply chain. APICS Performance Advantage 15(2):32–35.

Shing o S (1996) Quick Changeover for Operators: The SMED System (Productivity Press, Portland, OR).Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:25 . For personal use only, all rights reserved.