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

Question

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
m.flag = Var(m.TASKS, m.DAYS, domain=Binary)

# 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    
for t in m.TASKS:
    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:
    m.c.add(sum([m.flag[t, d]*m.DURATIONS[t] for t in m.TASKS]) <= 8)

# earliest and latest time for tasks
for t in m.TASKS:
    for d in m.DAYS:
        if d < m.RELEASES[t]:
            m.c.add(m.flag[t, d] == 0)
        if d > m.DUE_DATES[t]:
            m.c.add(m.flag[t, d] == 0)


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 i in m.TASKS:
    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
------------------------------------------

Answer 1

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*}