2024-05-06

Author

Witek ten Hove

OBP:

Afspraken:

  • We gaan verder kijken naar Simulation Optimization methodes

  • Wellicht icm Gradient Boosting, mogelijk ML-toepassingen

  • Start met artikel van Homem-de-Mello, Kong, and Godoy-Barba (2022)

    • Onderzoeken wat de stand van zaken is mbt SO en Appointment Scheduling
    • Waarom is de het probleem dat besproken wordt in Homem-de-Mello, Kong, and Godoy-Barba (2022) non-convex?
    • Aanmaken van Overleaf document voor samenwerking.
    • Literatuurnotities maken.

Code examples

This code simulates the cost of a clinic’s schedule based on different cost factors related to patient waiting time, physician idle time, and clinic overtime. The scheduling process aims to minimize these costs by analyzing how different appointment times affect them.

Cost Parameters

We define three cost parameters:

  • c_w: The cost of waiting time (1 per time unit).
  • c_I: The cost of physician idle time (10 per time unit).
  • c_o: The cost of overtime beyond regular clinic hours (15 per time unit).

Service Time Distribution

Service time, or the time taken to treat a patient, is simulated with a uniform distribution between 2.5 and 7.5 time units (service_time_min and service_time_max).

Clinic End Time

The clinic ends its daily operations after 12 time units (T), beyond which overtime charges apply.

Simulation Function

The simulate_schedule() function calculates the total cost for a given appointment schedule.

  1. Initialization:
    • Initializes total cost variables to zero for waiting, idle, and overtime costs.
    • Sets the starting current_time to zero.
  2. Cost Calculation:
    • For each appointment in the schedule:
      • If the physician is idle (i.e., the appointment is scheduled after current_time), idle costs are added.
      • The patient’s service time is drawn randomly between the specified minimum and maximum bounds.
      • If the patient waited before seeing the physician, waiting costs are calculated.
      • current_time is updated based on service time.
  3. Overtime Calculation:
    • If the last appointment exceeds the clinic’s end time, overtime costs are calculated.
  4. Total Cost Calculation:
    • The function returns the sum of waiting, idle, and overtime costs.

Example Schedule

The provided schedule = [0, 4, 8] simulates three patient appointments at times 0, 4, and 8 time units. By setting the random seed for reproducibility (random.seed(42)), the function is executed to calculate the total cost for this specific schedule.

import random
import plotly.graph_objs as go
import csv
import random

# Cost parameters
c_w = 1  # waiting cost
c_I = 10  # idle cost
c_o = 15  # overtime cost

# Service time distribution
service_time_min = 2.5
service_time_max = 7.5

# Clinic end time
T = 12

def simulate_schedule(schedule):
    total_waiting_cost = 0
    total_idle_cost = 0
    total_overtime_cost = 0

    current_time = 0
    for i, appointment in enumerate(schedule):
        # Ensure that the current appointment does not start before the current time
        if current_time < appointment:
            idle_time = appointment - current_time
            total_idle_cost += idle_time * c_I
            current_time = appointment
        
        # Calculate waiting time cost if the patient arrives before current_time
        waiting_time = current_time - appointment
        if waiting_time > 0:
            total_waiting_cost += waiting_time * c_w
        
        # Determine the service time for the current patient
        service_time = random.uniform(service_time_min, service_time_max)
        
        # Update the current time after servicing the current patient
        current_time += service_time
    
    # Calculate overtime cost if the last appointment exceeds the clinic end time
    overtime = max(0, current_time - T)
    total_overtime_cost = overtime * c_o
    
    # Calculate the total cost
    total_cost = total_waiting_cost + total_idle_cost + total_overtime_cost
    return total_cost

# Example schedule
schedule = [0, 4, 8]  # assuming three patients scheduled at these times

# Run the simulation and print the objective value (total cost)
random.seed(42)  # set seed for reproducibility
total_cost = simulate_schedule(schedule)
print(f"Total cost of the given schedule is: {total_cost}")
Total cost of the given schedule is: 4.979337164417394

The updated simulation function below, named simulate_schedule_w_no_shows(), extends the simulation’s complexity and realism. Here’s a breakdown of the differences and how the new elements work:

Main Differences

  1. No-Show Consideration:
    • The updated code introduces the concept of no-shows, where patients may not appear for their scheduled appointment. This is a crucial addition for modeling more realistic healthcare environments where no-shows can significantly impact operational costs and scheduling efficiency.
  2. No-Show Probability Function:
    • A function no_show_probability(appointment, T) is presumed to exist, which calculates the likelihood of a patient not showing up based on the appointment time and perhaps other factors like clinic closing time T. This function is not shown in the snippet but is essential for determining if a patient attends their appointment.
  3. Random Attendance Check:
    • For each appointment, a random check against the no-show probability determines whether the patient shows up (shows_up). This introduces randomness into the simulation, reflecting the uncertain nature of patient attendance.
  4. Handling No-Shows in the Simulation:
    • If a patient does not show up, the function now accounts for the idle time until the next appointment or until the same appointment time without the need to service the patient, updating current_time appropriately. This differs from the original simulation, where every patient was assumed to show up, and service time was always added to current_time.

Updated Functionality in the Code

  • Idle Time Calculation:
    • In both scenarios (whether the patient shows up or not), if current_time is less than the appointment time, idle time is calculated. This ensures the clinic’s resource utilization is adjusted for gaps between actual service times and scheduled appointment times.
  • Service Time and Waiting Time:
    • These are now calculated only if the patient shows up. If the patient arrives and the current_time is already past their scheduled time, the waiting time cost is added, which penalizes delays in service relative to the appointment time.
  • Total Cost Calculation:
    • The formula for total cost remains the sum of waiting, idle, and overtime costs. However, these costs could now be affected differently since some appointments might result in no service being rendered due to no-shows.

Example and Output

The example uses the original simulate_schedule(schedule) instead of the updated simulate_schedule_w_no_shows(schedule), which could be a typographical error in the example. To test the new functionality, one should replace simulate_schedule(schedule) with simulate_schedule_w_no_shows(schedule) to incorporate the no-show logic.

# Generate random schedules and their objective values
num_schedules = 10000

schedules = []

schedules_results = []

# Create random schedules
for _ in range(num_schedules):
    # Generate a random schedule with three patients
    x_1 = random.uniform(0, T)
    x_2 = random.uniform(x_1, T)
    schedule = [0, x_1, x_2]
    schedules.append(schedule)
    
# For each schedule, simulate a number of times and calculate the average total cost
for schedule in schedules:
    i = 1000
    schedule_costs = []
    while i > 0:
      total_cost = simulate_schedule(schedule)
      schedule_costs.append(total_cost)
      i -= 1
    avg_cost = sum(schedule_costs) / len(schedule_costs)
    schedules_results.append((schedule[1], schedule[2], avg_cost))

# Extract data for plotting
x_1_values, x_2_values, costs = zip(*schedules_results)

# Create a 3D scatter plot using Plotly
scatter = go.Scatter3d(
    x=x_1_values,
    y=x_2_values,
    z=costs,
    mode='markers',
    marker=dict(size=2, color=costs, colorscale='Viridis', opacity=0.8)
)

layout = go.Layout(
    title='3D Plot of x_1, x_2, and Objective Values',
    scene=dict(
        xaxis_title='x_1',
        yaxis_title='x_2',
        zaxis_title='Objective Value'
    )
)

fig = go.Figure(data=[scatter], layout=layout)
fig.show()
# Cost parameters
c_w = 1  # waiting cost
c_I = 10  # idle cost
c_o = 15  # overtime cost

# Service time distribution
service_time_min = 2.5
service_time_max = 7.5

# Clinic end time
T = 12

# Define a no-show probability function based on time of day
def no_show_probability(time_of_day, T):
    # Linear function as an example: Probability increases with time
    return 0.2 + 0.6 * (time_of_day / T)  # example function

# Update the simulation function to include no-show consideration
def simulate_schedule_w_no_shows(schedule):
    total_waiting_cost = 0
    total_idle_cost = 0
    total_overtime_cost = 0
    
    current_time = 0
    for appointment in schedule:
        # Calculate the no-show probability for this appointment time
        no_show_prob = no_show_probability(appointment, T)
        shows_up = random.random() >= no_show_prob
        
        if shows_up:
            # Patient shows up, update the idle time and service time
            if current_time < appointment:
                idle_time = appointment - current_time
                total_idle_cost += idle_time * c_I
                current_time = appointment
            
            # Calculate waiting time cost if the patient arrives before current_time
            waiting_time = current_time - appointment
            if waiting_time > 0:
                total_waiting_cost += waiting_time * c_w
            
            # Determine the service time for the current patient
            service_time = random.uniform(service_time_min, service_time_max)
            
            # Determine the service time for the current patient
            current_time += service_time
            
        else:
            # Patient doesn't show up, count the idle time from the last service to the appointment time
            if current_time < appointment:
                idle_time = appointment - current_time
                total_idle_cost += idle_time * c_I
                current_time = appointment
    
    overtime = max(0, current_time - T)
    total_overtime_cost = overtime * c_o
    
    total_cost = total_waiting_cost + total_idle_cost + total_overtime_cost
    return total_cost


# Example schedule
schedule = [0, 4, 8]  # assuming three patients scheduled at these times

# Run the simulation and print the objective value (total cost)
random.seed(42)  # set seed for reproducibility
total_cost = simulate_schedule_w_no_shows(schedule)
print(f"Total cost of the given schedule is: {total_cost}")
Total cost of the given schedule is: 53.749462238866656
# Generate random schedules and their objective values (with nop-shows)
num_schedules = 10000

schedules = []

schedules_results = []

# Create random schedules
for _ in range(num_schedules):
    # Generate a random schedule with three patients
    x_1 = random.uniform(0, T)
    x_2 = random.uniform(x_1, T)
    schedule = [0, x_1, x_2]
    schedules.append(schedule)
    
# For each schedule, simulate a number of times and calculate the average total cost
for schedule in schedules:
    i = 1000
    schedule_costs = []
    while i > 0:
      total_cost = simulate_schedule_w_no_shows(schedule)
      schedule_costs.append(total_cost)
      i -= 1
    avg_cost = sum(schedule_costs) / len(schedule_costs)
    schedules_results.append((schedule[1], schedule[2], avg_cost))

# Extract data for plotting
x_1_values, x_2_values, costs = zip(*schedules_results)

# Create a 3D scatter plot using Plotly
scatter = go.Scatter3d(
    x=x_1_values,
    y=x_2_values,
    z=costs,
    mode='markers',
    marker=dict(size=2, color=costs, colorscale='Viridis', opacity=0.8)
)

layout = go.Layout(
    title='3D Plot of x_1, x_2, and Objective Values (with No-Shows)',
    scene=dict(
        xaxis_title='x_1',
        yaxis_title='x_2',
        zaxis_title='Objective Value'
    )
)

fig = go.Figure(data=[scatter], layout=layout)
fig.show()

References

Homem-de-Mello, Tito, Qingxia Kong, and Rodrigo Godoy-Barba. 2022. “A Simulation Optimization Approach for the Appointment Scheduling Problem with Decision-Dependent Uncertainties.” INFORMS Journal on Computing 34 (5): 2845–65.