Consequential task assignments with possible soft constraint

[DaanSijbring]

Hi,

I am modeling a flexible job-shop problem that plans X jobs consisting of two tasks whilst taking job deadlines into account. Possible allocation of jobs to N suitable workers is done prior to modeling, and I am using the CP-SAT solver in Python.
Now, I am wondering about two things:

• What would be an efficient way to constrain the allocation of the second task of each job to a certain worker, based on which worker performed the first task? E.g. if worker 1 has performed task 1 of job X, it is known that worker 5 has to complete task 2 of job X. We can obviously make sure this is the only allowable combination of task division in the pre-allocation of options, but this might influence my second concern below.
• Is it possible to implement some sort of soft constraint on the allocation of the worker that performs task 2 of job X. In more simple terms, if worker 1 performs task 1 of job X, we have one preferred worker who can perform task 2 of job X, but also several backup workers for if the schedule does not allow allocation of task 2 to the preferred worker.

Thanks in advance, I am curious to see some ideas!

Kind regards,
Daan

[ghost]

Are you using OptionalIntervalVar?
If so, you can create a new boolean that is true iff worker1 does task1 and workerx does task2, and maximize those booleans in the objective

[ghost]

Please note that you shoudn't use any(), all() with boolvars as they truth value in python is always true.

[DaanSijbring]

Wow, that was a mistake easily avoided by not taking the shortcut 👍 Thanks.
However, adding individual implications for the BoolVar that tracks the score still seems to fail. It does not influence the allocation of tasks to workers. Instead of the approach in my previous response, I use:

# create preferred boolean
                suffix = '_j%i_trans%i_proof%i_preferred' % (order_id, emp_id, pref_id)
                hit = model.NewBoolVar('hit' + suffix)
                for opt in opt_pref_proof_pres:
                    model.AddImplication(opt, hit)
                scorePreferred.append(hit)

Where again opt_pref_proof_pres contains all presences for all possible IntervalVars during which the preferred worker for job 2 can be present.

In your previous example, you use two instances of AddImplication. I create the BoolVar only when the worker has an option for performing job 1, should this not be enough? Thanks!

[DaanSijbring]

Also, both option do not seem to work. I have created two more Booleans for each worker for each task, indicating whether they performed the task. Next, I add two implications for when worker x has performed task 1, and when worker y (preferred) has performed task two to imply that this combination (hit) is scored. It seems it still doesn't enforce that this is the only option, it still assigns true to these score BoolVars without enforcing the required combination of task division.

Any idea on how to enforce the score BoolVar to be True iff both required works performed the respective tasks?

[ghost]

Something like this?

if opt_pref_proof_pres:
    hit = model.NewBoolVar('hit' + suffix)
    # hit => worker1, task1
    model.AddImplication(hit, assigned[worker1, task1])
    # hit => (workerx, task2) or (workery, task2) or (workerz, task2)
    model.AddBoolOr(opt_pref_proof_pres+ [hit.Not()])

[DaanSijbring]

Hi there,

Thanks again for your input, I really am struggling with this part. Enforcing the 'preferred' combination of workers and tasks, however, does not seem to work at all, not even with your latest suggestion. I am afraid I'm overlooking something in the logic of when a BoolVar should be true because right now, it seems that the model considers all possible interval options to be true. What I'm working with right now assumes a dict of presences that are linked to the OptionalIntervalVars for every option of completing a task. So, each presence is keyed by a tuple of (order_id, task_id, worker_id, day_id, Boolean indicating overlap). Then, for each worker able to complete the first task of a certain job, I create a BoolVar indicating whether or not they performed that job:

transOpts = list(set([p[2] for p in job_presences if p[1] == 0]))
        transBools = {}
        for trans in transOpts:
            transPresences = [job_presences[p] for p in job_presences if p[1] == 0 and p[2] == trans]
            transBool = model.NewBoolVar('%i_translated_order_%i' % (trans, order_id))
            for presenceOption in transPresences:
                model.AddImplication(presenceOption, transBool)
            transBools[(order_id, trans)] = transBool

I do the same for each worker able to complete the second task of that same job:

proofOpts = list(set([p[2] for p in job_presences if p[1] == 1]))
        proofBools = {}
        for proof in proofOpts:
            proofPresences = [job_presences[p] for p in job_presences if p[1] == 1 and p[2] == proof]
            proofBool = model.NewBoolVar('%i_proofread_order_%i' % (proof, order_id))
            for presenceOption in proofPresences:
                model.AddImplication(presenceOption, proofBool)
            proofBools[(order_id, proof)] = proofBool

Next, I look at each worker that is able to perform the first task, select their preferred co-worker for the second task and, according to your latest help, score whether or not the combination occurred:

for trans in transOpts:
            [emp] = [e for e in emps if e['userInfo']['id'] == trans]
            for i in range(len(emp['userExpertise'])):
                exp = emp['userExpertise'][i]
                if exp['lang_from'] == order['langFrom'] and exp['lang_to'] == order['langTo'] and exp['theme_name'] == order['theme']:
                    pref_id = exp['pr_prefer'][0]['id']
                    if exp['pr_backup']:
                        backup_id = exp['pr_backup'][0]['id']
                    else:
                        backup_id = False
            if (order_id, pref_id) not in proofBools.keys(): continue
            if proofBools[(order_id, pref_id)]:
                hit = model.NewBoolVar('job_%i_score_trans_%i_proof_%i' % (order_id, trans, pref_id))
                model.AddImplication(hit, transBools[(order_id, trans)])
                model.AddBoolOr([proofBools[(order_id, pref_id)]] + [hit.Not()])

However, the if proofBools[(order_id, pref_id)]: statement seems to hit every time because I end up with a list of Booleans created by all combinations of workers, and the solver stated that all are True, which cannot be. I am new to or-tools and constraint programming as a whole, so I think I must be missing some insight into how these Booleans are constrained amongst each other.

[ghost]

Yes, if boolvar: always evaluate to true.
I can't really help you debug your code but I'll leave a full example here, hope it helps:

from ortools.sat.python import cp_model

model = cp_model.CpModel()
workers = range(3)
tasks = range(2)

prefer_task1 = {
    # if worker 0 does task 0 prefer worker 1 for task 1
    0: [1],
    1: [2],
    2: [0, 1],
}

assigments = {(t, w): model.NewBoolVar("") for t in tasks for w in workers}
# 1 worker per task
for t in tasks:
    model.Add(sum(assigments[t, w] for w in workers) == 1)

pref_booleans = []
for w0, prefs in prefer_task1.items():
    tmp = model.NewBoolVar("")
    # worker does task[0]
    model.AddImplication(tmp, assigments[tasks[0], w0])
    # a prefered worker does task[1]
    model.AddBoolOr([tmp.Not()] + [assigments[tasks[1], w1] for w1 in prefs])
    pref_booleans.append(tmp)

# Test
# model.Add(assigments[0, 0] == 1)

model.Maximize(sum(pref_booleans))
solver = cp_model.CpSolver()
solver.Solve(model)

for task in tasks:
    for w in workers:
        if solver.Value(assigments[task, w]):
            print("Task", task, "Worker", w)

[DaanSijbring]

@stradivari96, thank you so much for your help and insights! I was able to get it working with your example above, I didn't realize the difference in using AddImplication or AddBoolOr - this was certainly necessary to properly account for the 'possible' time slots a worker could perform the task in. Simplicity was key 👍 Thanks