job-schedulingor-toolscp-sat

Modeling a job-scheduling problem with variable resource mapping


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

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

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.


Solution

  • 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.