# How to merge tasks or do batching in a quality control lab

Background information:

In the Quality Control labs of pharmaceutical companies, analysts inspect products or raw materials in the units of ‘batches’ (which is essential a physical sample of bill, liquid or powder).

Typically, analysts do a set of tests on a batch/sample according to the requirements/documents.

Here we call one test applied on a batch a task.

Common constraints/objectives:

1. Each task has an earliest start time (release date of the task) and the latest finish time (the due date of the task). This is a hard constraint or an objective related to overall lateness. In this example, we set it as hard constraints.
2. There is limited resource. In this example, there is only a constraint for maximum 8 hours per day for working.
3. Typically we want to minimize the total working time. This is what we set in this example.

Key item to optimize:

There is an important practice that we can do to improve efficiency.

When two product/raw material batches come and there is a common test for them, analysts can merge them so they can be processed with less total processing time.

For example, (Batch #1 - Test 2) and (Batch #2 - Test 2) takes 6 hours separately. But if they are merged and processed together, the total time can is not 6*2 hours but can be only 8 hours.

A graphical illustration:

How could we tell the model that we want to merge tasks whenever resources allows?

A minimal reproducible code with pyomo and glpk :

from pyomo.environ import *
import pandas as pd

m = ConcreteModel()

m.DAYS = (1,2,3,4)

m.TASKS = ('Batch_1_Test_1', 'Batch_1_Test_2', 'Batch_2_Test_2', 'Batch_2_Test_3')

m.DURATIONS = {'Batch_1_Test_1': 4, 'Batch_1_Test_2': 6, 'Batch_2_Test_2': 6, 'Batch_2_Test_3': 4}
m.RELEASES = {'Batch_1_Test_1': 1, 'Batch_1_Test_2': 1, 'Batch_2_Test_2': 2, 'Batch_2_Test_3': 2}
m.DUE_DATES = {'Batch_1_Test_1': 2, 'Batch_1_Test_2': 2, 'Batch_2_Test_2': 3, 'Batch_2_Test_3': 3}

D = pd.DataFrame(index = m.TASKS, columns = ['Duration_hours', 'Release_date_index', 'Due_date_index'])
D.Duration_hours = m.DURATIONS.values()
D.Release_date_index = m.RELEASES.values()
D.Due_date_index = m.DUE_DATES.values()
D

#                Duration_hours  Release_date_index  Due_date_index
#Batch_1_Test_1               4                   1               2
#Batch_1_Test_2               6                   1               2
#Batch_2_Test_2               6                   2               3
#Batch_2_Test_3               4                   2               3

TWO_BATCH_MODE_DURATION_FOR_TEST_2 = 4

# array for tasks x days

# minimize the total processing time
m.OBJ = Objective(expr=sum([m.flag[i, j]*m.DURATIONS[i] for i in m.TASKS for j in m.DAYS]), sense=minimize)

m.c = ConstraintList()

# each task is done only once
m.c.add(sum([m.flag[t, d] for d in m.DAYS]) == 1)

# there is only 8 hours in a day
for d in m.DAYS:

# earliest and latest time for tasks
for d in m.DAYS:
if d < m.RELEASES[t]:
if d > m.DUE_DATES[t]:

SolverFactory('glpk').solve(m).write()

SCHEDULE_df = pd.DataFrame(index = m.TASKS, columns= m.DAYS)
SCHEDULE_HOURS_df = pd.DataFrame(index = m.TASKS, columns= m.DAYS)

for j in m.DAYS:
SCHEDULE_df.loc[i,j] = m.flag[i,j]()
SCHEDULE_HOURS_df.loc[i,j] = m.flag[i,j]()*m.DURATIONS[i]

print('------------------------------------------')
print(SCHEDULE_df)
print('------------------------------------------')
print(SCHEDULE_HOURS_df)


My output:

------------------------------------------
flags:
1  2  3  4
Batch_1_Test_1  0  1  0  0
Batch_1_Test_2  1  0  0  0
Batch_2_Test_2  0  0  1  0
Batch_2_Test_3  0  1  0  0
------------------------------------------
hours:
1  2  3  4
Batch_1_Test_1  0  4  0  0
Batch_1_Test_2  6  0  0  0
Batch_2_Test_2  0  0  6  0
Batch_2_Test_3  0  4  0  0
------------------------------------------


One way you can handle is to create combined tasks of (Batch #1 - Test 2) and (Batch #2 - Test 2) as a newer task (in your tasks set) and include this new task in your first set of covering/partitioning constraint. In more detail for 2 day case, Let say $$t_{1,1}$$ represent (Batch #1 - Test 2) completing task-1 on day-1 and $$t_{2,1}$$ represent (Batch #2 - Test 2) completing task-2 on day-1 and add new task task ($$t_{3,1}$$) that represent (both Batch #1 - Test 2 & Batch #2 - Test 2 completion on day-1). Similarly for $$t_{1,2}$$, $$t_{2,2}$$ and $$t_{3,2}$$ represents for tasks completion on day-2.
We can write following constraints. For task-1: \begin{align*} t_{1,1}+t_{3,1}+t_{1,2}+t_{3,2} = 1 \end{align*} for task-2: \begin{align*} t_{2,1}+t_{3,1}+t_{2,2}+t_{3,2} = 1 \end{align*}