scheduling problem with variable delays between tasks

[gregy4]

Hello,
I have scheduling problem with tasks and workers assigned to tasks - scheduling + assignment problem.

In case I need to respect time when a worker moves between some tasks, a circuit constraint is used for every worker with a node for every task that can be assigned to a worker. This produce a lot of boolean variables for possible edges between nodes that affects speed and used memory.

I realized that a worker moving between tasks can be seen in different way as a vehicle moving between places and this is vehicle routing problem.

Is there a chance when I rewrite the problem to VRP (don't know whether it is completely possible) to get better results ?

As an alternative to circuit constraint in cp-sat solver I see a variant of noOverlap constraint with distance matrix between optional intervals. This can guarantee movement time for worker between tasks but doesn't help when minimization of movements will be requested. I think I saw similar constraint in documentation of ibm cp optimizer.

Best regards,
Jan

[lperron]

By definition, the problem is quadratic, either with the routing model, or the scheduling + circuit model, or the disjunctive model. So pick your poison.

[gregy4]

Thanks :-)

Is there some shortcut to guarantee distance between optional intervals ?
Otherwise I have to use extra variable for order of intervals, something like that:

s1 < s2.onlyEnforceIf(b)

s2 - e1 >= walking time . onlyEnforceIf(b, p1, p2)

s1 - e2 >= walking time . onlyEnforceIf(b.not, p1, p2)

[lperron]

No, this is the fully disjunctive model. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mer. 1 déc. 2021 à 14:29, gregy4 ***@***.***> a écrit :

…

Thanks :-) Is there some shortcut to guarantee distance between optional intervals ? Otherwise I have to use extra variable for order of intervals, something like that: s1 < s2.onlyEnforceIf(b) s2 - e1 >= walking time . onlyEnforceIf(b, p1, p2) s1 - e2 >= walking time . onlyEnforceIf(b.not, p1, p2) — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2940 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3P4ET33RKDTGUS6DC3UOYPLJANCNFSM5JD2B35A> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[lperron]

Note you should remove the first equation 's1 < s2.onlyEnforceIf(b)' in the general case.

[gregy4]

Good point :-)
Works better for smaller datasets, for bigger datasets first equation for main interval (optional interval represents assigned worker) allowed me to reuse order variable b.
So far it seems that disjunctive model is better than circuit model but both fail on large datasets. With over 2000 tasks and 700 workers a model contains over 50 milions of channeling constraints to guarantee just walking time between tasks. I didn't have enough patience to wait for creation of a model.

[jmarca]

Sorry this is slightly off topic. I’m very curious about the problem domain, mostly because I’ve been thinking a lot lately about partitioning strategies. Are all 700 workers really necessary to be solved simultaneously? For example, if workers are identical, and if a worker is pre-assigned job A, is it still possible for that worker to perform any of the other 2k tasks?

If being assigned 1 job reduces to feasible set, and if jobs have some differentiating characteristic, maybe you can run a randomized partitioning step to break up the problem into disjoint sets that are easier to solve.

[gregy4]

Each worker has a skill and a task needs a skill with given quantity. Sometimes a tasks can choose only from subset of skill workers. In the dataset I'm talking about is seven skills.

It is good approach to divide a problem into subproblems. But when number of workers should be minimized it is not so easy. Sharing of workers over all tasks should be theoretically always better (in worst case) equal to a solution from subproblems. So question is how to divide tasks and workers. Smaller subproblems generate less optimal global solution.

[lperron]

And after the first solution has been found, you can select random (or not) subsets of the intervals, and run some (external) LNS on each subset. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le ven. 3 déc. 2021 à 17:13, James Marca ***@***.***> a écrit :

…

Sorry this is slightly off topic. I’m very curious about the problem domain, mostly because I’ve been thinking a lot lately about partitioning strategies. Are all 700 workers really necessary to be solved simultaneously? For example, if workers are identical, and if a worker is pre-assigned job A, is it still possible for that worker to perform *any* of the other 2k tasks? If being assigned 1 job reduces to feasible set, and if jobs have some differentiating characteristic, maybe you can run a randomized partitioning step to break up the problem into disjoint sets that are easier to solve. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2940 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MKPZYY4TPZDVJJYPTUPDUDVANCNFSM5JD2B35A> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[yinxiongchen]

@lperron
I am having the same issue. If I use addCircuit to add delay or sequence to the jobs, workers are not enabled to work in parallel in the output solution. But I am expecting to allow workers to work at the same time, which means there should be multiple circuits in the output, one worker one circuit. I have create a cpModel with 10+ constraints. Circuit is the only one unfixed.

I have checked multiple references, it doesn't seem to be answer. Can you help me with some guidance, please? Thanks.

#3924
https://github.com/google/or-tools/blob/main/ortools/sat/docs/scheduling.md#transitions-in-a-no_overlap-constraint