CarpetPlus sells and installs floor covering for commercial buildings. A CarpetPlus account executive, was just awarded the contract for five jobs. This executive now must assign a CarpetPlus installation crew to each of the five jobs. Because the commission, the executive will earn depends on the profit CarpetPlus makes, This executive would like to determine an assignment that will minimize total installation costs. Currently, five installation crews are available for assignment. Each crew is identified by a color code, which aids in tracking of job progress on a large white board. The following table shows the costs (in hundreds of dollars) for each crew to complete each of the five jobs.
Crew 1 2 3 4 5
Red 30 44 38 47 31
White 25 32 45 44 25
Blue 23 40 37 39 29
Green 26 38 37 45 28
Brown 26 34 44 43 28
(a) Develop a network representation of the problem.
(b) Formulate and solve a linear programming model to determine the minimum cost assignment.
rfdf
d
fd
fd
f
To solve this problem, we can use the network representation and linear programming model.
(a) Network representation:
In the network representation, we will have two sets of nodes: job nodes and crew nodes. We will connect each job node to each crew node with an arc, and assign a cost to each arc based on the installation cost for that particular crew on that particular job.
Here is the network representation for this problem:
Job Nodes: J1, J2, J3, J4, J5
Crew Nodes: C1 (Red), C2 (White), C3 (Blue), C4 (Green), C5 (Brown)
C1 C2 C3 C4 C5
--------------------------------
J1 | 30 25 23 26 26
J2 | 44 32 40 38 34
J3 | 38 45 37 37 44
J4 | 47 44 39 45 43
J5 | 31 25 29 28 28
Now, we can move on to formulating the linear programming model.
(b) Linear Programming Model:
Let Xij represent the assignment of crew i to job j, where Xij = 1 if crew i is assigned to job j, and Xij = 0 otherwise.
The objective is to minimize the total installation costs.
Minimize: 30X11 + 44X12 + 38X13 + 47X14 + 31X15 +
25X21 + 32X22 + 45X23 + 44X24 + 25X25 +
23X31 + 40X32 + 37X33 + 39X34 + 29X35 +
26X41 + 38X42 + 37X43 + 45X44 + 28X45 +
26X51 + 34X52 + 44X53 + 43X54 + 28X55
Subject to:
1. Each job should be assigned to exactly one crew:
X11 + X12 + X13 + X14 + X15 = 1 (for J1)
X21 + X22 + X23 + X24 + X25 = 1 (for J2)
X31 + X32 + X33 + X34 + X35 = 1 (for J3)
X41 + X42 + X43 + X44 + X45 = 1 (for J4)
X51 + X52 + X53 + X54 + X55 = 1 (for J5)
2. Each crew should be assigned to at most one job:
X11 + X21 + X31 + X41 + X51 <= 1 (for C1)
X12 + X22 + X32 + X42 + X52 <= 1 (for C2)
X13 + X23 + X33 + X43 + X53 <= 1 (for C3)
X14 + X24 + X34 + X44 + X54 <= 1 (for C4)
X15 + X25 + X35 + X45 + X55 <= 1 (for C5)
3. All decision variables should be binary:
Xij = {0, 1}
Solving this linear programming model will provide the optimal assignment of crews to jobs that minimizes the total installation costs.