8 Corrected exercises on assignment problems

Contents

Corrected exercises on assignment problems

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

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.

Solution

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.

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

Solution

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.

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.

Solution

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.

Solution

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?

Solution

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 4X₁₁+ 6X₁₂+ 5X₁₃+ 5X₁₄+ 7X₂₁+ 4X₂₂+ 5X₂₃+ 6X₂₄ + 4X₃₁+ 7X₃₂+ 6X₃₃+ 4X₃₄ + 5X₄₁+ 3X₄₂+ 4X₄₃+ 7X₄₄

St. X₁₁+ X₁₂+ X₁₃+ X₁₄=1

X₂₁+ X₂₂+ X₂₄+ X₂₄=1

X₃₁+ X₃₂+ X₃₃+ X₃₄=1

X₄₁+ X₄₂+ X₄₃+ X₄₄=1

X₁₁+ X₂₁+ X₃₁+ X₄₁=1

X₁₂+ X₂₂+ X₃₂+ X₄₂=1

X₁₃+ X₂₃+ X₃₃+ X₄₃=1

X₁₄+ X₂₄+ X₃₄+ X₄₄=1

Solution

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.

Solution

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?

Solution

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.