I'm looking for suggestions on algorithms, data structures or at least problems (so that I look for solutions in that domain) to consider. I realize that exact solution probably doesn't exist. But the more similar problems/solutions I can find the more ideas they may inspire.
We need to transfer reactants from source vials to target vials where they'll be mixed with other reactants and be a part of chemical reactions.
Settings: a liquid handling robot has up to 8 tips which can aspirate (suck in) & dispense (spit out) liquid from/to multiple vials. They can do this either simultaneously or one-by-one.
Input: list of source vials, list of target vials, mapping between source and target vials as well as volume to be transferred.
Goal: minimize time to transfer. This usually means maximize the amount of time tips work simultaneously. To simplify the problem - lets optimize (meaning group them) only dispense operations.
Example
E.g. we aspirate from Source vials and dispense to Target vials. In this example we'll use 4 tips:
- Aspirate all 4 Source vials, then dispense to A1, B1, C1, D1
- Dispense E1 with 1st tip, then use 1st & 3d tips to dispense to F1, H1, then dispense to G1
- Use 2nd & 3d tip to dispense to A2, B2 then to C2, D2
- The rest will be filled by 1 tip at a time.
Here color represents which Target Vial should receive liquid from which Source Vial:
Additional conditions
- Simultaneous aspiration/dispense is possible only when vials are located in the same column.
- Tips can change the spacing between them. E.g. 1st & 3d tip can either dispense to E1 & H1 or F1 & H1 simultaneously.
- Tips have max volume (1mL). If you need to dispense more - you'll have to return back and aspirate more.
- Volume to be dispensed is different in different locations.
- We could've aspirated with 2 tips from the same vial and then transfer the same substance with these 2+ tips. But for simplicity let's not consider this option.