Contenus

Toggle## Exercices corrigés sur les problèmes d'affectation

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.

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

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

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.

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

Solution :

Starts in New York: (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 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?

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

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.

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_{11}+ 6X_{12}+ 5X_{13}+ 5X_{14}+ 7X_{21}+ 4X_{22}+ 5X_{23}+ 6X_{24} + 4X_{31}+ 7X_{32}+ 6X_{33}+ 4X_{34} + 5X_{41}+ 3X_{42}+ 4X_{43}+ 7X_{44}

St. X_{11}+ X_{12}+ X_{13}+ X_{14}=1

X_{21}+ X_{22}+ X_{24}+ X_{24}=1

X_{31}+ X_{32}+ X_{33}+ X_{34}=1

X_{41}+ X_{42}+ X_{43}+ X_{44}=1

X_{11}+ X_{21}+ X_{31}+ X_{41}=1

X_{12}+ X_{22}+ X_{32}+ X_{42}=1

X_{13}+ X_{23}+ X_{33}+ X_{43}=1

X_{14}+ X_{24}+ X_{34}+ X_{44}=1

You need to solve the assignment problem:

## Exercise 7

Solve 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 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?

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.