Laboratory Samples Allocation Problem ^†

Abstract

This work aims to solve the optimization problem associated with the allocation of laboratory samples in plates. The processing of each of these plates is costly both in time and money, therefore the main objective is to minimize the number of plates used. The characteristics of the problem are reminiscent of the well-known bin packing problem, an NP-Hard problem that, although it is feasible to model as a linear programming problem, it cannot be solved at a reasonable cost. This work, proposes the implementation of a heuristic algorithm that provides good results at a low computational cost.

1. Introduction

The daily work of a laboratory requires processing samples in thermal cyclers as part of more complex processes. As processing each of the plates is costly in both time and money, the main objective of the work is to reorganize the samples in the plates taking into account the restrictions imposed by the characteristics of the thermal cycler.

The plates used by the laboratory consist of 8 rows and 12 columns, making a total of 9 6 wells. In turn, the 12 columns are divided into 6 temperature bands with 16 wells each. The first restriction imposes that the difference of temperature between two adjacent strips must be less than 5 °C.

The input data of the problem has the following characteristics, each sample occupies a well, each group of samples is processed at a certain temperature and, in addition, for each group is necessary to reserve a well to accommodate the group control. Figure 1 shows an example plate of this configuration.

The objective of the work is to obtain the distribution of the samples in plates in such a way that the number of plates used is minimized, the total number of cells used is minimized and the percentage of occupancy of the plates is maximized according to the lexicographical order.

2. The Algorithm

As seen in the article published by [1], since it is necessary to achieve a solution in a reasonable time, a heuristic algorithm, based on the simulated annealing method introduced by [2], has been developed. The idea of the method comes from the analogy between the process of metal annealing and the optimization of combinational problems. To implement this method, it is necessary to define the problem in terms of a solution space with a neighborhood and a solution space.

The algorithm starts from an initial solution, obtained by filling the plates with the samples ordered by temperature, bearing in mind that each group needs a present indicator, different groups with the same temperature can share a strip and it is possible to leave free strips to maintain the difference of 5 °C between consecutive strips. To this first solution, minimal changes are made (the neighbors), on which the objective function is calculated, which allows us to assess whether the change has been positive for the resolution of the problem. The movements that allow these changes are two, the exchange of strips and the grouping of samples dispersed by several plates.

3. Preliminary Results

The laboratory works with commercial software known as LabWare, against which the results of the implemented algorithm have been compared.

Table 1. Results and comparison.

Sample Count	LabWare	Heuristic Algorithm	Time Spent (s)
1473	22	19	71.25
1944	47	23	92.48
2071	41	25	59.03
2248	56	27	68.30
2496	36	30	83.08
2703	65	32	102.79
3783	90	44	109.73

shows a summary of the solutions obtained for a set of tests, showing the number of plates necessary in each option, accompanied by the execution time of the heuristic algorithm

4. New Challenges

In the real world, samples have different priorities (modeled by temporary windows), the processing capacity of plates is limited and sometimes it will be inevitable to postpone part of the work. In addition, the laboratory receives new samples to be processed periodically.

In order to face these new challenges, an architecture to generalize this work has been designed. This architecture must meet several requirements, such as maintaining the quality of the solutions, being able to carry out tasks in parallel with great autonomy and being of help to operators in making decisions.

This new approach consists of a web interface, capable of multiprocessing parallelism, scalable and able to work with the complete solution with which operators can interact. Figure 2 shows an example capture of the result of an execution.