3
$\begingroup$

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: enter image description here

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
------------------------------------------
$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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