Question

Assignment problem and branch and bound

A factory produces a certain type of car parts. There are four alternative machines that can be used for the production of the car parts from start to finish. Each of the machines needs to be controlled by an individual operator. The operators have different efficiencies on different machines. The table below shows how many car parts the individual operators produce in average per day. Furthermore, this table shows how many erroneous parts the individual operators produce in average. Your task is to find out where the operators should be placed such that they produce as many as possible car parts. At the same time, the number of erroneous parts should not exceed 4 % of the total production.

Production per day:

	Machine A	Machine B	Machine C	Machine D
Operator 1	18	20	21	17
Operator 2	19	15	22	18
Operator 3	20	20	17	19
Operator 4	24	21	16	23
Operator 5	22	19	21	21

Number of erroneous parts per day:

	Machine A	Machine B	Machine C	Machine D
Operator 1	0,3	0,9	0,6	0,4
Operator 2	0,8	0,5	1,1	0,7
Operator 3	1,1	1,3	0,6	0,8
Operator 4	1,2	0,8	0,6	0,9
Operator 5	1,0	0,9	1,0	1,0

a) Set up a mathematical program for this problem.

b) Implement this problem in Excel and try to find a solution with the Excel Solver!

c) Neglecting the constraint concerning the erroneous products, how many feasible solutions does this problem have?

d) For health reasons, operator 1 needs to be placed on machine 1. Draw a sketch that can used as a departing point for a branch-and-bound approach that solves this problem more efficiently than brute force (brute force means that we evaluate all possible solutions).

e) Execute your version of the Branch-and-bound approach to solve this problem

Answer 1

Our objective here is to maximize the total number of parts produced. This means we need to consider the “Production per day” table as for the objective function. On the other hand, our constraint is that, total erroneous parts should not exceed 4% of the total production. So this will form the part of the constraint.

We know that each machine needs only 1 operator. Now, in this case we have total of 20 decision variables that hold binary values and indicate assignment. The model can be set up as shown below.

The formulation is shown below. We need to use these so that we can set the solver parameters accordingly.

The solver parameters are shown below. This is an assignment problem. As a result, we need to use the binary constraint on the decision variable table.

The result is shown below. The highlighted green cells inside the decision variable table is the solution and the maximum production possible with a limit of 4% error is 83 units.

PLEASE POST REMAINING PARTS SEPARATELY!