A Multiperiod Scheduling Example

[Page 135 ( continued )]

PM Computer Services assembles its own brand of personal computers from component parts it purchases overseas and domestically. PM sells most of its computers locally to different departments at State University as well as to individuals and businesses in the immediate geographic region.

[Page 136]

PM has enough regular production capacity to produce 160 computers per week. It can produce an additional 50 computers with overtime. The cost of assembling, inspecting, and packaging a computer during regular time is $190. Overtime production of a computer costs $260. Furthermore, it costs $10 per computer per week to hold a computer in inventory for future delivery. PM wants to meet all customer orders, with no shortages, to provide quality service. PM's order schedule for the next 6 weeks is as follows :

Week	Computer Orders
1	105
2	170
3	230
4	180
5	150
6	250

PM Computers wants to determine a schedule that will indicate how much regular and overtime production it will need each week to meet its orders at the minimum cost. The company wants no inventory left over at the end of the 6-week period.

[Page 137]

Management Science Application: Gasoline Blending at Texaco

The petroleum industry first began using linear programming to solve gasoline blending problems in the 1950s. A single grade of gasoline can be a blend of from 3 to 10 different components. A typical refinery might have as many as 20 different components it blends into 4 or more grades of gasoline. Each grade of gasoline differs according to octane level, volatility, and area marketing requirements.

At Texaco, for example, the typical gasoline blends are Power and unleaded regular, Plus, and Power Premium. These different grades are blended from a variety of available stocks that are intermediate refinery products, such as distilled gasoline, reformate gasoline, and catalytically cracked gasoline. Additives include, among other things, octane enhancers . As many as 15 stocks can be blended to yield up to 8 different blends. The properties or attributes of a blend are determined by a combination of properties that exist in the gasoline stocks and those of any additives . Examples of stock properties (that originally emanated from crude oil) include to some extent vapor pressure, sulfur content, aromatic content, and octane value, among other items. A linear programming model determines the volume of each blend, subject to constraints for stock availability, demand, and the property (or attribute) specifications for each blend. A single blend may have up to 14 different characteristics. In a typical blend analysis involving 7 input stocks and 4 blends, the problem will include 40 variables and 71 constraints.

Sources: C. E. Bodington and T. E. Baker, "A History of Mathematical Programming in the Petroleum Industry," Interfaces 20, no. 4 (JulyAugust 1990): 117127; and C. W. DeWitt et al., "OMEGA: An Improved Gasoline Blending System for Texaco," Interfaces 19, no. 1 (JanuaryFebruary 1989): 85101.

Decision Variables

This model consists of three different sets of decision variables for computers produced during regular time each week, overtime production each week, and extra computers carried over as inventory each week. This results in a total of 17 decision variables. Because this problem contains a large number of decision variables, we will define them with names that will make them a little easier to keep up with:

r _j = regular production of computers per week j ( j = 1, 2, 3, 4, 5, 6)

o _j = overtime production of computers per week j ( j = 1, 2, 3, 4, 5, 6)

i _j = extra computers carried over as inventory in week j ( j = 1, 2, 3, 4, 5)

This will result in 6 decision variables for regular production ( r ₁ , r ₂ , etc.) and 6 decision variables for overtime production. There are only 5 decision variables for inventory because the problem stipulates that there is to be no inventory left over at the end of the 6-week period.

The Objective Function

The objective is to minimize total production cost, which is the sum of regular and overtime production costs and inventory costs:

minimize Z = $190( r ₁ + r ₂ + r ₃ + r ₄ + r ₅ + r ₆ ) + 260( o ₁ + o ₂ + o ₃ + o ₄ + o ₅ + o ₆ ) + 10( i ₁ + i ₂ + i ₃ + i ₄ + i ₅ )

[Page 138]

Model Constraints

This model includes three sets of constraints. The first two sets reflect the available capacity for regular and overtime production, while the third set establishes the production schedule per week.

The available regular production capacity of 160 computers for each of the 6 weeks results in six constraints, as follows:

r _j 160 computers in week j ( j = 1, 2, 3, 4, 5, 6)

The available overtime production capacity of 50 computers per week also results in six constraints:

o _j 50 computers in week j ( j = 1, 2, 3, 4, 5, 6)

The next set of six constraints shows the regular and overtime production and inventory necessary to meet the order requirement each week:

week 1: r ₁ + o ₁ i ₁ = 105

week 2: r ₂ + o ₂ + i ₁ i ₂ = 170

week 3: r ₃ + o ₃ + i ₂ i ₃ = 230

week 4: r ₄ + o ₄ + i ₃ i ₄ = 180

week 5: r ₅ + o ₅ + i ₄ i ₅ = 150

week 6: r ₆ + o ₆ + i ₅ = 250

For example, 105 computers have been ordered in week 1. Regular production, r ₁ , and overtime production, o ₁ , will meet this order, whereas any extra production that might be needed in a future week to meet an order, i ₁ , is subtracted because it does not go to meet the order. Subsequently, in week 2 the order of 110 computers is met by regular and overtime production, r ₂ + o ₂ , plus inventory carried over from week 1, i ₁ .

Model Summary

The complete model for this problem is summarized as follows:

Computer Solution with Excel

The Excel spreadsheet for this multiperiod scheduling example is shown in Exhibit 4.20, and the accompanying Solver window is shown in Exhibit 4.21. The formula for the objective function is embedded in cell C13 and is shown on the formula bar at the top of the screen. The decision variables for regular production are included in cells B6:B11 , whereas the variables for overtime production are in cells D6:D11 . The computers available each week in column G includes the regular production plus overtime production plus the inventory from the previous week. For example, cell G7 (computers available in week 2) has the formula = B7+D7+I6 . Cell I7 (the inventory left over in week 2) includes the formula = G7H7 (i.e., computers available minus computers ordered).

[Page 139]

Exhibit 4.20.

Exhibit 4.21.

The actual constraint for week 2 would be G7 = H7 . It is also necessary to enter the constraints for available regular and overtime production capacities into Solver. For example, the constraint for regular capacity would be B6:B11 160 .

Solution Analysis

The solution is

r ₁ = 160 computers produced in regular time in week 1

r ₂ = 160 computers produced in regular time in week 2

r ₃ = 160 computers produced in regular time in week 3

r ₄ = 160 computers produced in regular time in week 4

r ₅ = 160 computers produced in regular time in week 5

r ₆ = 160 computers produced in regular time in week 6

o ₃ = 25 computers produced with overtime in week 3

o ₄ = 20 computers produced with overtime in week 4

[Page 140]

o ₅ = 30 computers produced with overtime in week 5

o ₆ = 50 computers produced with overtime in week 6

i ₁ = 55 computers carried over in inventory in week 1

i ₂ = 45 computers carried over in inventory in week 2

i ₅ = 40 computers carried over in inventory in week 5

PM Computers must operate with regular production at full capacity during the entire 6-week period. It must also resort to overtime production in weeks 3, 4, 5, and 6 in order to meet heavier order volume in weeks 3 through 6.

As each week passes , PM Computers can use this model to update its production schedule should order sizes change. For example, if PM is in week 2, and the orders for week 5 change from 150 computers to 200, the model can be altered and a new schedule computed. The model can also be extended further out into the planning horizon to develop future production schedules.

PM may want to consider expanding its regular production capacity because of the heavy overtime requirements in weeks 3 through 6. The dual values (from the sensitivity analysis report from the computer output) for the constraints representing regular production in weeks 3 through 6 show that for each capacity increase for regular production time that will enable the production of one more computer, cost can be reduced by between $70 and $80. (This total reduction would occur if processing time could be reduced without acquiring additional labor, etc. If additional resources were acquired to achieve an increase in capacity, the cost would have to be subtracted from the shadow price.)