Assignment Problem Minimization Definition

In combinatorial optimization, a field within mathematics, the linear bottleneck assignment problem (LBAP) is similar to the linear assignment problem.[1]

In plain words the problem is stated as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the maximum cost among the individual assignments is minimized.

The term "bottleneck" is explained by a common type of application of the problem, where the cost is the duration of the task performed by an agent. In this setting the "maximum cost" is "maximum duration", which is the bottleneck for the schedule of the overall job, to be minimized.

Formal definition[edit]

The formal definition of the bottleneck assignment problem is

Given two sets, A and T, together with a weight functionC : A × TR. Find a bijectionf : AT such that the cost function:
is minimized.

Usually the weight function is viewed as a square real-valued matrixC, so that the cost function is written down as:

Mathematical programming formulation[edit]

subject to:

Asymptotics[edit]

Let denote the optimal objective function value for the problem with n agents and n tasks. If the costs are sampled from the uniform distribution on (0,1), then [2]

and

References[edit]

  1. ^Assignment Problems, by Rainer Burkard, Mauro Dell'Amico, Silvano Martello, 2009, Chapter 6.2 "Linear Bottleneck Assignment Problem" (p. 172)
  2. ^Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.




The Assignment Model



The assignment model is used to solve the traditional one to one assignment problem of assigning employees to jobs, employees to machines, machines to jobs, etc. The model is a special case of the transportation method. In order to generate an assignment problem it is necessary to provide the number of jobs and machines and indicate whether the problem is a minimization or maximization problem. The number of jobs and machines do not have to be equal but usually they are.

Objective function. The objective can be to minimize or to maximize. This is set at the creation screen but can be changed in the data screen.

Example



The table below shows data for a 7 by 7 assignment problem. Our goal is to assign each salesperson to a territory at minimum total cost. There must be exactly one salesperson per territory and exactly one territory per salesperson.

MortChorineBruceBethLaurenEddieBrian
Pennsylvania12543487548998
New Jersey33458727347665
New York12547623874462
Florida15373765269623
Canada42321877235587
Mexico40717876829044
Europe12346523442312


The data structure is nearly identical to the structure for the transportation model. The basic difference is that the assignment model does not display supplies and demands since they are all equal to one.

The Solution





The results are very straightforward.

Assignments. The 'Assigns's in the main body of the table are the assignments which are to be made. For example, Mort is to be assigned to Pennsylvania, Chorine is to be assigned to Florida, Bruce is to be sent to Canada, Beth is to work the streets of New York, Lauren is across the river in New Jersey, Eddie works Europe and Brian will work in Mexico.

Total cost. The total cost appears in the upper left cell. In this example the total cost is given by $191.

The assignments can also be given in list form as shown below.

The marginal costs can be displayed also. For example, if we want to assign Chorine to Pennsylvania then the total will increase by $6 to $197.



NOTE: To preclude an assignment from being made (in a minimization problem) you should enter a very large cost. If you enter an 'x' then the program will place a high cost in that cell.










0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *