pythonor-toolscp-sat

Scheduling problem : how to hanlde stock variation hover tasks


I'm trying to optimize a job shop manufacturing problem. I've managed to implement my constraints of tasks depending on the end of other tasks, optimization with respect to target dates and earliest/latest scheduling, thanks to the CP SAT solver in python.

On the other hand, there's one subject on which I get stuck no matter what solutions I try: inventory management. I've entered a JSON that looks like

{"stocks":{"toto": 600,"tata": 6000},"tasks": [{"id": 1,"duration": 50,"stocks_required":{"tata": 600},"stocks_produced":{"toto" : 10}},{"id": 2,"duration": 50,"stocks_required":{"tata": 600},"stocks_produced":{"toto" : 1}},{"id" : 3,"duration": 100,"stocks_required":{"toto": 660},"stocks_produced":{"tata" : 300}},{"id" : 4,"duration": 5,"stocks_required":{"tata" : 600,"toto" : 8},"stocks_produced":{"toto" : 60}}]}

So I have a list of tasks with their duration, the stocks they require and the stocks that are produced.
My aim is to schedule as many tasks as possible with no stock shortages, all references included.

Note that tasks can run in parallel, and it's possible that some stock may be missing. I really don't see how to correctly manage the variation of stocks over time, and the fact that moving tasks causes stocks to vary for the following tasks.

Thanks in advance for your feedback,

I've managed to handle the case without creating inventory by tasks, by freeing myself from time and simply maximizing the tasks without missing, as coded below:

from ortools.sat.python import cp_model
import json

# Définition des données
json_brut = """
    {
      "stocks": 
        {
          "toto": 600,
          "tata": 6000
        },
      "taches": [
        {
          "id": 1,
          "stocks_requis": 
            {
              "tata" : 600
            }
        },
        {
          "id": 2,
          "stocks_requis": 
            {
              "tata" : 600
            }
        },
        {
          "id": 3,
          "stocks_requis": 
            {
              "toto" : -600
            }
        },
        {
          "id": 4,
          "stocks_requis": 
            {
              "tata" : 600,
              "toto" : 8
            }
        }
      ]
    }
"""

data = json.loads(json_brut)

stocks = data["stocks"]
taches = data["taches"]

# Création du modèle
model = cp_model.CpModel()

# Définition des variables
execute_vars = {}
for tache in taches:
    execute_vars[tache["id"]] = model.NewBoolVar("execute_%i" % tache["id"])

# Définition des contraintes
for tache in taches:
    for stock, quantite in tache["stocks_requis"].items():
        model.Add(sum(execute_vars[t["id"]] * t["stocks_requis"].get(stock, 0) for t in taches) <= stocks[stock])

# Définition de l'objectif
objectif = sum(execute_vars.values())
model.Maximize(objectif)

# Résolution du modèle
solver = cp_model.CpSolver()
status = solver.Solve(model)

# Affichage des résultats
if status == cp_model.OPTIMAL:
    print("Solution optimale trouvée:")
    for tache in taches:
        if solver.Value(execute_vars[tache["id"]]):
            print("Tâche %i: exécutée" % tache["id"])
        else:
            print("Tâche %i: non exécutée" % tache["id"])
else:
    print("Aucune solution trouvée")

But nothing works, as soon as I add the time I'm lost, I can't see how to link my inventory variation to the start date of my tasks.


Solution

  • You can use the reservoir constraint.

    It is tailored for this use case.