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

TO

D

VS

TO

105

0

55

15

B

15

0

25

75

VS

35

0

0

10

D

0

0

5

0

After second reduction:

 

R

TO

D

VS

TO

90

0

40

0

B

0

0

10

60

VS

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.

corrected exercises automated planning and scheduling problems assignment problems

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.

corrected exercises automated planning and scheduling problems assignment problems

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.

corrected exercises automated planning and scheduling problems assignment problems

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 AM:

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).

corrected exercises automated planning and scheduling problems assignment problems

Solution:

corrected exercises automated planning and scheduling problems assignment problems

Starts in NY: (1.3), (2.4), (3.5), (5.6), (6.7).

Starts in Chicago: (4.1), (7.2).

Total downtime = 25h.

corrected exercises automated planning and scheduling problems assignment problems

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?

corrected exercises automated planning and scheduling problems assignment problems

As the previous exercise, firstly compute the layover time matrices, one for layover in Mumbai and the other for Delhi.

corrected exercises automated planning and scheduling problems assignment problems

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.

corrected exercises automated planning and scheduling problems assignment problems

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:

corrected exercises automated planning and scheduling problems assignment problems

Exercise 7

Resolve the following problem as an assignment problem.

corrected exercises automated planning and scheduling problems assignment problems

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?

corrected exercises automated planning and scheduling problems assignment problems

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.