3
$\begingroup$

So, I'm modelling a job assigning problem in OR-Tools CP-SAT. I want to maximize rescheduled jobs based on some constraints. Right now jobs in my model look like this:

jobs = [(1, 1, 1, 3, 1),           # job id, job type, start time, length, worker id
         ...
        (7, 5, 9, 1, 4)]

And the way I initialize data looks like this:

for h in range(horizon):
    ...
    for w in workers:
        ...
        for jt in job_types:
            ...
            for job in jobs:  

The data on top level is stored in smth like:

 List<List<List<List<IntervalVar>>>> intervals_by_hour

Based on all of this I find it pretty hard already to initialize everything and select some of the data ranges to make constraints. Next, I would like to widen a job definition a bit, so I feel that I'll have another layer of for loops and a hard time isolating entities from them.

So the question is: Am I doing something wrong or is it some acceptable way of doing so? I've looked through examples and some books, and rn I dont feel neither those examples fit my needs well, nor some of them feel better in modeling part

Initial task: I get some jobs from the ERP system that (in this example) can overlap each other by the workers attached to them. (E.g. Alex can be assigned to job1 and job2 at the same time), so I want to reschedule such jobs. Every job consists of job ID, job type, start time, length, worker id. Right now in my model I use BoolVars to indicate that job exists and OptionalIntervals for a job to exist if BoolVar exists. Basically I want jobs of one type to not overlap, jobs of one worker to not overlap and to maximize the sum of scheduled jobs

performed_at = model.NewBoolVar("performed by %dh %dw %dj %dt" % (h, w, job[0], jt))
start = model.NewIntVar(h, h, "start of %dh %dw %dj %dt" % (h, w, job[0], jt))
end = model.NewIntVar(0, horizon, "end of %dh %dw %dj %dt" % (h, w, job[0], jt))
optint = model.NewOptionalIntervalVar(start, job[3], end, performed_at, "interval of %dh %dw %dj %dt" % (h, w, job[0], jt))

Full source code of working model: Model

$\endgroup$
8
  • 3
    $\begingroup$ this is much too vague to be useful. Please post a complete standalone small example that describe what your are doing, what you want to achieve. $\endgroup$ Feb 6, 2022 at 12:58
  • $\begingroup$ Thanks, updated the task and linked a source code $\endgroup$
    – Gleb S
    Feb 6, 2022 at 15:31
  • 1
    $\begingroup$ I do not understand why you need 4 loops to create intervals. Look at the flexible jobshop example, you have one loop per task and one loop per worker that can perform this task. $\endgroup$ Feb 6, 2022 at 20:51
  • $\begingroup$ I get what you mean, but for example I looked at ortools github - and yet they basically use FOR loop to initialize every entity (of every entity) present (like I do). In my case I have constant horizon for rescheduling + I want to maximize the number of possible planed jobs (theres possibility that it would be impossible to plan as desired in ERP system), that's why I iterate with horizon - workers - types - jobs, and my variables basically say - "Can job (and its interval) start at that minute" $\endgroup$
    – Gleb S
    Feb 7, 2022 at 15:06
  • 1
    $\begingroup$ why don't you have 1 interval per task to schedule with a variable start ? $\endgroup$ Feb 7, 2022 at 20:11

1 Answer 1

2
$\begingroup$

So, with a great help of Mr. Perron I understood my own assignment!

Basically I was linking my OptionalIntervals to the particular points in time, making it time and memory consuming. I really thought that BoolVar for OptInterval should be bound to specific moment in time, yes.

In fact there were no need to do it and it really is 1 interval per task and some constraints, so, flexible job-shop kinda.

The final look

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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