Integer Programming - Formulations

INTRODUCTION TO INTEGER LINEAR PROGRAMMING WAREHOUSE LOCATION Prof. Stephen Graves A firm wants to decide where to locate its warehouses to best serve its customer base. It has aggregated the customer base according to three-digit zip code regions; for each aggregate customer, the firm has estimated the annual product demand for that region. The firm has also generated a list of candidate warehouse sites; for each candidate site, the firm has estimated the annual fixed cost for opening and operating the warehouse, the per-unit transportation costs for supplying the warehouse from the firm's production facilities, and the per-unit transportation costs for supplying each aggregate customer from this warehouse. In addition to minimizing costs for distribution, the firm insists that the warehouse service to each customer meet some minimum service threshold, e. g., delivery within 24 hours. A SPARE PARTS PROBLEM An office equipment company has a crew of field representatives who provide service to the company's customers. When an installed piece of equipment (a photocopier) fails, a field representative is sent to attempt to diagnose and repair the equipment. In order to be able to complete the repair on site, the field representative carries an inventory of spare parts. If the repair requires the replacement of parts that the field rep does not have on hand, then the field rep must return to the local sales office or warehouse for the part and then turn around and return to the customer site. This greatly increases the amount of time the customer is inconvenienced due to the failed copier. However, since the field representative must carry the spare parts in his/her vehicle, there is a physical limit on how many different types of spare parts can be carried. Furthermore, it is very hard to anticipate what parts are needed on any particular repair job; in most instances the customer is not able to provide very helpful diagnostic information when reporting a failure. Suppose that there are 100 replaceable parts in the copier, and that pj, j = 1, 2, ... 100, is the probability that part j is needed to complete a repair, given that the copier has failed. For simplicity, assume that the probability of requiring part i is independent of the probability of requiring part j, for all pairs i, j. Let sj be the space consumed by part j, and suppose that the field rep's vehicle can carry 40 cubic feet of spare parts. FIXED CHARGE PROBLEM The cost function for many production activities consists of a fixed component and a variable component. If there is no production activity, the cost is zero. If there is any production activity at all, then a fixed cost is incurred; this often will correspond to a setup or changeover cost. Beyond the fixed cost, there may be a variable cost that is proportional to the amount of production. Sometimes, if we talk about the production cost function for a production department or line, there may be several fixed charges depending upon the number of shifts to be run (or some other measure of activity). There may be a fixed charge for operating the first shift; this would include overhead and indirect costs required to keep the facility open and operate the department. If two shifts are to be run, there will be a fixed charge for each shift, with the charge for the second shift usually smaller than for the first. Similarly, there are three fixed charges if three shifts are running. To this, we need add the variable production costs, where the variable cost rate may also depend upon the shift. Here it would be common to expect that the variable cost rate for the first shift to be lower than for the second, which is lower than the third shift. APPROXIMATING NON LINEAR FUNCTIONS Suppose we wish to minimize a piece-wise linear cost function; let x denote the decision variable and c(x), the cost function, is specified as follows: dc(x) = 2 for 0 ≤ x ≤ 5 ; dx dc( x ) = 1 for 5 ≤ x ≤ 12 ; dx dc( x ) = 3 for 12 ≤ x ≤ 18 . dx We can model c(x) with integer variables so that the minimization of c(x), subject to various constraints on x, can be solved as an integer program. c(x) = 2x1 + x2 + 3x3 x = x 1 + x2 + x 3 5y1 <= x1 <= 5 ; 7y2 <= x2 <= 7y1 ; 0 <= x3 <= 6y2 and y1 = 0 or 1; y2 = 0 or 1. LOGICAL CONSTRAINTS 1. Mutually exclusive alternatives - pick at most one from a set: n ∑x i =1 i ≤ 1 2. contingent decisions: if j then must have i: xi >= xj if j, then cannot have i: 1 - xj >= xi n 3. set covering - at least one from a set must be chosen: ∑x i =1 i ≥ 1 ROUTING AND SCHEDULING PROBLEMS The best-known routing/scheduling problem is the so-called traveling salesman problem given N cities to visit, create a minimum-cost or minimum-length tour that originates in a given city, visits each city exactly once and returns to the city of origin. This problem, while quite important in its own right, is the fundamental sub-problem for more complex vehicle-routing and machine-scheduling problems. The traveling salesman problem is also the standard benchmark for testing and evaluating new combinatorial-optimization algorithms. CUTTING STOCK PROBLEM A firm that manufactures oil-drilling rigs purchases steel beams from a steel supplier. The steel supplier will deliver a batch of beams at a time. The steel beams come in varying lengths that range from 38 feet to 42 feet, and will vary both within a batch and from batch to batch. The firm uses the beams to make brackets, and the first step in the fabrication process is to cut the beams to the bracket length. The bracket lengths can be 6 feet, 7 feet, 8 feet, or 10 feet. Given a batch of beams and given a set of requirements for brackets, the firm must decide how to cut the beams so as to minimize trim loss. As a simple example, suppose we have on hand 10 forty-foot beams and we need to produce the following: 10 8 15 8 6' brackets 7' brackets 8' brackets 10' brackets How should the beams be cut to minimize material usage? FORWARD PLANNING FOR AUTOMOBILE COMPONENTS [From Michael J. Chrzanowski’s LFM thesis, Development of a Manufacturing and Business Planning Tool to Aid in Forward Planning, 1993] Consider a manufacturing enterprise that produces a family of automobile components at several manufacturing locations. About two dozen items represents 80% of the enterprise's manufacturing volume. There are five locations; the locations differ in terms of their manufacturing processes, their production rates, their costs, and their capacities. The forward planning process determines which products are to be made at what locations. These decisions are complicated by the fact that the allocation decision depends on investment decisions, which need to be determined concurrently. In order to manufacture a product at a particular location may require an investment or investments at the location. These investments are associated with product features, and result in the location having the capability of producing any product with a specific feature. Thus, a particular investment at a location may be applicable to more than one product. COMPONENT ASSIGNMENT (From Dennis J. Arnow’s LFM thesis, Increasing Throughput in a Surface Mount Assembly Line by Improving Machine Balance and Revising Metrics, 1993) A surface mount assembly operation consists of three major steps: solder paste application, component placement, and solder re-flow. For most products, the bottleneck of the process is the component placement step. There are three insertion machines in sequence. Each of these machines has different capabilities in terms of what types of components it can handle and at what speed it can operate. The first machine is a high-speed chip shooter. The second machine is a pickand-place machine that operates about ten times slower than the chip shooter; but the pick-and-place is needed to handle some large components that can’t be inserted by the chip shooter. The third machine is also a pick-and-place machine but with slightly different characteristics than the other pick-and-place machine. Products are manufactured in batches, where each board in a batch visits each of the three machines in sequence. One issue in operating the line is how to assign components to each of these machines so as to increase the throughput of the line. For instance suppose we consider a product that has 509 components to insert of the following types: Component Type A B C D F G I J K L Number of Components 358 2 3 71 35 11 12 12 4 1 The operating speeds (in seconds) for inserting a component vary by component type and by machine: Component Type A B C D F G I J K L Machine 1 0.3 0.3 0.36 0.48 0.57 0.57 0.96 Machine 2 2.6 2.8 2.8 2.8 2.8 3.0 3.0 2.8 3.6 Machine 3 2.8 3.0 3.0 3.0 3.0 3.3 3.6 3.0 4.5 4.5 Blanks in the table signify that the machine cannot handle that type of component. OPTIMIZATION OF IN-LINE INSPECTION IN WAFER FABRICATION (From John W. Bean’s LFM thesis, Variation Reduction in a Wafer Fabrication Line Through Inspection Optimization, 1997) One important source of lost output in semiconductor manufacturing is special-cause defects or excursions. Excursions are typically caused by a preventable condition that can be corrected through better system design and maintenance. System improvements are cost effective until a reasonable risk level is achieved. A company must live with some level of excursion risk below which it is uneconomical or impossible to achieve improvement. At this point, the impact of excursions can only be limited by improved detection. The impact of an excursion depends on its severity and how much product is affected before it is identified by in-line inspection and corrected. Excursions can be traced to certain higher risk process steps. These high-risk steps include metal deposition, photolithography, etchant steps and film deposition steps. Each excursion has a different impact on the lots, wafers and dice it affects. Some excursions are intermittent while others are consistent. One excursion may impact all wafers but only a few dice per wafer. Another may only impact one out of three wafers but every die on these wafers. The locations of in-line inspection determine the impact of an excursion. Proper excursion control will consider both the informational and production loops shown in the figure. The solid line represents the flow of product and the dotted line represents the flow of information. Defect is detected. Excursion Source Inspection Location Source is identified and corrective action taken. Flow of excursionary material and information. There may be an opportunity to improve the control of excursions through the improved allocation of inspection resources for several reasons. First, in-line inspection plans are developed during the initial process development and may or may not be adjusted as the process is modified. Hence, current inspection plans may be artifacts of past processing conditions. Second, there is a tendency to view inspection plan modifications in isolation. Inspections may be added, moved or removed based on data collected at a single area in the process. This data may indicate the need to modify a specific inspection step, but a holistic view of the process could uncover additional opportunities for improvement. The analysis tools that were developed include the formulation for an optimization routine and a scenario analysis tool. Both tools are built from the same general formulation that mathematically represents the nature of excursion occurrences and the typical procedures followed by the defect reduction group. The model formulation begins by breaking the several hundred process steps down into modules based on the most probable inspection locations. Typically, the top 30-50 possible inspection locations are used to divide the process into modules. Process steps are sectioned into modules according to the following guidelines. • Queue limitations -- Queue limits between steps prevent any additional material handling or inspection. The most common example is the queue restriction following each cleaning operation. Product must be processed immediately following a cleaning operation to prevent re-contamination of the wafer surface. • Process limitations -- Processing conditions make certain locations unfavorable for inspection. Photo-resist residue, deposited films or etching operations may reduce the sensitivity of an inspection below acceptable levels. • Risk assessment -- Certain steps can be grouped together because of low probability of excursion occurrence, Pr[excursion].