How to model a job scheduling/assignment problem

[Richard Brown]

We're attempting to solve a problem that seems to combine elements from Scheduling (job shop) and Assignment examples. The problem can be summarised as:

• Workers are assigned tasks
• The cost of each task varies depending on the worker assigned to it
• Some workers can only work on specific types of task
  
• Multiple tasks make up a job and occur in a specific sequence
  
• We are trying to minimise the end time of the jobs
• Workers may have periods of unavailability, e.g. lunch break, holiday, etc.
  

We've implemented a solution based on the Job Shop Problem but it has severe performance issues (see this GitHub issue).

We have now been looking at Assignment Problem, which also looks applicable to our problem.

What would be the best approach to this? Are we getting such serious performance issues because we're looking at it the wrong way?

Any help or advice would be much appreciated.

Richard.

[Gabrielly Carvalho]

Hello!

I'm going through a very similar situation. Were you able to resolve the performance issue?

[grego...@gmail.com]

It seems that original author never gave or-tools team data, proto file or some basic info about size of his problem.

From my experience (similar problem) I can say it is possible to use cp-sat solver with a few thousand tasks. For larger instances it is very beneficial to work with capacities instead individual workers (if possible) and assign workers later when task placement is given.

Jan 

[cfs]

Hi,

I think, we also worked on a similar job shop problem as in the post at the top of this thread.

But you have to take care very much about the details!

In our case it is not a weighted assignment problem, but many SAME tasks (in terms of scheduling, batches).

So there are lots of possibilities to assign them to machines (but does not change the schedule or scheduling objective just indexing ..)
The machine has a NoOverlap for all its tasks.

Then it was much faster (ortools 9.6) to restrict assignment via constraints (linear or AllowedAssignments), see illustration attached for an example of n=4 tasks :-)

> @Jan

> From my experience (similar problem) I can say it is possible to use cp-sat solver with a few thousand tasks. For larger instances it is very beneficial to work with capacities > instead individual workers (if possible) and assign workers later when task placement is given.

So that is scheduling a single machine/worker after you have planned the amounts for machines/workers?

How do you calculate a makespan bound during planning? Is this logic-based Benders decomposition?

Christoph

[grego...@gmail.com]

In case I have for example 10 identical workers, 10 optional intervals for every possible task is replaced by integer variable that represents used amount. An equation for a task is needed in case other worker outside the group of workers can be used to fulfill task requirement. Cumulative constraint over all possible tasks with height given by used number of workers from a group guarantees that a solution will be valid. In next step is solved MIP problem where worker assignment for the group of workers should be identified but simple assignment of workers to tasks ordered by a position on a timeline should be also fine.

Massive reduction of model variables leads to much simpler a faster model to solve. Unfortunately sometimes we need to work with workers individually.