System Optimization: Midterm Exam

Network Problems Prof. Stephen Graves Network (or graph) is defined by a set of nodes (vertices) and a set of arcs; each arc is given by a pair of nodes, e. g., (i, j) which denotes that there is an arc between node i and node j, permitting flow between i and j. Usually we deal with directed arcs; e. g., arc (i, j) signifies that there can be flow from node i to node j. Networks are a useful modeling construct for representing a variety of problems, especially where we are attempting to model some type of flow - material flow; transportation flows; communication flows; etc. Due to the specialized structure of some network problems, there are very efficient, specialized algorithms for solving these problems; however, all these problems can also be solved as LP's. The general form for a network problem is as follows: decision variables: xij denotes flow on arc from i to j flow balance constraints: for every node i, flow into node i must equal flow out of node i. Si ∑ x ki ∑ x ij Di k j where Si is the exogenous supply at node i and Di is the exogenous demand at node i. If Si > 0 and Di = 0, then node i is a source or supply node. If Si = 0 and Di > 0, then node i is a sink or demand node. If Si = 0 and Di = 0, then node i is a transshipment node. + = + arc capacity constraints: for every arc (i, j), there can be an upper bound Uij: x ij ≤ U ij objective function: minimize flow cost for cij being the per unit cost of flow on arc (i, j) MIN ∑ ∑ cij xij i j • Transportation problem: Network consists of supply nodes and demand nodes only. • Assignment problem: Transportation problem with one unit of supply at each supply node and one unit of demand at each demand node. Problem is to find a one-to-one assignment between "supply" nodes (say, personnel) and "demand" nodes (say, tasks). Due to structure of problem, LP solution will always be integer. • Shortest path problem: One supply node and one demand node; problem is to send one unit of flow from supply node to the demand node, where the arc costs are the "length" of the arc. • Longest path problem: same as shortest path, but now want to find longest path from supply node to demand node. This is of interest for finding critical path for a PERT or CPM project network. • Max Flow problem: One supply node and one demand node. Given the arc capacities, the problem is to determine the maximum amount of flow that the network can handle from the supply node to the demand node. • Min Cost Network Flow problem: Find the network flow that satisfies demand at demand nodes at minimum cost, given the network structure, and capacities, and supply at supply nodes. NETWORK EXAMPLE TRANSPORTATION PROBLEM Given three warehouses, each with a supply of televisions, determine least-cost allocation to four sales offices; matrix provides per unit costs for transporting one unit from warehouse to sales office. Nashua Acton Brockton Cambridge $15 $18 $13 Brighton $17 $12 $15 Somerville $14 $13 $16 Quincy $18 $19 $13 Supply 400 750 380 Demand 320 280 560 370 1530 ASSIGNMENT PROBLEM For four roommates, determine best assignment to four weekly clean-up jobs; matrix provides measure of performance for assigning individual to task. John Paul George Ringo Kitchen 2 4 6 8 Bathroom 4 6 2 4 Basement 6 1 3 2 Yard 8 3 1 5 MAXIMUM FLOW PROBLEM Determine the maximum flow from a source node (node A) to a sink node (node I), where there is a capacity limit or bound on flow on each arc. 19 7 2 20 5 2 18 3 15 3 26 4 4 13 7 3 SHORTEST PATH EXAMPLE: NUMBER OF OPTIONS IN PRODUCT LINE Currently, a manufacturing company offers its customers 20 different options for lighting panels. Power or lighting panels are the circuit boxes that take the main bus from the power company, and connect it to several branch circuits that power various parts or functions of a building. Each panel consists of a box, trim, an interior and the breakers. The interior provides the basic functionality of the lighting panel. The elements of the interior consist of three bus bars, which function as the main electrical conductor and carry the electrical supply throughout the lighting panel, and the main lug, which forms the connection between the main electric supply and the lighting panel. Circuit breakers form the connection between the individual house circuits and the electrical supply carried by the bus bars. The box holds the lighting panel and the trim provides a protective cover as well as the access to the breakers. Lighting panels differ according to the outside dimensions and layout of the box, both of which are driven by the number of circuits that can be handled. There are currently 20 different length interiors. Each size currently has its own box. As the number of different box sizes increases, so does the cost to manufacture this variety. This is exacerbated by the fact that there are four trims options for each box size. It is possible, though, to reduce the number of options offered by substituting a larger, more capable box (larger interior) than desired or needed by the customer. The advantage to the company is having fewer items to manufacture, stock and service; furthermore, customers will get more than they wanted, which has a positive utility provided that it does not come at a higher price. Reducing the number of boxes that are manufactured will reduce the manufacturing overhead that is driven by product variety ( e. g., scheduling, purchasing, manufacturing engineering). The disadvantage from limiting the number of options is that the company will be giving away part of the product, by providing more than the customer wants; in particular, there will be wasted material cost, for which the company will not be able to recover the costs. The company estimates that the overhead cost per year for each box size is $26,000. The material cost for each box is estimated to be $0.60 per inch of length, plus $5 for the ends of the boxes. Also, marketing projects that customers would actually prefer getting a bigger boxes, as long they are not 12" larger than what was requested. To model the problem, create a network: Nodes: One node for each box length Arcs: Arc (i, j) denotes using the box length assigned to node j to demand for the box length assigned to nodes i+1, i+2, … j. Arc Cost: the cost for arc (i, j) is the annual fixed cost per box ($26,000) plus the annual incremental cost for material for supplying box j to meet demand for boxes i+1, i+2, ... j. Note that if the difference between the box lengths for nodes j and i+1 is greater than 12", then the arc has an infinite cost (or is not defined). SHORTEST PATH EXAMPLE: DESIGN OF AN ASSEMBLY LINE --- EQUIPMENT SELECTION AND TASK ASSIGNMENT Suppose we want to design and lay out an assembly line for a given product. To assemble the product entails completing N tasks, where the assembly tasks are numbered according to their precedence sequence; that is, task 1 precedes task 2, task 2 precedes task 3, etc. We are given a projection of the annual demand for the product and we wish to design an assembly system that will have sufficient capacity to meet the demand and will be the minimum cost system. The assembly system is to be a serial line, consisting of work stations in sequence. Each task is to be assigned to a single work station and each work station is responsible for the completion of one or more tasks. Thus, in an assembly system, we associate a set of consecutive tasks to each work station. The cost for each possible work station (i. e., each set of consecutive tasks) is a complex derivation. If the work station is a manual station, then the costs include the direct labor costs plus costs for tooling, part feeders and fixtures. The latter costs need to be amortized over the annual product volume. And, in order to be a candidate station, it needs to have a cycle time small enough to be able to satisfy the projected annual demand for the product. If the station is automated, then there is an investment cost for the primary assembly resource (robot or piece of fixed automation), plus the amortized costs for tooling, part feeders and fixtures; there is also a variable operating cost, which covers maintenance, material handling and indirect labor. Again, the station needs to be designed so that its cycle time is capable of meeting the annual demand for the product. If both an automated and a manual station are feasible options for a proposed work station (i. e., a set of consecutive tasks), then the least cost alternative is chosen for further consideration. Once all of the possible candidate work stations have been enumerated and costed, then the system design problem is to choose a set of work stations that covers all of the tasks at the minimum cost. This can be formulated and solved as a shortest path problem. This approach extends to handle (i) multi-product assembly systems; (ii) single products with a partially-ordered precedence structure for the tasks; (iii) probabilistic task times or task options; (iv) demand requirements given as a distribution.