Winston Chapter 9.6, Page 531, Number 2 (Traveling Salesman & Assignment)
/ / 1Winston Chapter 9.6, Page 531, Number 2 (Traveling Salesman & Assignment)
Problem Statement: Each day, Sunco manufactures four types of gasoline: lead-free premium, lead-free regular, leaded premium, and leaded regular. Because of cleaning and resetting of machinery, the time required to produce a batch of gasoline depends on the type of gasoline last produced. For example, it takes longer to switch between a lead-free gasoline and a leaded gasoline than it does to switch between two lead-free gasolines. The times (in minutes) required to manufacture each day’s gasoline requirements are shown in Table 71. Use a branch-and bound approach to determine the order in which the gasolines should be produced each day.
Table 71:
Last-Produced Gasoline /Gas to Be Next Produced
LFR / LFP / LR / LPLFR / -- / 50 / 120 / 140
LFP / 60 / -- / 140 / 110
LR / 90 / 130 / -- / 60
LP / 130 / 120 / 80 / --
Note: Assume that the last gas produced yesterday precedes the first gas produced yesterday.
- Solve using the Traveling Salesman option of Quant. Print input and output of Quant.
- Solve using the Assignment option of Quant and creating the Branch-and-Bound tree. Print input and output of Quant.
- Comment on these solutions.
- Quant Input and Output Using Travel-Salesman Option of Quant:
|------|
| Summarized Traveling for 053102A Page: 1 |
|------|
| City | To City | Distance | City | To City | Distance |
|------+------+------+------+------+------|
| LFR | LFP | +50.00 | LR | LFR | +90.00 |
| LFP | LP | +110.0 | LP | LR | +80.00 |
|------|
| Minimum OBJ = 330 Iteration = 3 CPU second = .0625 |
|------|
Optimal Traveling Route:
LFR -- LFP -- LP -- LR -- LFR
The optimal traveling route, or tour, shown above represents the order in which the gasolines should be produced each day. The optimal order in which to produce the gasolines is as follows:
- Produce lead-free regular.
- Produce lead-free premium.
- Produce leaded premium.
- Produce leaded regular.
Production for the day may be started with any gasoline as long as the sequence of the route is followed in either forward or reverse direction. The Travel-Salesman option used above insures that each gasoline is produced exactly once per period (per day).
- Quant Input and Output Using the Assignment Option of Quant & Creating the Branch-and-Bound tree:
|------|
| Summary of Assignments for 053102B Page: 1 |
|------|
| Object | Task |Cost/Prof.| Object | Task |Cost/Prof.|
|------+------+------+------+------+------|
| LFR | LFP | +50.00 | LR | LP | +60.00 |
| LFP | LFR | +60.00 | LP | LR | +80.00 |
|------|
| Minimum OBJ = 250 Iteration = 1 CPU second = 0 |
|------|
The assignment option of Quant does not report an optimal tour. This option allows for multiple tours (sub-tours) while finding the absolute minimum objective value in minutes. Here, the result summary above is analyzed and two separate sub-tours are noticed. One sub-tour indicates that lead-free regular and lead-free premium should be alternately manufactured, while the other sub-tour indicates that leaded regular and leaded premium should be alternately manufactured. Although the time to complete these sub-tours is reduced to 250 minutes (from 330 minutes), these two sub-tours do not allow for one optimum schedule in which all gasolines are manufactured.
From here on, the branch-and-bound method will be used to find an optimum order of manufacturing so that all gasolines will be manufactured exactly once per period within a minimum amount of time. As well, a number instead of its acronym will represent each gasoline.
LFR, lead-free regular = 1.
LFP, lead-free premium = 2.
LR, leaded regular = 3.
LP, leaded premium = 4.
Quant Input & Output for x12 = 0:
|------|
| Summary of Assignments for 053102C Page: 1 |
|------|
| Object | Task |Cost/Prof.| Object | Task |Cost/Prof.|
|------+------+------+------+------+------|
| LFR | LR | +120.0 | LR | LP | +60.00 |
| LFP | LFR | +60.00 | LP | LFP | +120.0 |
|------|
| Minimum OBJ = 360 Iteration = 1 CPU second = 0 |
|------|
Quant Input & Output for x21 = 0:
|------|
| Summary of Assignments for 053102D Page: 1 |
|------|
| Object | Task |Cost/Prof.| Object | Task |Cost/Prof.|
|------+------+------+------+------+------|
| LFR | LFP | +50.00 | LR | LFR | +90.00 |
| LFP | LP | +110.0 | LP | LR | +80.00 |
|------|
| Minimum OBJ = 330 Iteration = 1 CPU second = 0 |
|------|
Summary of Branch and Bound Method:
The solution from sub-problem 1 (the initial assignment solution) shows two sub-tours. These sub-tours can be manipulated so that only one tour exists at the expense of some additional time by prohibiting certain routes of travel. The boxes with heavy borders above contain candidate solutions. The optimum solution of candidate solutions is located within sub-problem 3. Sub-problem 3 contains one complete tour and has the minimum possible objective function.
In other words, the first solution in sub-problem one indicates that lead-free regular and lead-free premium should be alternately manufactured, while also manufacturing regular and leaded premium gasolines. The minimum time to manufacture a day’s gasoline requirements is 250 minutes. This solution isn’t practical because it doesn’t take into consideration the need for cleaning and resetting the machines.
Cleaning and resetting the machines can only occur properly if all gasolines are manufactured one after another. The branch-and-bound method with Quant’s assignment program eventually gives the same solution as Quant’s traveling salesman program. The order and times in which the gasolines should be produced (either forward or reverse order, starting with any gasoline and ending with the same gasoline) is shown below:
- Produce lead-free regular for 50 minutes.
- Produce lead-free premium for 110 minutes.
- Produce leaded premium for 90 minutes.
- Produce leaded regular for 80 minutes.
The total time necessary to manufacture a day’s gasoline is 330 minutes.