3
$\begingroup$

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:

  1. Aspirate all 4 Source vials, then dispense to A1, B1, C1, D1
  2. Dispense E1 with 1st tip, then use 1st & 3d tips to dispense to F1, H1, then dispense to G1
  3. Use 2nd & 3d tip to dispense to A2, B2 then to C2, D2
  4. The rest will be filled by 1 tip at a time.

Here color represents which Target Vial should receive liquid from which Source Vial:

enter image description here

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.
$\endgroup$
0

2 Answers 2

1
$\begingroup$

If we focus solely on the dispensing operation, we can formulate this as a Set Cover Problem. Namely, we are given a set of tips that have already aspirated some source liquids and we are asked to minimze the number of dispense operations to fill up a given column of target vials. In this simplified set up, we aren't allowed to go back and aspirate new source liquids and we assume that the target volumes are less than the tip capacities.

To set this up as a Set Cover Problem, we treat each target vial as its own element in the universe. We associate with each configuration of the tips (e.g.: position and tip spacing) a set corresponding to the target vials that may be covered by this configuration, taking into account the aspirated fluids in each tip (i.e.: a target vial is "covered" by a tip configuration, if there is a tip that has aspirated the appropriate fluid and positioned over that vial).

$\endgroup$
0
$\begingroup$

One approach would be to view this as an operations research problem, where you have a scheduling problem with a bunch of constraints. A plausible approach would be to formulate this as an integer linear programming problem (or an instance of SAT), then solve using an off-the-shelf solver.

This reminds a bit of job shop scheduling, where you are minimizing makespan. However, your problem has many additional constraints that I suspect will be difficult to model within that framework, so I doubt it will be a useful framework for approaching your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.