Crowdly
Add to Chrome
Assigning jobs to machines A workshop has five jobs to run today. Each job runs ...
✅ The verified answer to this question is available below. Our community-reviewed solutions help you understand the material better.
Assigning jobs to machines
A workshop has five jobs to run today. Each job runs on exactly one machine, each machine can run only a limited number of jobs in a day, and each job needs a machine with the right tooling. The workshop wants to run as many jobs as possible.
| machine | maximum number of jobs |
|---|---|
m1 | 1 |
m2 | 1 |
m3 | 3 |
| machine | jobs it can take |
|---|---|
m1 | j1 |
m2 | j2, j4, j5 |
m3 | j1, j3 |
Someone proposes to solve this with a flow network. It has a source s, one vertex per machine, one vertex per job and a sink t, with these edges:
| edges | how the proposal defines them |
|---|---|
| source edges | from the source to each machine, with capacity equal to that machine's own limit |
| middle edges | from each machine to each job it is allowed to take, with capacity 1 |
| sink edges | from each job to the sink, with capacity equal to the number of machines that could take that job |
They compute a maximum flow in it and report its value as the number of jobs that can be covered.
The proposal is wrong: on the instance above it reports a number that is too large. Answer all four parts.
- What is the value of a maximum flow in the proposed network on this instance? Describe a flow that achieves it.
- What is the true answer, i.e. the largest number of jobs that can be covered? Give an assignment that achieves it.
- Which requirement of the original problem does the proposed network fail to enforce? Explain exactly how the flow you gave in part 1 breaks that requirement.
- Repair the construction, and explain why your repair enforces the requirement.
Write in plain text. You may describe edges as s -> v1 and so on.