The page presents several corrected exercises about automated planning and scheduling problems, especially about assignment problems.
Exercise 1
The Atlantic Coast Grid deserves four cities. The office wants to assign four plants. The price to send energy from a plant to each city is described below:
| Raleigh | Atlanta | Durham | Clemson |
Plant A | 210 | 90 | 180 | 160 |
Plant B | 100 | 70 | 130 | 200 |
Plant C | 175 | 105 | 140 | 170 |
Plant D | 80 | 65 | 105 | 120 |
A plant can deserve only one city, and a city can take energies only from one plant. Find the best assignment at lowest cost.
After first reduction:
| R | A | D | C |
A | 105 | 0 | 55 | 15 |
B | 15 | 0 | 25 | 75 |
C | 35 | 0 | 0 | 10 |
D | 0 | 0 | 5 | 0 |
After second reduction:
| R | A | D | C |
A | 90 | 0 | 40 | 0 |
B | 0 | 0 | 10 | 60 |
C | 55 | 15 | 0 | 10 |
D | 0 | 15 | 5 | 0 |
Solution: 90+100+140+120=450.
Exercise 2
Permute the columns of a square matrix so as to minimize the sum of elements on the main diagonal.
8 | 16 | 15 | 91 | 64 |
83 | 42 | 93 | 75 | 27 |
76 | 95 | 75 | 81 | 50 |
20 | 42 | 96 | 90 | 24 |
38 | 28 | 2 | 15 | 81 |
Find an assignment solution to this matrix. Reorganize the columns such as the solution forms a diagonal.
Exercise 3
Three robots {a,b,c} need to finish three tasks {t1, t2, t3} in the following grid. It take one day for a robot to move from one cell to one of its neighbors.
In the following table, we list the days that each robot can finish each task alone. The tasks need to be finished as soon as possible.
Add Manhattan distance in days to the last table. Solve the assignment problem.
Exercise 4
Braneast Airlines must staff the faily flights between New York and Chicago shown in the table below. Each of Braneast’s crews lives in either New York or Chicago. Each day a crew must fly one NY-Chicago and one Chicago-NY flight with at least one hour of downtime between flights.
Braneast wants to schedule the crews to minimize the total downtime. Set up an assignment problem that can be used to accomplish this goal. Of course, some assignments are not possible. Find the flight assignments that minimize the total downtime. How many crews should be based in each city? Assume that at the end of the day, each crew must be in tis home city.
The assignment table is constructed as follows: for the first flight from Chicago, considering the time it arrives at NY, how much time the crew has to wait at the airport. For example for the first flight from Chicago, it arrives at 10 A.M:
Flight | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Leave New York | 7 | 8 | 10 | 12 | 14 | 16 | 18 |
Waiting time | impossible | impossible | impossible | 2 | 4 | 6 | 8 |
We note that flight 4, 5, 6, 7 from Chicago can’t be starting point, so we compute waiting time from NY flight. Note that flight 7 from NY can’t be a starting point, so we compute waiting time from Chicago flight. From each elements of the table, we keep the lowest value computed (for flight from Chicago and NY).
Solution:
Starts in NY: (1,3), (2,4), (3,5), (5,6), (6,7).
Starts in Chicago: (4,1), (7,2).
Total downtime = 25h.
Exercise 5
Consider the data of table below. If a crew based in Mumbai arrives at Delhi on a given flight, it must return to Mumbai on a later flight. Assume that for any given pairing, the crew cill be based in the city that results in the smaller layover.
The problem is to find the pairings so as to minimize the time on ground away from home, subject to a minimum interval of one hour between arrival and departure. Given the pairs of flights, where should the crews be based?
As the previous exercise, firstly compute the layover time matrices, one for layover in Mumbai and the other for Delhi.
We now compute the minimum of the values for the 36 pairs and construct the table below. For example (7,2) is the minimum between (7,2) in first matrix and (2,7) of the second one.
The solution of this problem is pairs (7,3) from Mumbai, (8,4) from Mumbai, (9,2) from Delhi, (10,5) from Mumbai, (11,6) from Delhi, (12,1) from Delhi with a total layoff time = 18h.
Exercise 6
Resolve the following problem as an assignment problem.
Minimize 4X11+6X12+5X13+5X14+7X21+4X22+5X23+6X24 +4X31+7X32+6X33+4X34 +5X41+3X42+4X43+7X44
St. X11+X12+X13+X14=1
X21+X22+X24+X24=1
X31+X32+X33+X34=1
X41+X42+X43+X44=1
X11+X21+X31+X41=1
X12+X22+X32+X42=1
X13+X23+X33+X43=1
X14+X24+X34+X44=1
Here is the table to resolve:
Exercise 7
Resolve the following problem as an assignment problem.
The assignment problem is described in the table below:
| 1 | 2 | 3 |
1 | 5 | 9 | inf |
2 | inf | 2 | inf |
3 | inf | 1 | 1 |
Exercise 8
The Art History Department wishes to offer six courses in a semester. There are seven professors in the department, each of which can teach only certain courses, as shown in the table. Is it possible to assign the six courses to the professors so that no professor teaches more than one course?
The assignment problem is described in the table below:
| Ant | Bat | Cat | Dodo | Frog | Gnat | Hog |
Antique | 1 | 1 | 1 | 1 | inf | inf | inf |
Renaissance | 1 | inf | inf | inf | 1 | 1 | inf |
Baroque | 1 | inf | inf | inf | 1 | inf | inf |
Impressionism | inf | inf | inf | inf | 1 | 1 | inf |
Modern | inf | inf | 1 | inf | inf | 1 | 1 |
Contemporary | 1 | inf | inf | inf | inf | 1 | inf |
dummy | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
In order to find an assignment, it’s better to use stepping stone method instead of Hungarian method.
