Baker K.R. Optimization Modeling with Spreadsheets
Подождите немного. Документ загружается.
various collection areas. In addition, the amortized monthly cost for the facility at each
proposed site has also been estimated. The data are shown in the table below.
From
collection
Transportation cost per ton
to
landfill site
Monthly
area L1 L2 L3 L4 tons
A $14 $16 $10 $8 500
B 12111214 700
C 13 8 9 11 1500
D 10 15 14 12 1000
E 8 12 10 11 1800
F 11 10 8 6 1200
Operating
cost/ton
$8 $10 $9 $11
Fixed cost/
month
$1000 $800 $700 $900
What is the optimal configuration and the minimum system monthly cost?
7.7. Distribution Planning Southeastern Foods has hired you to analyze their distribution
system design. The company has eleven distribution centers, with monthly volumes as
listed below. Seven of these sites can support warehouses, in terms of the infrastructure
available, and are designated by (W).
Center Volume Center Volume
Atlanta (W) 5000 Memphis (W) 7800
Birmingham (W) 3000 Miami 4400
Columbia (W) 1400 Nashville (W) 6800
Jackson 2200 New Orleans 5800
Jacksonville 8800 Orlando (W) 2200
Louisville (W) 3000
Information has been compiled showing the cost per carton of shipping from any
potential warehouse location to any distribution center. Southeastern has standardized
its warehouse design so that all such facilities can handle up to 15,000 cartons in a
month. In addition, the monthly fixed cost for operating one of these warehouses is esti-
mated at $3600. Southeastern could build warehouses at any of the designated locations,
but its criterion is to minimize the total of fixed operating costs and variable shipment
costs.
286 Chapter 7 Integer Programming: Logical Constraints
Atl Bir Col Jac Jvl Lvl Mem Mia Nash NewO Orl
Atlanta 0.00 0.15 0.21 0.40 0.31 0.42 0.38 0.66 0.25 0.48 0.43
Birmingham 0.15 0.00 0.36 0.25 0.46 0.36 0.26 0.75 0.19 0.35 0.55
Columbia 0.21 0.36 0.00 0.60 0.30 0.50 0.62 0.64 0.44 0.69 0.44
Louisville 0.42 0.36 0.50 0.59 0.73 0.00 0.38 1.09 0.17 0.70 0.86
Memphis 0.38 0.26 0.62 0.21 0.69 0.38 0.00 1.00 0.21 0.41 0.78
Nashville 0.25 0.19 0.44 0.41 0.56 0.17 0.21 0.91 0.00 0.53 0.69
Orlando 0.43 0.55 0.44 0.70 0.14 0.86 0.78 0.23 0.69 0.65 0.00
(a) What is the total distribution cost (fixed warehouse costs plus variable distribution
cost) for the optimal configuration? What is the optimal configuration of locations
to use for the system?
(b) To streamline communications, management requires that each distribution center
must be served by just one warehouse. When this requirement is imposed, how
much does total cost increase, as compared to the cost in (a)?
7.8. Scheduling with Sequence-dependent Setups A painting operation is scheduled in
blocks, where each block involves painting products with a particular color. Cleaning
time is required in between each pair of blocks so that the equipment can be prepared
for the new color. In each cycle there is one block of each color, and the total painting
time is determined by the volume of orders. However, the actual schedule length is deter-
mined by the sequence in which the blocks are scheduled, since the cleaning time depends
on the color in the previous block and the color in the next block. The table below gives the
number of minutes required to clean the equipment, according to the color pair.
Cleaning To color
times 1 2 3 4 5 6
1 –48 6 82
From 2 5– 711134
color 3 11 6 – 8 4 3
4 572 – 25
5 10 9 7 5 – 2
6 843 6 5–
(a) Find the block sequence that minimizes the amount of time spent in cleaning during a
full cycle.
(b) What is the minimum number of minutes devoted to cleaning?
7.9. Planning a European Tour Recent graduate and amateur world traveler Alastair Bor
is planning a European trip. His preferences are influenced by his curiosity about urban cul-
ture in Europe and by his extensive study of international relations while he was in school.
Accordingly, he has decided to make one stop in each of 12 European capitals in the time he
has available. He wants to find a sequence of the cities that involves the least total mileage.
He has calculated inter-city distances using published data on latitude and longitude,
and applying the geometry for arcs of great circles. These distances are shown below.
Exercises 287
To
Ams Ath Ber Brus Cope Dub Lis Lon Lux Mad Par Rom
Amsterdam – 2166 577 175 622 712 1889 339 319 1462 430 1297
Athens 2166 – 1806 2092 2132 2817 2899 2377 1905 2313 2100 1053
Berlin 577 1806 – 653 348 1273 2345 912 598 1836 878 1184
Brussels 175 2092 653 – 768 732 1738 300 190 1293 262 1173
Copenhagen 622 2132 348 768 – 1203 2505 942 797 2046 1027 1527
From Dublin 712 2817 1273 732 1203 – 1656 440 914 1452 743 1849
Lisbon 1889 2899 2345 1738 2505 1656 – 1616 1747 600 1482 1907
London 339 2377 912 300 942 440 1616 – 475 1259 331 1419
Luxembourg 319 1905 598 190 797 914 1747 475 – 1254 293 987
Madrid 1462 2313 1836 1293 2046 1452 600 1259 1254 – 1033 1308
Paris 430 2100 878 262 1027 743 1482 331 293 1033 – 1108
Rome 1297 1053 1184 1173 1527 1849 1907 1419 987 1308 1108 –
(a) Find a minimum distance tour for Alastair, starting and ending in Brussels.
(b) What is the length of the optimal tour?
7.10. Miles Manufacturing (Revisited) Revisit the scenario of Example 7.4. Suppose we
decide that it is important to distinguish among the levels of importance represented by
the various jobs. In particular, we associate a weighting factor with each job. Now, we
can take our objective to be the total weighted tardiness in the schedule, where a job’s
weighted tardiness is the product of its tardiness and its weight. The weights of the
jobs are listed in the full table of data given below.
Job number 1 2 3456
Processing time (hours) 5 7 9 11 13 15
Weight 886642
Due date (hours from now) 28 35 24 32 30 40
(a) What is the total weighted tardiness for the optimal sequence (5-3-1-2-4-6) found in
Example 7.4?
(b) What is the optimal value of total weighted tardiness?
7.11. Locating Emergency Service Bases The Southeast Emergency Management Agency
is planning to establish a number of helicopter bases in a hurricane-prone part of the
country. There are 25 sites under consideration, but the agency has funds to install
only three bases. Using a specialized map, the agency has identified counties that can
be served from each site in less than 15 minutes of response time. (This response time
is considered the maximum desired for the purposes of servicing life-and-death emergen-
cies that might follow a hurricane.)
The data describing the potential sites consist of a census list and an accessibility
matrix. The census list gives the population of each county. The accessibility matrix con-
tains a 1 as its (k, j)th element if county k can be serviced from a base at site j within 15
minutes.
At present, the agency has funds to install just three of the bases, and it wishes to
maximize the population served by the bases. At which sites should the bases be estab-
lished and what is the corresponding population served?
288 Chapter 7 Integer Programming: Logical Constraints
County Population 12345678910111213141516171819202122232425
Abbeville 93,109 011000110 1000000001000110
Aiken 105,481 001000000 0100000000000001
Allendale 69,358 110000010 0010001000000001
Anderson 3583 100000001 1010100000010000
Bamberg 135,155 000000001 0100100000001010
Barnwell 134,336 000000000 0000000001100000
Beaufort 55,393 000000000 0001000001101000
Berkeley 91,701 001000000 0100000000000000
Calhoun 26,290 000110000 0010000000100000
Cherokee 58,751 100100000 0001011000101000
Chester 80,815 110000000 0000101001100000
Chesterfield 138,362 001100001 0001100010000000
Claredon 3503 000000100 1010000000000000
Colleton 28,612 000110000 0110001010000001
Darlington 15,303 000000000 1000000000010101
Dillon 125,505 001000000 1100100000000010
Dorchester 163,144 100000000 0000000011000000
Edgefield 10,692 000000000 0010100101000000
Fairfield 100,910 000001100 0100000110000100
Florence 71,737 100001101 1100000000001110
Georgetown 96,531 000100000 0100010000000000
Greenville 123,314 000010100 1000000000100100
Greenwood 68,294 100000000 0100010001101000
Hampton 47,899 100010000 0000001000110001
Horry 11,904 011110000 0000110000000010
Jasper 162,741 110101000 0001000001000001
Kershaw 158,158 110010100 0000010101000000
Lancaster 39,963 100100000 0011000000110000
Laurens 50,358 000000010 0010001100000000
Lee 159,543 000010101 0000000010000000
(Continued)
289
Table 7.5 Continued
County Population 12345678910111213141516171819202122232425
Lexington 77,538 000010000 0001000001001001
Marion 130,967 010010000 0000010000001000
Marlboro 115,343 010010000 0100110110000000
McCormick 107,742 110001100 0010100000001000
Newberry 131,642 000000010 0000011000000010
Oconee 145,303 010110001 0001000000110100
Orangeburg 15,198 001010100 0001000000001000
Pickens 117,555 100010100 0000100001000110
Richland 114,203 000000100 0000010000000000
Saluda 56,227 000000100 0000001001001000
Spartanburg 112,869 101001000 0101100001100000
Sumter 43,744 100000001 0011000000000000
Union 100,277 010000100 0001011000100100
Williamsburg 69,503 000000000 0100000000000100
York 48,458 010010000 0000000100000100
290
Case: Hornby Products Company
∗
The Hornby Products Company, headquartered in Denver, Colorado, markets a broad line of
handcrafted home furnishings that are produced either in its own plants or by local artisans
working under contract with the company. Hornby Products has established markets throughout
most of the area west of the Mississippi. Its products are distributed to these markets mainly
through a series of specialized manufacturer’s representatives. In a few areas, the company uti-
lizes architectural firms and interior decorators as distributors.
The company has been so successful in western markets that management has decided
to expand its market area to the east. The most recent expansion has been into a region east
of the Mississippi from Illinois to western New York and as far south as Alabama and South
Carolina. The company is currently serving this new region from its warehouse in Denver
and a regional warehouse in St Paul. Sales in the eastern region have grown to such a level
that management has decided to establish a system of distribution warehouses to serve this
market. The company is now asking, how many additional warehouses are needed, and
where should they be located?
History
The Hornby product line contains the full gamut of home furnishings, from heavy pieces of
handcrafted furniture to delicate pottery and statues. The company’s management has always
insisted that the workmanship in its products meet the highest standard. Because of this insis-
tence, the company has attained an industry-wide reputation for outstanding quality. In addition
to product quality, management has also concentrated on the quality of its customer service. As
its reputation for quality and service has spread, the company has begun to experience very rapid
growth. With a vigorous management team, it appears possible to sustain this rapid growth rate
without much difficulty.
The company has several policies that have permitted this growth without major capital
additions. Subcontracting of production has reduced the necessary investment in plant and
equipment. Leasing rather than buying warehouses has practically eliminated investment in
this area. The company has, however, deviated from its minimum investment policy in order
to maintain a high level of customer service. A full line of products is stocked at every distri-
bution warehouse and every effort is made to provide delivery within 24 hours. The company
considers this policy critical to expanding the market for its products.
Hornby Products has contracted with 22 different manufacturer’s representatives and
architectural firms in the expansion east of the Mississippi. As the company’s product line
has become established in that area, the representatives have been placing larger orders,
necessitating more and more shipments from Denver rather than from St Paul. Denver shipments
have been required in order not to drastically deplete the stock at St Paul. This has made it dif-
ficult to adhere to the 24-hour delivery policy. The situation has worsened to the point where
management has concluded that the sales growth will be stifled unless distribution warehouses
∗
Adapted from Berry, W.L. and D. Clay Whybark, Computer Augmented Cases in Operations and
Logistics Management (1972) South-Western Publishing. An edited version was graciously provided by
Alan Neebe.
Case: Hornby Products Company 291
are set up to serve the eastern region. The final impetus to establish these warehouses was pro-
vided by the representative in Indianapolis, who complained that late delivery of samples had
caused the loss of a sizable contract for the furnishings of a major hotel chain. Hornby
management recognized that this would be an increasing problem if better delivery service
couldn’t be arranged. They went to work on establishing a new distribution system for the east-
ern region.
EXHIBIT 7.1 Potential Warehouse Locations for the New Region
292 Chapter 7 Integer Programming: Logical Constraints
Alternatives
As a first step in establishing the system, company officers visited each of the cities in which they
had manufacturing representatives. These 22 cities are shown on the map in Exhibit 7.1. (After
initially drawing the map, the company officers decided that Denver should continue to serve
Little Rock and Willow Springs.) Eight of these cities were judged to have sufficient transpor-
tation services and warehouse facilities for distribution warehouses. Preliminary work was done
on estimating the costs and determining the availability of specific facilities. Since company
policy was to lease distribution warehouses, little difficulty was encountered in finding at
least some warehouse space in each of the eight possible cities.
The typical warehouse facility offers a leasing arrangement that follows the cost structure
diagrammed in Exhibit 7.2. The cost structure consists of a fixed cost (F) and a variable cost (V ).
In addition, there is a lower limit (L) and an upper limit (U) associated with annual volume. The
EXHIBIT 7.2 Cost Structure at a Typical Warehouse
EXHIBIT 7.3 Warehouse Cost Data
W/H Location
Fixed
cost
Variable
cost
Min.
(L)
Max.
(U)
1 Atlanta 2700 6 200 1750
2 Buffalo 2900 8 150 1250
3 Chicago 3500 9 250 2000
4 Cincinnati 2200 7 200 1500
5 Detroit 3300 8 200 1750
6 Pittsburgh 3000 8 200 1500
7 Richmond 2000 6 150 1000
8 St. Louis 1800 5 200 1500
Case: Hornby Products Company
293
upper limit is a volume ceiling dictated by material handling equipment: no more than this
amount of product can be moved through the warehouse. The lower limit functions as a guar-
antee of sorts to the leasing company. In each city, lease arrangements require a certain mini-
mum capacity to be leased if a warehouse is established. Specifically, Hornby can choose to
operate at a volume lower than L, but the fixed cost F would be charged in any event. Only
volumes in excess of L incur additional costs, and here the charge is equal to the variable
cost V multiplied by the excess volume. Exhibit 7.3 presents the detailed cost and capacity
estimates.
For the purposes of evaluating expansion alternatives, sales levels have been forecast
two years into the future. Detailed sales forecasts for each representative have been converted
to hundredweights (cwt) sold annually at each location. (The term hundredweight refers
to 100 pounds of product.) At Hornby Products Company, the use of hundredweights as
a unit of measure turns out to be a relatively accurate means of aggregating demand, and it
is convenient in working out transportation costs. The sales forecasts are given in Exhibit 7.4.
EXHIBIT 7.4 Forecast for Annual Demands
Rep. no. Location Volume
1 Atlanta 275
2 Birmingham 160
3 Buffalo 240
4 Charleston 260
5 Charlotte 135
6 Chattanooga 160
7 Chicago 400
8 Cincinnati 200
9 Cleveland 320
10 Columbus 220
11 Detroit 190
12 Evansville 100
13 Ft Wayne 140
14 Indianapolis 310
15 Knoxville 125
16 Louisville 340
17 Memphis 240
18 Nashville 210
19 Peoria 150
20 Pittsburgh 340
21 Richmond 300
22 St Louis 260
294 Chapter 7 Integer Programming: Logical Constraints
EXHIBIT 7.5 Unit Costs for Distribution
Atlanta Buffalo Chicago Cincinnati Detroit Pittsburgh Richmond St Louis
Atlanta 1 13 16 11 15 11 8 12
Birmingham 4 15 15 12 16 13 11 10
Buffalo 13 1 10 8 4 4 7 13
Charleston 7 6 11 6 8 6 4 10
Charlotte 4 10 15 10 13 8 4 14
Chattanooga 2 11 14 9 13 9 7 11
Chicago 16 10 1 9 6 9 14 7
Cincinnati 9 6 7 3 6 6 7 7
Cleveland 13 3 7 6 3 5 8 10
Columbus 10 4 8 4 5 4 7 9
Detroit 15 4 6 8 1 7 11 11
Evansville 9 10 7 6 9 8 10 4
Ft. Wayne 14 8 2 7 4 9 12 6
Indianapolis 12 9 4 6 7 8 11 4
Knoxville 4 9 12 7 11 9 6 9
Louisville 8 8 8 4 8 8 8 6
Memphis 8 14 12 10 14 12 12 6
Nashville 6 12 11 8 12 10 9 7
Peoria 16 11 2 10 8 11 15 5
Pittsburgh 11 2 9 6 5 3 5 11
Richmond 8 7 14 9 11 7 1 14
St Louis 12 13 7 9 11 11 14 1
295