CS535 Homework 3
程序Homework代写 Suppose that we know a non-integer maximum áow in a áow network with integer arc capacities. Give an algorithm…
1. Suppose that we know a non-integer maximum áow in a áow network with integer arc capacities. Give an algorithm for converting this áow into an integer maximum áow in O (mn) time where m is the number of edges and n is the number of nodes in the áow network. (Hint: The residual edges with fractional residual capacity contain a circuit.) 程序Homework代写
2. A set J of jobs are to be scheduled on m identical machines. Each job j 2 J has a processing requirement pj (denoting the number of machine days required to complete the job), a release date rj (representing the beginning of the day when job j becomes available for processing), and a due date dj rj + pj (representing the beginning of the day by which the job must be completed). We assume that a machine can work on only one job at a time and that each job can be processed by at most one machine at a time. However, we allow preemptions (i.e., we can interrupt a job and process it on di§erent machines on di§erent days). The scheduling problem is to determine a feasible schedule that completes all jobs before their due dates or to show that no such schedule exists. Formulate this problem as a maximum áow problem.
3. An airline has p áight legs that it wishes to service by the fewest possible planes. To do so, it must determine the most e¢ cient way to combine these legs into áight schedules. The starting time for áight i is ai and the Önishing time is bi . The plane requires rij hours to return from the point of destination of áight i to the point of origin of áight j. Formulate this problem as a minimum áow problem. 程序Homework代写
4. Consider a computer system with two processors (which do not have to be identical) on which a large program should be executed. The program contains n modules i = 1; ; n that interact with each other during the execution of the program. Let i and i denote the cost for computing module i on processors 1 and 2, respectively. Assigning di§erent modules to di§erent processors incurs additional costs due to interprocessor communication. Let cij denote the interprocessor communication costs if modules i and j are assigned to di§erent processors. We wish to allocate modules of the program to the two processors such that the total cost of processing and interprocessor communication is minimized.
5. A commander is located at one node p in a communication network G and his subordinates are located at nodes denoted by the set S. Let cij be the e§ort required to eliminate arc (i; j) from the network. The problem is to determine the minimal e§ort required to block all communications between the commander and his subordinates. How can you solve this problem in polynomial time?
