Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Optimisation for Business Processes

Coursework 1

MTH784P

2.  Consider the directed graph G whose vertices are the n projects 0, 1, 2, . . . , n − 1 and whose edges are the m constraints:  thus, an edge pq indicates that if project p is run then project q must also be run.   Suppose that the graph G contains a directed cycle (p0 , p1 , . . . , pé=p0 ).  Explain why the solution to the maximum flow problem constructed by your program necessarily places all projects {p0 , p1 , . . . , pé − 1 } on the same side of the minimum cut.                                                                                                          [3 marks]

3.  Consider two variants of the project scheduling problem.  In Variant A, projects can be run in parallel. In Variant B, whenever there is a constraint (edge) pq, project p can only be started once project q has been completed. What is the impact of having a cycle in the data (as described in Part 2) in the two variants?

Add a test to your program from Part 1 that warns the user when there is a cycle of dependencies.                                                                                                          [4 marks]

4. Now suppose that, in addition to a profit, each project has a duration d夕 , which is the time required to complete the project. Suppose also that we are in Variant B, so that projects with dependencies must be run in sequence. We are given a deadline D, and only projects completed by time D (starting at time 0) count towards the total profit.

Explain how you would now compute the optimal selection of projects. This problem can be answered using the algorithms we studied in the module as building blocks. You are not required to produce a program for this part, but you should provide a detailed explanation of your method.  Also try, as best you can, to justify the correctness of your approach.

[8 marks]