8 Corrected exercises on assignment problems

The page presents several corrected exercises on automated planning and scheduling problems, in particular on assignment problems.

problèmes daffectation

Exercise 1

The Atlantic Coast network serves four cities. The management wants to allocate four factories to the cities. The price to send energy from a factory 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 factory can only earn one city, and a city can only draw energies from one factory. Find the best mission at the lowest cost.

After the 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

Then :

 

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

Swap the columns of a square matrix so as to minimize the sum of the elements on the main diagonal.
816159164
8342937527
7695758150
2042969024
382821581

Find an assignment solution to this matrix. Rearrange the columns so that the solution forms a diagonal.

Exercise 3

Three robots {a,b,c} must complete three tasks {t1, t2, t3} in the following grid. It takes a day for a robot to move from one cell to one of its neighbours.

assignment problem corrected exercises hungarian algorithm kuhn algorithm

In the following table, we list the days when each robot can complete each task on its own. Tasks should be completed as soon as possible.

assignment problem corrected exercises hungarian algorithm kuhn algorithm

Add the distance from Manhattan in days to the last table. Solve the assignment problem.

Exercise 4

Braneast Airlines is to staff the failed flights between New York and Chicago listed in the table below. Each of the Braneast crew lives in either New York or Chicago. Each day, a crew must fly one NY-Chicago flight and one Chicago-NY flight with at least one hour of downtime between flights.

Braneast wants to schedule crews to minimize total downtime. Develop an assignment problem that can be used to achieve this goal. Of course, some assignments are not possible. Find flight assignments that minimize total downtime. How many crews should be based in each city? Suppose that at the end of the day, each crew must be in their home town.

assignment problem corrected exercises hungarian algorithm kuhn algorithm

The assignment table is constructed as follows: for the first flight departing from Chicago, given the time of arrival in NY, how long the crew must wait at the airport. For example for the first flight from Chicago, it arrives at 10am:

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 flights 4, 5, 6, 7 from Chicago cannot be the point of departure, so we calculate the wait time from the flight from New York. Note that flight 7 from NY cannot be a departure point, so we are calculating the wait time from the flight from Chicago. From each of the elements in the table, we retain the lowest calculated value (for flights from Chicago and NY).

assignment problem corrected exercises hungarian algorithm kuhn algorithm

Solution :

assignment problem corrected exercises hungarian algorithm kuhn algorithm

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

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

Total downtime = 25h.

assignment problem corrected exercises hungarian algorithm kuhn algorithm

Exercise 5

Consider the data in the table below. If a Mumbai-based crew arrives in Delhi on a given flight, they must return to Mumbai on a subsequent flight. Assume that for any given pairing, the crew will be based in the city that results in the smallest stopover.

The problem is to find pairings in a way that minimizes ground time away from home, subject to a minimum one-hour interval between arrival and departure. Given the flight pairs, where should the crews be based?

assignment problem corrected exercises hungarian algorithm kuhn algorithm

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

assignment problem corrected exercises hungarian algorithm kuhn algorithm

We now calculate 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 the first matrix and (2.7) in the second.

assignment problem corrected exercises hungarian algorithm kuhn algorithm

The solution to this problem is the pairs (7,3) Mumbai, (8,4) Mumbai, (9,2) Delhi, (10,5) Mumbai, (11,6) Delhi, (12 , 1) from Delhi with total downtime = 18h.

Exercise 6

Solve 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

You need to solve the assignment problem:

assignment problem corrected exercises hungarian algorithm kuhn algorithm

Exercise 7

Solve the following problem as an assignment problem.

assignment problem corrected exercises hungarian algorithm kuhn algorithm

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 Department of Art History wishes to offer six courses per semester. There are seven professors in the department, each of whom can only teach certain courses, as shown in the table. Is it possible to assign all six courses to teachers so that no teacher teaches more than one course?

assignment problem corrected exercises hungarian algorithm kuhn algorithm

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 a mission, it is better to use the stepping stone method instead of the Hungarian method.

To share