Das behandelte Problem der Diplomarbeit ist es, Schichtpläne, welche eine hohe Flexibilität bzgl. der zu berücksichtigenden Parameter aufweisen, zu erstellen. Dies geschieht am Beispiel von Schichtplänen für Ärzte. Für die Lösung werden sowohl ein gemischt-ganzzahliges Programm (MIP) als auch ein dynamisches Programm (DP) angewandt.
Das Problem der Schichtplangenerierung von Ärzten wird in Brunner et al. (2010)1
anhand eines Branch & Price gelöst. Es ist jedoch dort nur möglich, Lösungen für einfache Probleminstanzen zu erzeugen, da das Subproblem des Spaltengenerierungsverfahrens eine zu hohe Lösungszeit für komplexere Instanzen aufweist. Ziel der Diplomarbeit ist daher gewesen, das Subproblem geeignet zu reformulieren und darauf aufbauend ein
zeit-efizientes Lösungsverfahren zu implementieren.
Die Diplomarbeit gliedert sich in acht Kapitel.
Häufig gestellte Fragen
What is the goal of the document presented?
The document aims to explore efficient methods for generating staff schedules in service industries, particularly within healthcare, where resource optimization is crucial due to cost pressures and fluctuating demand.
What problem is the document trying to solve?
The document addresses the challenge of creating personnel deployment plans, specifically for physicians in service industries, to optimize resource utilization while adhering to constraints like labor agreements and employee preferences. Current approaches, such as those relying on mixed-integer programming, may become inefficient with more complex problem instances.
What methods does the document investigate?
The study investigates two primary methods: reformulating the scheduling problem as a Resource Constrained Shortest Path problem (RCSP) solved using both a Mixed Integer Program (MIP) and Dynamic Programming (DP).
What is Brunner et al. (2010) reference in the document?
Brunner et al. (2010) is a reference to a previous work that uses a column generation approach with a mixed-integer programming subproblem for staff scheduling, particularly relevant for generating physician schedules in service organizations. The current document's goal is to reformulate and solve the subproblem more efficiently.
What kind of real-world constraints are considered by the model?
The models accommodate real-world constraints, including minimum and maximum working hours, break times, the inclusion of on-call shifts ("Dienst"), overtime considerations, and preferences concerning the start times of work shifts.
What parameters are varied in the performance analysis, and why?
The study varies several parameters during the run-time analysis to understand how they affect the performance of the DP solution procedure. These parameters include the frequency of efficiency checks in the Dynamic Program, ORDER rules, and parameters relating to shift constraints. The variations aim to identify efficient configurations for solving scheduling problems of various complexities.
What does the term "Dichte der Deltas" refer to?
The "Dichte der Deltas" (Density of Deltas) refers to the density of the Dual variable with (Delta dem ab) and D (Delta Dab), which represent the density between the relationship between the Dual variables in question.
Why is preprocessing used in the model?
Preprocessing techniques are applied to reduce the complexity of the problem. Before the DP model is deployed, the variables are constrained which narrows the solution space, and enables more efficient computation for the solution.
What are the key components of the Label Setting Algorithm described?
The key components of the Label Setting Algorithm are a description of the parameters (i.e resources), defining the algorithm, and defining how dominance is used to limit labels.
What are the conditions under which this Schichtplanung provides the optimal solution?
A Schichtplan will provide an optimal solution if: (1) No work shift extends beyond a week, (2) a shifts can be repositioned so that they occur within only a single week, or (3) the planning period is divisible into equal chunks.
What are the key takeaways from the document?
Dynamic programming appears to present significant speed improvements over other approaches and is an excellent approach when you do not have the full scheduling information all-at-once. While this review is on a specific scheduling example, the general approach could be applied to numerous additional cases.
- Citation du texte
- Jan Mathias Köhler (Auteur), 2010, Generierung von Personaleinsatzplänen in Dienstleistungsunternehmen: Reformulierung von Entscheidungsproblemen und deren Lösung, Munich, GRIN Verlag, https://www.grin.com/document/184852