William Beebe owns a small shoe store. He has 10 pairs of shoes that require resoling and polishing. He has a machine that can resole one pair of shoes at a time, and the time required for the operation varies with the type and condition of the shoe and the type of sole that is used. Shoes are polished on a machine dedi-cated to this purpose as well, and polishing is always done after resoling. His assistant generally does the polishing while Mr. Beebe does the resoling. The resoling and polishing times (in minutes)

are Shoes R esoling Time Polishing Time 1 14 3 2 28 1 3 12 2 4 6 5 5 10 10 6 14 6 7 4 12 8 25 8 9 15 5 10 10 5 In what order should the shoes be repaired in order to minimize the total makespan for these 10 jobs?