network flow approach for maximizing number of jobs that can be scheduled

Question

I'm curious to lean the network-flow approach to solve this problem. Hope someone here can take time to help me construct an appropriate and suitable graph for this problem. The constructed graph, when solved for maximum flow should result in Job-Machine assignments maximizing number of jobs for given number of machines & job-schedule.


Given m machines and n jobs, with constraint m≤n. Use network flow algorithm to solve assignments for maximizing number of jobs with given number of machines.

Each job Ji has a start-time Si and Finish-time Fi. All machines are identical and can take at-most one job at a time. we have to find an assignment such that we can schedule maximum number of jobs.

Approach I've tried: -> jobs and machines forms the nodes in the graph.
->An edge from source to all Job nodes.
->An edge to terminal node from all machines.
->An intermediary node for each job node, which has incoming edges from each overlapping job node.
and stuck here how to proceed further.

I've worked out a solution by greedy approach, I'm curious to learn network-flow approach.

P.S: I've worked out a solution by greedy approach.
Asked the same question and was shot down with down votes without any explanation Hence re-asking as the previous question is not gaining any attention due to down votes.

Answer 1

How about this approach? I presume that you are familiar with the Circulation with Demand Problem.

Consider each job Ji to be a node, that has edge to Job Jj if Jj can be done after Ji, and Ji and Jj do not overlap in any way. Now consider a node for every machine also, and name it Mi. Now in this model, each Ji node has a demand of -1 and each machine has a demand of 0. Also add a node t, with demand n, and connect every Machine node m to it with capacity of n. every other edge has a capacity of 1.

Now solve this with circulation with demand and I think you will get your answer.