Idee/Ansatz für Termin-Buchungssystem gesucht.

[Elya]

Hallo Forum,
wir konzipieren gerade eine Buchungsseite (PHP/MySQL) für eine Dienstleistung (DL). Diese soll über einen Zeitraum von 2 Wochen an einigen wenigen Orten durchgeführt werden.

Der Kunde bucht einen Termin und soll direkt sehen, ob dieser frei ist. ABER! Folgende Problematik.

• Der Kunde gibt nicht einen bestimmten Termin an, sondern einen Zeitraum von X Uhr - bis Y Uhr, in dem die DL durchgeführt werden kann, wobei zwischen den Zeiten ein Minimum von n Stunden liegen muß
• Der Anbieter braucht im Schnitt Z Minuten für die Arbeit.

Dies soll eine gewisse Flexibilität für den Anbieter der DL gewährleisten (er kann schieben, wenn der Kunde ihm mehr als n Stunden gibt), kompliziert aber die Programmierung. Ich bekomme da irgendwie keinen Ansatz hin.

Da es nur rund 400 Termine insgesamt sind, noch dazu an unterschiedlichen Orten, können wir durchaus jeden Termin mit id in die DB schreiben. Aber wie kann ich prüfen, ob für den angegebenen Zeitraum noch ein Termin "oben drauf" zu packen ist? Ich hatte schon einmal gedacht, daß man die Termin-Tabelle von hinten (Y = Endzeitpunkt) füllt, komme da aber nicht weiter.

Ich brauche keinen Code, nur einen Ansatz für meinen Knoten im Hirn ;) Danke für's Mitdenken.

Schöne Grüße aus Köln-Ehrenfeld,

Elya

[lulu]

Huhu Elya

kurze Nachfrage, ob ich das richtig verstanden habe:

Die Kunden geben einen Zeitrahmen vor in welchem die Dienstleistung (DL) erbracht werden kann/ soll.

Jetzt soll

1. die optimale Ausnutzung des Zeitbudgets des Diensleisters ermittelt werden.

2. geprüft werden, ob durch geschicktes "Schieben" der Termine Platz für weitere Kundentermine geschaffen werden kann.

3. bzw. geprüft werden ob der gewünschte Termin verfügbar ist (oder, durch geschicktes Anordnen, verfügbar gemacht werden kann)

In folgender Skizze steht ein "X" für eine Zeiteinheit (ZE).
Wenn Beispielsweise die DL 3 ZE beansprucht gibt es
mehrere Lösungsmöglichkeiten um diese aufzuteilen.

Zeit___:abcdefghijklmnopqr
Kunde_1:XXXXXXXX__________
Kunde_2:_____XXXXXX_______
Kunde_3:________XXXXXX____
-------:
Dienst.:111__222___333____
Dienst.:_____111222333____
[...]
etc.

wenn jetzt ein weiterer Kunde den Termin "ijk" haben möchte wäre
das bei der ersten Anordnung möglich.

Ist das so richtig dargestellt?

Scheint jedenfalls ein interessantes Problem zu sein, viel Spass dabei ;-)

Viele Grüße

lulu

[Elya]

Huhu Elya

huhu lulu :)

1. die optimale Ausnutzung des Zeitbudgets des Diensleisters ermittelt werden.

2. geprüft werden, ob durch geschicktes "Schieben" der Termine Platz für weitere Kundentermine geschaffen werden kann.

3. bzw. geprüft werden ob der gewünschte Termin verfügbar ist (oder, durch geschicktes Anordnen, verfügbar gemacht werden kann)

In folgender Skizze steht ein "X" für eine Zeiteinheit (ZE).
Wenn Beispielsweise die DL 3 ZE beansprucht gibt es
mehrere Lösungsmöglichkeiten um diese aufzuteilen.

Zeit___:abcdefghijklmnopqr
Kunde_1:XXXXXXXX__________
Kunde_2:_____XXXXXX_______
Kunde_3:________XXXXXX____
-------:
Dienst.:111__222___333____
Dienst.:_____111222333____
[...]
etc.

Super, schöner ist es kaum auszudrücken. Muß nur noch in php übersetzt werden :-|

Scheint jedenfalls ein interessantes Problem zu sein, viel Spass dabei ;-)

Auf alle Fälle, das wird es, danke!

Schöne Grüße aus Köln-Ehrenfeld,

Elya

[Michael Schröpl]

Hi Elya,

Dies soll eine gewisse Flexibilität für den Anbieter der DL gewährleisten (er kann schieben, wenn der Kunde ihm mehr als n Stunden gibt), kompliziert aber die Programmierung.

in der Tat. Dein Szenario ist äquivalent zu einer verschäften Form des Knapsack-Problems, und das allein ist immerhin schon NP-vollständig ...

Aber wie kann ich prüfen, ob für den angegebenen Zeitraum noch ein Termin "oben drauf" zu packen ist?

Indem Du es ausprobierst. Und ich fürchte, das bedeutet, Permutationen zu generieren und den Rekursionsbaum überall dort abzuschneiden, wo Du eine Kollision findest ("Suche in der Tiefe").
Je effizienter Du diesen Baum beschneidest, desto schneller wird Dein Algorithmus werden; zunächst mußt Du den Baum (über alle möglichen Reihenfolgen Deiner Ereignisse) aber überhaupt mal generieren, und das ist m. E. schon das Hauptproblem.

Ich hatte schon einmal gedacht, daß man die Termin-Tabelle von hinten (Y = Endzeitpunkt) füllt, komme da aber nicht weiter.

Gäbe es einen linearen Algorithmus für das allgemeine Problem, dann wäre dieser ungefähr einen Nobelpreis wert. ;-)

Ich rate Dir davon ab, das Probieren innerhalb des CGI-Timeout zu realisieren ... mach es lieber im Hintergrund und generiere eine Bestätigungs- oder Ablehnungs-E-Mail an den Besucher.

Du kannst aufgrund Deines Datenbestandes immerhin feststellen, ob Dein Problem leicht ist oder schwer, indem Du einen trivialen Versuch unternimmst (z. B.: Sortiere alle Ereignisse nach ihrem Intervall-Mittelpunkt und fülle sie sequentiell in Dein Zeitraster - bei dünn besetzten Ereignismengen wird das oft funktionieren). In diesem Falle kannst Du dem Besucher die Annahme sofort bestätigen.
Falls dies jedoch scheitert, müßte ein intelligenterer Ansatz verwendet werden, und der kann dann dauern ...

Viele Grüße
      Michael

[Elya]

hoppla, Michael,

in der Tat. Dein Szenario ist äquivalent zu einer verschäften Form des Knapsack-Problems, und das allein ist immerhin schon NP-vollständig ...

Gäbe es einen linearen Algorithmus für das allgemeine Problem, dann wäre dieser ungefähr einen Nobelpreis wert. ;-)

Mir war klar, daß es komplex wird, aber soooo... meine Kollegin meinte schon, wir sollten Deinen Satz so in unser Angebot schreiben.

»Du kannst aufgrund Deines Datenbestandes immerhin feststellen, ob Dein Problem leicht ist oder schwer, indem Du einen trivialen Versuch unternimmst

Es handelt sich glücklicherweise um einen relativ kleinen Datenbestand. Also 1 Tag - ca. 10-12 Zeitintervalle = Termine pro Ort. Das müßten wir mal durchprobieren.

Vielen Dank für's Mitdenken!

Schöne Grüße aus Köln-Ehrenfeld,

Elya