Verteilungs- (Entscheidungs-) Algorithmus

[MarcelF6]

Guten Morgen miteinander

Ich beschäftige mich gerade mit einem relativ komplizierten Problem: Ich habe eine Menge von Personen gegeben, die in einer Datei ihre erste und ihre zweite Präferenz angegeben haben, wann sie am liebsten arbeiten wollen. Ich als fiktiver Arbeitgeber speichere alle Wochentage und die Anzahl der an diesem Tag nötigen Arbeitskräfte. Ich sollte die Tage so verteilen, dass so viele wie möglich zufrieden sind. (normalerweise werden weniger Tage angeboten als mögliche Arbeitskräfte vorhanden sind).

Ich habe bereits eine Funktion geschrieben, die pro Person und Präferenz je 2 Punkte gibt, falls es sich dabei um die erste Präferenz handelt, 1 Punkt falls es sich um die 2.Präferenz handelt und 0 Punkt für alle nicht gewählten Tage.
Ich erhalte dann also beispielsweise sowas als "Zwischenergebnis":

Code: Alles auswählen

{'samstag': 5, 'sonntag': 7, 'montag': 8, 'donnerstag': 7}

Nun frage ich mich: Wie kann eine mögliche Implementation aussehen, wenn ich zB am Sonntag 2 Leute, am Montag 1, am Dienstag 1 und am Donnerstag 2 Leute brauche? (Achtung: das "Zwischenergebnis" oben beinhaltet die Summe der Gewichte, nicht der Anzahl Personen, die dann arbeiten wollen) Dies sollte dann irgendwie mit der jeweiligen Präferenz der Personen verglichen werden und eben, es sollte geschaut werden, dass die Personen "glücklich" sind .

Zwischenzeitlich habe ich auch noch das probiert:

Code: Alles auswählen

>>> import itertools
>>> for schedule in itertools.permutations('Bob Sue Jim Tony Alice Zane Tim'.split()):
...  print(schedule)
... 
('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Zane', 'Tim')
('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Tim', 'Zane')
('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Alice', 'Tim')
('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Tim', 'Alice')
('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Alice', 'Zane')
('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Zane', 'Alice')
('Bob', 'Sue', 'Jim', 'Alice', 'Tony', 'Zane', 'Tim')

Die erste Zeile würde dann heissen: "Bob arbeitet am Sonntag, Tim am Samstag". Wenn Bob's erste Präferenz der Sonntag und Tim's zweite Präferenz der Samstag war (und wir sonst keine Präferenz einer anderen Person getroffen hätten), ergäbe diese Zeile eine Summe der Gewichte von 3 Punkten.
ABER: So kanns nicht funktionieren, weil ich je nach dem auch mehrere Leute pro Tag "brauche". Und mit dem obigen System ist jeweils nur eine Person pro Tag möglich.

Ja, wie ihr seht, wäre ich sehr dankbar für brauchbare Inputs
Evtl. habe ich mich auch völlig verfahren mit diesem Lösungsweg - wenns einen einfacheren / anderen Weg gibt, der aber ganz unterschiedlich zu dem hier ist: egal, ich bin einfach an einer sauberen, brauchbaren Lösung interessiert
Vielen Dank.

[BlackJack]

@MarcelF6: Da fehlen noch Randbedingungen. Dürfen Personen nur auf Tage gesetzt werden, die sie präferieren, oder sind die 0er-Tage im Notfall auch setzbar? (Dann würde ich die wahrscheinlich negativ gewichten, weil 0 eher neutral ist.)

Und darf eine Person mehrfach eingesetzt werden? Dann müsste man noch Gewichtungen dafür finden, dass jemand mehr als einmal eingesetzt wird.

Ansonsten kannst Du ja einfach mal alles mehr oder weniger Brute-Force durch probieren. Also den Montag auffüllen, dann mit den restlichen Leuten den Dienstag und so weiter. Davon alle Kombinationen, wobei man mit „branch & bound” natürlich die Zweige im Suchbaum weglassen kann, wo die Teillösung schon schlechter als die bisherige beste Lösung war.

[MarcelF6]

Hallo und danke für deine Antwort!
Du hast Recht, ich habe oben einige Sachen vergessen.
Also: Jede Person gibt 2 Präferenzen an. Jede Person bekommt aber nur je 1 Tag. Das heisst: Wenn eine Person am Dienstag und Mittwoch arbeiten will, ich dann aber keine Plätze zur Verfügung stelle, so bekommt er halt nichts.
Hm...was meinst du mit "Brute-Force"? Beim Sonntag (Montag) beginnen und dann alle Plätze mit den Präferenzen abgleichen und auffüllen wollte ich auch...allerdings ist das schneller gesagt, als gemacht ...eine Implementation habe ich eben leider noch nicht hingekriegt.
Danke für jede Hilfe

[pillmuncher]

@MarcelF6: Falls ich dich richtig verstehe, gibt es sieben Personen, die jeweils einen Arbeitseinsatz pro Woche haben, so dass für Tage, an denen mehrere Personen gemeinsam arbeiten, es entsprechend viele Tage gibt, an denen keiner arbeitet?

Eine weitere Frage wäre, ob die Personen einfach irgendwelche Tage präferieren sollen, oder nur solche, an denen auch gearbeitet wird?

[BlackJack]

@MarcelF6: Mit Brute-Force meine ich das was man darunter üblicherweise in der Informatik versteht: https://de.wikipedia.org/wiki/Brute-Force-Methode

[MarcelF6]

@pillmuncher: Es sind 7 Personen (können aber auch mehr/weniger sein). Aber die Anzahl Personen hat nichts mit der Anzahl Wochentage zu tun. So könnten auch viel mehr Arbeitsplätze angeboten werden als es Personen hat
Welche Tage die Personen präferiere wird bei dem Programm übergeben. Das kann ganz unterschiedlich sein...
Hmm..ist das Problem wirklich so tricky? :S

[pillmuncher]

@MarcelF6: Nein, ganz so tricky ist es nicht. Aber man muss sehr genau sagen was man möchte, weil man ja sehr genau programmieren muss, was geschehen soll. Obwohl ich mir manchmal eine Programmiersprache wünsche der man sagen kann "Mach ungefähr das."

[EyDu]

Obwohl ich mir manchmal eine Programmiersprache wünsche der man sagen kann "Mach ungefähr das."

Du meinst Problog? Da sagt man zwar genau was man haben will, aber gerade bei kombinatorischen Problemen mit Nebenbedingungen ist es doch ideal. Das Problem hier sollte sich doch wirklich schnell in Prolog darstellen lassen.

[BlackJack]

@EyDu: Nein, das war nicht gemeint, denn auch in Prolog musst Du präzise formulieren was Du haben möchtest. Und nur das bekommst Du dann auch. Einen „gibt mir was meine und nicht was ich sage”-Modus hat auch Prolog nicht.

[EyDu]

Ich zitiere mich mal selber:

Da sagt man zwar genau was man haben will...

Prinzipiell ist es auch nicht besonder schwer etwas zu programmieren, so dass man eine "in etwa" Lösung bekommt. Das Problem ist ja eher, dass man gar nicht genau sagen kann was "in etwas" bedeutet. Bzw. das in konkrete Werte (Gewichte, Wahrscheinlichkeiten, Likelihood) zu packen, welche ggf. noch von einander abhängen. Wenn nicht einmal der Anwender mit Hintergrundinformation dazu in der Lage ist, dann wird das für ein Stück Software ohne Information "schwierig".

[pillmuncher]

An Prolog hatte ich auch zuerst gedacht. Mach ich vielleicht morgen. Hier ist eine Python-Lösung:

Code: Alles auswählen

import pprint
from random import randint, sample
from itertools import permutations, islice, imap, cycle
from operator import itemgetter


first = itemgetter(0)


def compose(f, g):
    return lambda x: g(f(x))


def take(n, iterable):
    "Return first n items of the iterable as a list"
    return list(islice(iterable, n))


def generate_team_sizes(m, n):
    it = iter([1] * n)
    for i in xrange(n - 1):
        yield sum(take(randint(0, m), it))
    yield sum(it)


max_team_size = 3

workers = 'Bob Sue Jim Tony Alice Zane Tim'.split()

days = 'mon tue wed thu fri sat sun'.split()

by_day = compose(first, {day: i for i, day in enumerate(days)}.__getitem__)

team_size_per_day = zip(sample(days, len(days)),
                        generate_team_sizes(max_team_size, len(days)))
team_size_per_day.sort(key=by_day)

preferences = {}
for worker in workers:
    day_a, day_b = sample(days, 2)
    preferences[day_a, worker] = 2
    preferences[day_b, worker] = 1


tmp1 = ([(day, take(size, each)) for day, size in team_size_per_day]
        for each in imap(cycle, permutations(workers)))

tmp2 = ([[day, frozenset((w, preferences.get((day, w), 0)) for w in team)]
            for day, team in each]
        for each in tmp1)

tmp3 = (tuple((day, wps, sum(pref for w, pref in wps)) for day, wps in each)
        for each in tmp2)


def by_weight_desc(rows):
    prefs = [pref for day, wps, prefsum in rows for w, pref in wps]
    return prefs.count(0) * 2 - sum(prefs)


result = sorted(set(tmp3), key=by_weight_desc)
pprint.pprint(team_size_per_day)
print
pprint.pprint(sorted(preferences.iteritems(), key=compose(first, by_day)))
print
for solution in result:
    if all(pref for day, wps, prefsum in solution for w, pref in wps):
        print 'A solution for all preferred days was found:'
        print
        pprint.pprint(solution)
        break
else:
    if result:
        solution = result[0]
        print 'A solution for all preferred days could not be found.'
        print 'Best match is:'
        print
        pprint.pprint(solution)
    else:
        print 'No solution could be found.'

Nicht sehr hübsch aber scheint zu funktionieren.

[MarcelF6]

Wow!
Chapeau, echt eindrücklich!!
Dürfte ich noch ein paar Fragen zum Code stellen?
1.) Was ist max_demand?
2.) Du gewichtest die erste Präferenz mit 1, die zweite mit 2, oder?
Besten Dank =)

[pillmuncher]

Ich hab nochmal versucht es übersichtlicher zu machen und die Benennungen zu verbessern. Ich hoffe, dass damit klarer wird, wie es funktioniert.

1.) Was ist max_demand?
2.) Du gewichtest die erste Präferenz mit 1, die zweite mit 2, oder?

1.) Hab's umbenannt zu max_team_size, das ist die maximale Anzahl von Arbeitern pro Einsatzteam.
2.) Die Reihenfolge der Tage (also liebster Tag zuerst, dann zweit-liebster Tag - oder umgekehrt) hat für das Programm keine Bedeutung, nur die Gewichtung der Tage ist von Belang.

[MarcelF6]

Super, besten Dank dir, pillmuncher, und an all jene, die mir ebenfalls geholfen haben

[pillmuncher]

Hier nochmal mit besseren Namen, besserem Algorithmus und besserer Bewertungsfunktion:

Code: Alles auswählen

from __future__ import division
from random import randint, sample
from itertools import permutations, product, starmap
from operator import itemgetter
from collections import defaultdict
import pprint


first = itemgetter(0)


def compose(f, g):
    return lambda x: g(f(x))


def randints_upto_total(min_int, max_int, total):
    for _ in xrange(total - 1):
        n = randint(min_int, min(max_int, total))
        yield n
        total -= n
    yield total


def variance(numbers):
    numbers = iter(numbers)
    m = next(numbers)
    s = 0
    i = 2
    for i, x in enumerate(numbers, start=2):
        # See Knuth TAOCP vol 2, 3rd edition, page 232
        n = m
        m += (x - m) / i
        s += (x - m) * (x - n)
    return s / (i - 1)


workers = 'Bob Sue Jim Tony Alice Zane Tim'.split()
days = 'mon tue wed thu fri sat sun'.split()

by_day = compose(first, {day: i for i, day in enumerate(days)}.__getitem__)

team_size_per_shift = zip(sample(days, len(days)),
                          randints_upto_total(0, 3, len(days)))
team_size_per_shift.sort(key=by_day)

preferences = {}
for worker in workers:
    day_a, day_b = sample(days, 2)
    preferences[day_a, worker] = 2
    preferences[day_b, worker] = 1


def by_weight(shifts):
    rank = 0
    zeros = 0
    attendance = defaultdict(int)
    for day, team in shifts:
        for worker, preference in team:
            attendance[worker] += 1
            if preference:
                rank += preference
            else:
                zeros += 1
    return -variance(attendance.itervalues()), -zeros, rank


def shift(day, team_size):
    for team in permutations(workers, team_size):
        yield day, frozenset((worker, preferences.get((day, worker), 0))
                             for worker in team)


pprint.pprint(team_size_per_shift)
print
pprint.pprint(sorted(preferences.iteritems(), key=compose(first, by_day)))
print
result = max(set(product(*starmap(shift, team_size_per_shift))), key=by_weight)
if result:
    if all(preference for day, team in result
                        for worker, preference in team):
        print 'A solution for all preferred days was found:'
    else:
        print 'A solution for all preferred days could not be found.'
        print 'Best match is:'
    print
    pprint.pprint(result)
else:
    print 'No solution could be found.'