I am afraid the question title might not be sufficiently accurate but I could not come up with something more accurate
Here is the problem
Given 'n' machines
- Each machine has a set of capabilities
- Each machine has max availability (A(m))
Given 'm' tasks
- Each task requires a set of capabilities
- Each task takes a certain time (D(t))
- A task has to be performed on one machine only
The problem is to determine whether all tasks can be completed.
I get stuck with the 'one machine only' requirement. The only flow graphs I can come up with do not guarantee a task is not linked to more than one machine.
It's sort of a bipartite matching problem but with capacities > 1
I also ran into XOR-like behavior in flow networks which is similar but has the 'xor' requirement on the 'source' end where I would need it on the target end.
Would anyone have any tips? Is it at all possible to model this as a flow graph?
PS Trying to clarify requirements with more concrete example
Assume digital print systems and print jobs
- Each digital press can run for a number of hours
- Each press has some finishing possibilities: e.g. 'sheet cutter', 'laminate', 'laser cutter', 'page folding', ....
- Each print job requires a number of hours
- Each print job needs one or more of the finishing possibilities
Given a set of machines, the availability for each and the finishing possibilities and also a set of print jobs (duration, finishing options needed) determine whether all print jobs can finish
- Printer p1 is available for a duration of 10 hours and has features f1 and f2
- Printer p2 is available for a duration of 10 hours and has features f2 and f3
- Job1, requiring features f1 and f2 takes 8 hours to run
- Job2, requiring features f2 and f3 takes 8 hours to run
- Job3, requiring feature f2 requires 4 hours to run
A printer that is available for e.g. 10 hours can run 10 x 1 hour jobs or 5 x 2 hour jobs, or 1 x 8 hr job and 1 x 2 hr job, ... Jobs always have to run on a single printer
The flow diagrams I could come up with always result in cases where
8 hours of p1 is assigned to job1 (leaving 2 hours for printer p1) 8 hours of p2 is assigned to job2 (leaving 2 hours for printer p2)
(so far so good)
The 2 hours of p1 and p2 left are used to flow to job3 and the max flow seems to indicate the three jobs can be run (which is not ok)