Question

You are given n jobs and m machines where each machine has a subset of machines that they are able to be processed on. Using the Ford-Fulkerson algorithm, construct an algorithm that determines the smallest integer where no machine gets assigned more jobs than.

Answer 1

We will reduce this problem to max-flow problem which uses Ford-Fulkerson algorithm. For this we will create a graph G as follows:-

1. First create bipartite graph with set L as set of jobs and vertex set R as set of machines.

2. Create a directed edge with capacity 1 unit from vertex u in set L to vertex v in set R if the job u can be served by machine v.

3. Now add a vertex s to be used as the source vertex and create directed edges with capacity 1 unit from vertex s to each vertex in set L.

4. Add a vertex t to be used as the sink vertex and create directed edges with from all the vertices in set R to vertex t. The capacity of vertex R to t will decide the maximum number of loads on each machine.

Now our goal is to find the minimum integer capacity that can be assigned to the edges from vertex set R of machines to vertex t such that total flow received on pushing max-flow from source vertex s to target vertex t is n. Hence if the minimum capacity value of edges from set R to vertex t is k then this means that there will be a machine serving k jobs, in order to get all the jobs served. Hence the value k obtained from above will be our answer. In other words, k is the smallest integer where no machine get more than k jobs.

Below is the algorithm named Smallest_Load with input to the algorithm is graph G which perform Ford-Fulkerson algorithm from vertex s to t by setting value of k from 1 to n and it will stop for that particular value of k in which total flow received at t is n i.e. total number of jobs.

Smallest_Load(G)

1. For k = 1 to n //since maximum value of k can be n in which all the n jobs will be served by single machine

2............Assign capacity k to all the edges from machine set V to target vertex t.

3............Push max-flow using Ford-Fulkerson algorithm from source s to target t.

4............If max-flow == n then //this means maximum load given to a machine is k

5.......................Return k //maximum jobs that can be served by a machine will be k

6. Return

Thus above algorithm will give desired result by performing Ford-Fulkerson algorithm at most n times .

Please comment for any clarification.