Transcript Assignment

TM 631 Optimization
Assignment Problems
Prototype Problem
• K-Corp has 3 parts, each of which can be
assigned to 1 of 3 machines. The problem
is to assign 1 part to one machine only so
as to minimize the total production costs.
Relevant data are:
Cost to Produce Part i on Machine j
Machine
1
2
3
1
9
10
10
Part
2
12
8
11
3
11
13
9
LP Formulation
X
ij
=
1 , machine
0 , else
i assigned
to task
j
Min Z = total production costt
s. t .
Each machine to be used once
Each part to be assigned to a machine
LP Formulation
X ij =
1 , machine i assigned to task j
0 , else
Min Z = 9 X 11 + 12 X 12 + 11 X 13 + ... + 9 X 33
s. t .
X 11 + X 12 + X 13 = 1
X 21 + X 22 + X 23 = 1
X 31 + X 32 + X 33 = 1
X 11 + X 21 + X 31 = 1
X 21 + X 22 + X 23 = 1
X 31 + X 32 + X 33 = 1
machine 1 assigned
machine 2 assigned
machine 3 assigned
part 1 assigned
part 2 assigned
part 3 assigned
LP Formulation
n
n
Min Z =   cij X ij
i =1 j =1
s. t .
n
X
i =1
ij
, j = 1, 2,..., n
ij
, i = 1, 2,..., n
n
X
j =1
X ij  0 all i , j
Transportation Formulation
Parts/Tasks
Machines
Part 1
9
Part 2
12
Part 3
11
Machine 1
1
10
8
13
Machine 2
1
10
Machine 3
Demand
Vj
Supply
11
9
1
1
1
1
Assignment special case of Transportation
suppliers = destinations = n
si = d j = 1
Ui
Excel Approach
• Excel doesn’t have special Assignment
problem tool, but we can set up the problems
like an general LP or Transportation problem.
• The books graphic for Excel use follow.
Modeled as Network
Demand
Supply
1
9
1
-1
2
-1
3
-1
12
11
1
10
1
2
1
3
8
13
10
11
9
Class Problem
• K-Corp has 4 projects underway and 3 possible
EngManagers who could possibly be assigned to
the projects. In order to determine who to assign
to each project, the enterprise manager ranks each
employee on background, experience,
interpersonal skills, and organizational skills. A final
score for each employee for each project is
determined. Maximize the assignment score.
Project
Employee
IE
ME
MBA
1
13
9
8
2
10
12
6
3
11
10
9
4
8
10
9
Class Problem
Projects
Suppliers
Project 1
13
Project 2
10
Project 3
11
Project 4
8
TM
1
9
12
10
10
ME
1
8
6
9
9
MBA
1
0
Dummy
Demand
Vj
Supply
0
0
0
1
1
1
1
1
Ui
Class Problem
Projects
Suppliers
Project 1
13
Project 2
10
Project 3
11
Project 4
8
TM
1
9
12
10
10
ME
1
8
6
9
9
MBA
1
0
Dummy
Demand
Vj
Supply
0
0
0
1
1
1
This will not work, why not?
1
1
Ui
Prototype Problem
Hungarian Algorithm
• K-Corp has 3 parts, each of which can be
assigned to 1 of 3 machines. The problem
is to assign 1 part to one machine only so
as to minimize the total production costs.
Relevant data are:
Cost to Produce Part i on Machine j
Machine
1
2
3
1
9
10
10
Part
2
12
8
11
3
11
13
9
Prototype Problem
Hungarian Algorithm
• Step 1) Subtract the smallest number in each row from every
number in the row. (This is called row reduction.) Enter the
results in a new table.
Cost to Produce Part i on Machine j
Machine
1
2
3
1
9
10
10
Part
2
12
8
11
Machine
1
2
3
3
11
13
9
1
0
2
1
Part
2
3
0
2
3
2
5
0
Prototype Problem
Hungarian Algorithm
• Step 2) Subtract the smallest number in each column from
every number in the column. (This is called column
reduction.) Enter the results in a new table.
Cost to Produce Part i on Machine j
Machine
1
2
3
1
0
2
1
Part
2
3
0
2
Machine
1
2
3
3
2
5
0
1
0
2
1
Part
2
3
0
2
3
2
5
0
Prototype Problem
Hungarian Algorithm
• Step3. Test whether an optimal assignment can be made.
You do this by determining the minimum number of lines
needed to cover (i.e., cross out) all zeros. If the number of
equals the number of rows, an optimal set of assignments is
possible. In that case, go to step 6. Otherwise go on to step
4.
Machine
1
2
3
1
0
2
1
Part
2
3
0
2
3
2
5
0
Optimal, go to step 6.
Prototype Problem
Hungarian Algorithm
• 6. Make the assignments one at a time in positions that have
zero elements. Begin rows or columns that have only one zero.
Since each row and each column nee receive exactly one
assignment, cross out both the row and the column involved
each assignment is made. Then move on to the rows and
columns that are n crossed out to select the next assignment,
with preference again given to any such or column that has
only one zero that is not crossed out. Continue until every row
every column has exactly one assignment, and has been
crossed out.
Part
Machine 1 to Part 1
Machine
1
2
3
Machine 2 to Part 2
1
0
3
2
Machine 3 to Part 3
2
2
0
5
3
1
2
0
Hungarian Algorithm other
• 4. If the number of lines is less than the number
of rows, modify the table in the following way:
– a. Subtract the smallest uncovered number from
every uncovered number in table.
– b. Add the smallest uncovered number to the
numbers at intersections of cover lines.
– c. Numbers crossed out but not at the intersections
of cross-out lines carry over changed to the next
table.
• 5. Repeat steps 3 and 4 until an optimal set of
assignments is possible.