Optimizing Contractor Assignment and Min-Cost Network Flow Problem

Part 1: Contractor Assignment for Limited-Edition Race Car Production

SilverStone car company has decided to produce a limited-edition race car. The main parts of this car would be produced in a week at a special machine shop with contractors (from Monday to Sunday). There are two types of contractors; type A and type B. These contractors can be assigned to work at any day of the week. When a contractor of type A starts to work, s/he will work three days consecutively and cannot work more than three days a week. Similarly, when a contractor of type B starts to work, s/he will work two days consecutively and cannot work more than two days a week. For instance, if a contractor of type A starts to work on Wednesday, s/he will work on Wednesday, Thursday and Friday and will not return to work. On the other hand, if a contractor type B starts to work on Wednesday, s/he will work on Wednesday and Thursday and will not return to work. If a contractor starts to work on Saturday or Sunday, s/he will work for the required days since the prototype car production will end at the end of Sunday. For instance, if a contractor of type A starts to work on Saturday, s/he will only work on only Saturday and Sunday.

The company can hire as many contractors as required with no constraints. However, due to production plan, the requirement of contractors for each day is different. The following table shows the number of required contractors (type is not important since they work on the same process) at each day. In addition, only one type of contractor should be working on Wednesday, either type A or type B but not both. There is no such a restriction for the other days. Due to the high workload on Thursday, the company would like to work with both contractor of type A and type B on Thursday. 

The cost of type-A and type-B contractors is the same. Therefore, SilverStone car company wants to minimize the total number of contractors (type A and type B) hired for the production of race car.

Part 1.1 [30%]: By considering the information given in the above problem, formulate and solve an integer programming model to determine the number of contractors assigned to produce this race car. Present both the problem formulation and the solution.

Part 1.2 [20%]: Considering the required resources on each day, analyze the optimal solution of your model. What do you think about the applicability of your assignment schedule? Would it be possible to improve the schedule? If possible, what would be your modelling approach? Explain your approach and findings. 

In the following network, let be the supply node and , be two demand nodes. Let all the other three nodes be transshipment nodes. The number at each arc in the network represents the unit cost for a flow to traverse through the arc. The capacity of each arc is large enough so that it is assumed to be infinity. 

Part 2.1  Suppose node has a supply of 2 units and nodes , have a demand of 1 unit each. Apply the formulation for the general min-cost network flow problem to the instance given on the network and provide a linear programming (LP) formulation for the instance, without solving it. How many variables are there? How many constraints (excluding non-negativity constraints) are there? Provide all the details of your formulation without any omission.

Part 2.2: Let ∗ and ∗ be the optimal solution (vector) and the corresponding optimal value in Part 2.1, respectively. Now suppose node has a supply of 3 and nodes , have a demand of 1.5 each. Without solving the LP, answer the following questions: Will the original optimal solution ∗ change? If not, why? If yes, what is the new optimal solution? Will the optimal value ∗ change? If not, why? If yes, what is the new optimal value?

Part 2.3 Apply the weak duality theorem to your formulation in Part 2.1 without solving the LP to give a lower bound on the original optimal value ∗ . Provide all the details of your justification.