Modeling a job-scheduling problem with variable resource mapping

Question

I am new to google or-tools and I am trying to solve the following problem:

• a number of tasks with precedence constraints
• a pool of N resources
• resources are grouped by names (a: [0, 1], b: [2, 3, 4], ...)
• each job may acquire resources, either directly (job j needs resource 13 and 14) or indirectly (job j needs 1 resource of group a and 2 of group b)
• jobs may run in parallel if their precedence and resource constraints allow it, the amount of machines is unlimited
• all jobs are assumed to have the same execution time

I want to find a minimal makespan and I want to know:

• which job is supposed to run at any time t
• which resource is used by which job at time t

I implemented precedence constraints the following way:

from ortools.sat.python import cp_model

njobs = 5
precedence_constraints = [
    (0, 3),
    (0, 2),
    (1, 2),
    (2, 3),
    (2, 4)
]

model = cp_model.CpModel()

job_time = [ model.NewIntVar(0, njobs-1, 'j{}'.format(i)) for i in range(njobs) ]

for p, n in precedence_constraints:
    model.Add(job_time[p] < job_time[n])

model.Minimize(sum(job_time))

solver = cp_model.CpSolver()
status = solver.Solve(model)

for i in range(0, njobs):
    print('j{} = {}'.format(i, solver.Value(job_time[i])))

I do not understand how to implement the resource mapping.

Answer 1

You can try to model it as a nearly-classical flexible jobshop:

https://github.com/google/or-tools/blob/stable/examples/python/flexible_job_shop_sat.py

with the addition that you add a cumulative resource to help propagation (See this ongoing discussion on the or-tools mailing list: https://groups.google.com/forum/?hl=kn#!topic/or-tools-discuss/0syUImixcFI), and with the fact that the sum of active copies may be greater than 1.

This is not the most efficient, but it is easier to start that way. And it will be more robust if all durations are not equal.