Contexte

Le Bureau de la stratégie d'IA, auquel j'appartiens, organise une "Réunion de consultation sur les problèmes d'IA" en interne pour rechercher des solutions en combinant des outils et des bibliothèques existants pour répondre aux besoins de "Vous ne pouvez pas faire cela?" Nous faisons également des affaires.

Par exemple, il existe un service appelé LIFULL HOME'S Living Counter. Il s'agit d'un service qui vous permet de consulter gratuitement un conseiller dédié à la recherche de logements en matière de construction et de recherche de logements.

Est-il possible d'automatiser et d'optimiser le mécanisme de création d'un décalage pour ce conseiller en recherche de logement? Aujourd'hui, je voudrais vous présenter l'une des façons d'utiliser Google OR tools que j'ai trouvée là-bas.

exemple

Vous avez décidé de faire un quart de 5 conseillers à la recherche à domicile.
Puisqu'il est pratique pour l'illustration, je l'appellerai Ichihana, Nino, Sanku, Yotsuba et May.
Pour simplifier le problème, envisagez un seul changement de magasin.
Il y a 3 créneaux par jour x 7 jours qui peuvent être réservés.
Supposons qu'il n'y ait qu'une seule salle de conseil et que deux personnes ne puissent pas servir les clients (recevoir des réservations) en même temps.
Le travail de consultation étant difficile, le conseiller ne peut changer qu'un seul créneau par jour.
Il est souhaitable qu'il y ait le moins de biais temporel possible parmi les cinq personnes.
Il est souhaitable d'effectuer des quarts de travail pour répondre le plus possible au désir de travailler du conseiller

Résoudre comme problème de satisfaction de contrainte

Ces problèmes de planification peuvent parfois être résolus sous forme de problèmes de respect des contraintes (CSP).

Certaines conditions doivent être remplies, mais elles sont importantes

Conditions qui répondent à la contrainte
Conditions que vous souhaitez optimiser

Si vous pouvez y penser séparément, vous pouvez le résoudre à l'aide d'un solveur.

Tout ce que vous avez à faire est de demander au solveur de calculer la solution qui satisfait les conditions de contrainte, puis de spécifier les conditions que vous souhaitez optimiser. ici,

Deux personnes ne peuvent pas être dans le même quart de travail en même temps
Les conseillers ne peuvent changer qu'un seul créneau par jour
Essayez d'éviter le biais de temps autant que possible

Comme condition de contrainte

Remplissez autant de conseillers que possible

Optimisons la valeur.

Déclarer un modèle

Tout d'abord, préparez un modèle du solveur. Ici, nous utilisons le modèle CP-SAT. Consultez https://developers.google.com/optimization/cp/cp_solver pour plus de détails.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

Préparer les variables

Ensuite, préparez une variable à utiliser pour l'indicateur de planification.

Par exemple, si vous effectuez un décalage de s frame pendant d jours pour n conseillers, vous pouvez créer le tableau de décalage suivant.

Afin de sortir le tableau ci-dessus comme résultat de calcul, si vous le décomposez comme suit et en faites un "tableau tridimensionnel" de n, d, s

Si 1 est inclus dans l'élément, allez au travail
Si 0 est entré, ne va pas travailler

Peut être considéré comme.

En d'autres termes, la question de savoir où placer le drapeau dans le «tableau tridimensionnel» de «n, d, s» a été réduite.

Définissons une constante selon cet exemple.

    num_advisers = 5
    num_shifts = 3
    days = ["journée", "Mois", "Feu", "eau", "bois", "Argent", "sol"]
    num_days = len(days)
    adviser_name = ["Peut", "Ichihana", "Nino", "Sanku", "Yotsuba"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)

La variable pour définir l'indicateur 0 ou 1 et demander au solveur de la résoudre est créée en tant qu'instance de la classe `` ortools.sat.python.cp_model.IntVar '', elle ressemble donc à un tableau pseudo multidimensionnel utilisant dict. Je vais préparer quelque chose qui peut être utilisé.

    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

Mettre des contraintes

Les contraintes sont saisies avec model.Add ().

** Deux personnes ne peuvent pas être dans le même quart de travail en même temps: ** Assurez-vous qu'un seul drapeau est défini lorsque le diagramme "3D array" est visualisé depuis "top".

    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)

** Les conseillers ne peuvent changer qu'un seul créneau par jour: ** Assurez-vous qu'un seul indicateur est défini lorsque le diagramme "tableau tridimensionnel" est visualisé depuis le "front".

    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)

** Évitez autant que possible les biais temporels: ** Puisqu'il y a un cadre 3 × 7 = 21, définissez le cadre 21 // 5 = 4 comme limite inférieure, Il semble qu'il n'y aura pas de biais si le cadre (21 // 5) + 1 = 5 est défini comme limite supérieure pour chaque conseiller. Dans le diagramme "3D Array", ajoutez tous les indicateurs de la table du plan pour chaque conseiller afin que le résultat soit supérieur ou égal à la limite inférieure et inférieur ou égal à la limite supérieure.

    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)

Acceptez les souhaits du fuseau horaire

Ensuite, quantifiez le désir "d'entrer dans ce quart de travail!" Cela peut être une valeur simple de 0 ou 1, alors préparez-le comme un tableau multidimensionnel avec obéissance.

Si 1 est inclus dans l'élément, vous voulez aller travailler
Si l'élément contient 0, vous ne voulez pas aller travailler

Si vous décidez, vous pouvez quantifier les souhaits de décalage pour 5 personnes comme le tableau 3D suivant.

    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],   #Ichihana
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]

Ici, lorsque shifts contient une valeur, si le calcul de shift_requests [n] [d] [s] * shift [(n, d, s)] est effectué pour chaque élément, Le résultat du calcul est 1 uniquement lorsque "l'élément répond aux souhaits du conseiller". En passant cela à une fonction appelée model.Maximize, vous pouvez indiquer au solveur les conditions d'optimisation.

    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))

https://developers.google.com/optimization/scheduling/employee_scheduling

Programme complet

from ortools.sat.python import cp_model


def main():
    # This program tries to find an optimal assignment of advisers to shifts
    # (3 shifts per day, for 7 days), subject to some constraints (see below).
    # Each adviser can request to be assigned to specific shifts.
    # The optimal assignment maximizes the number of fulfilled shift requests.
    num_advisers = 5
    num_shifts = 3
    days = ["journée", "Mois", "Feu", "eau", "bois", "Argent", "sol"]
    num_days = len(days)
    adviser_name = ["Peut", "Ichihana", "Nino", "Sanku", "Yotsuba"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)
    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]
    # Creates the model.
    model = cp_model.CpModel()

    # Creates shift variables.
    # shifts[(n, d, s)]: adviser 'n' works shift 's' on day 'd'.
    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

    # Each shift is assigned to exactly one adviser in .
    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)

    # Each adviser works at most one shift per day.
    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)

    # min_shifts_assigned is the largest integer such that every adviser can be
    # assigned at least that number of shifts.
    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)

    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))
    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    solver.Solve(model)
    for d in all_days:
        print(days[d] + "journée:")
        for s in all_shifts:
            for n in all_advisers:
                if solver.Value(shifts[(n, d, s)]) == 1:
                    if shift_requests[n][d][s] == 1:
                        print('Adviser', adviser_name[n], 'works shift', s, '(requested).')
                    else:
                        print('Adviser', adviser_name[n], 'works shift', s, '(not requested).')
        print()

    # Statistics.
    print()
    print('Statistics')
    print('  - Number of shift requests met = %i' % solver.ObjectiveValue(), '(out of', num_advisers * min_shifts_per_adviser, ')')
    print('  - wall time       : %f s' % solver.WallTime())


if __name__ == '__main__':
    main()

Résultat de sortie:

dimanche:
Conseiller Yotsuba travaille quart 0(not requested).
Le conseiller Nino travaille le quart de travail 1(requested).
Le conseiller Sanku travaille le quart de travail 2(requested).

Lundi:
Conseiller Ichihana travaille quart de travail 0(not requested).
Le conseiller Nino travaille le quart de travail 1(requested).
Le conseiller Yotsuba travaille en équipe 2(requested).

Mardi:
Le conseiller Sanku travaille quart de travail 0(requested).
Le conseiller Ichihana travaille le quart de travail 1(requested).
Le conseiller Yotsuba travaille en équipe 2(not requested).

Mercredi:
Le conseiller Nino travaille quart de travail 0(requested).
Le conseiller Ichihana travaille le quart de travail 1(requested).
Le conseiller May travaille le quart 2(not requested).

Jeudi:
Conseiller Yotsuba travaille quart 0(requested).
Le conseiller Sanku travaille le quart de travail 1(not requested).
Le conseiller May travaille le quart 2(requested).

Vendredi:
Le conseiller Sanku travaille quart de travail 0(requested).
Le conseiller May travaille le quart 1(requested).
Le conseiller Ichihana travaille en équipe 2(not requested).

samedi:
Le conseiller Nino travaille quart de travail 0(not requested).
Le conseiller Yotsuba travaille le quart de travail 1(not requested).
Le conseiller May travaille le quart 2(requested).


Statistics
  - Number of shift requests met = 13 (out of 20 )
  - wall time       : 0.007237 s

Nous avons pu produire la solution qui répondait le plus aux souhaits de quart de travail du conseiller.

Enjoy!

[PYTHON] Remplissez 5 équipes égales