mansurarief/data_driven_scheduling
0
1import numpy as np2import pandas as pd3import pyomo.environ as pyo4import plotly.graph_objects as go5import plotly.express as px6import gradio as gr7import io8import os9from datetime import datetime, timedelta10 11"""12Shift Scheduling Problem Mathematical Formulation:13 14Minimize ∑(c_ij * x_ij) for all i in I, j in J15Subject to ∑(x_ij) = 1 for all i in I (each employee gets exactly one shift)16 ∑(x_ij) >= r_j for all j in J (each shift meets minimum staffing requirement)17 x_ij ∈ {0,1} for all i in I, j in J18 19Where:20- I is the set of employees21- J is the set of shifts22- c_ij is the cost of assigning employee i to shift j23- r_j is the minimum staffing requirement for shift j24- x_ij is the decision variable: 1 if employee i is assigned to shift j, 0 otherwise25 26The objective is to minimize the total assignment cost while meeting staffing requirements.27"""28 29def solve_shift_scheduling_model(excel_file):30 # Read data from the uploaded Excel file31 # 'costs' sheet contains the cost matrix for assigning employees to shifts32 costs_df = pd.read_excel(excel_file, sheet_name='costs', index_col=0)33 34 # 'employees' sheet contains information about employees35 employees_df = pd.read_excel(excel_file, sheet_name='employees', index_col=0)36 37 # 'shifts' sheet contains information about shifts38 shifts_df = pd.read_excel(excel_file, sheet_name='shifts', index_col=0)39 40 # 'params' sheet contains general parameters (optional)41 try:42 params = pd.read_excel(excel_file, sheet_name='params').to_dict(orient='list')43 params = {name_: value_ for name_, value_ in zip(params["name"], params["val"])}44 except:45 params = {}46 47 # Initialize the model48 model = pyo.ConcreteModel()49 50 # Define the sets51 model.I = pyo.Set(initialize=employees_df.index.tolist()) # Employees52 model.J = pyo.Set(initialize=shifts_df.index.tolist()) # Shifts53 54 # Define the decision variables55 # x_ij: 1 if employee i is assigned to shift j, 0 otherwise56 model.x = pyo.Var(model.I, model.J, domain=pyo.Binary)57 58 # Define the parameters59 # c_ij: cost of assigning employee i to shift j60 def c_init(model, i, j):61 return costs_df.loc[i, j]62 model.c = pyo.Param(model.I, model.J, initialize=c_init)63 64 # r_j: minimum staff required for shift j65 def r_init(model, j):66 return shifts_df.loc[j, 'min_staff']67 model.r = pyo.Param(model.J, initialize=r_init)68 69 # Define the objective function (minimize total assignment cost)70 def obj_rule(model):71 return sum(model.c[i, j] * model.x[i, j] for i in model.I for j in model.J)72 model.obj = pyo.Objective(rule=obj_rule, sense=pyo.minimize)73 74 # Define the constraints75 # Each employee is assigned to exactly one shift76 def one_shift_per_employee(model, i):77 return sum(model.x[i, j] for j in model.J) == 178 model.one_shift_constraint = pyo.Constraint(model.I, rule=one_shift_per_employee)79 80 # Each shift meets minimum staffing requirements81 def minimum_staff_constraint(model, j):82 return sum(model.x[i, j] for i in model.I) >= model.r[j]83 model.min_staff_constraint = pyo.Constraint(model.J, rule=minimum_staff_constraint)84 85 # Optional: maximum staff per shift constraint (if specified in shifts dataframe)86 if 'max_staff' in shifts_df.columns:87 def max_staff_constraint(model, j):88 return sum(model.x[i, j] for i in model.I) <= shifts_df.loc[j, 'max_staff']89 model.max_staff_constraint = pyo.Constraint(model.J, rule=max_staff_constraint)90 91 # Optional: Employee preferences constraint (if preference matrix is given)92 if 'preferences' in params.get('include', []):93 try:94 # Read preference matrix (1 = preferred, 0 = not preferred)95 prefs_df = pd.read_excel(excel_file, sheet_name='preferences', index_col=0)96 97 # Define minimum preferred shifts parameter98 min_preferred = params.get('min_preferred_pct', 0)99 100 # Add constraint: each employee gets at least min_preferred% of their preferred shifts101 def preference_constraint(model, i):102 preferred_shifts = [j for j in model.J if prefs_df.loc[i, j] == 1]103 if not preferred_shifts: # Skip if employee has no preferences104 return pyo.Constraint.Skip105 return sum(model.x[i, j] for j in preferred_shifts) >= min_preferred106 107 model.preference_constraint = pyo.Constraint(model.I, rule=preference_constraint)108 except:109 pass # If preferences sheet doesn't exist, skip this constraint110 111 # Solve the model using GLPK112 result = None113 solver_error = None114 115 try:116 # Use GLPK as the primary solver117 solver = pyo.SolverFactory('glpk')118 if solver.available():119 result = solver.solve(model, tee=True)120 output_text = "Using solver: GLPK\n\n"121 else:122 raise Exception("GLPK solver is not available")123 except Exception as e:124 solver_error = str(e)125 raise Exception(f"Failed to solve with GLPK: {solver_error}")126 127 # Generate analysis128 output_text = ""129 output_text += f"Status: {result.solver.status}\n"130 output_text += f"Termination condition: {result.solver.termination_condition}\n"131 output_text += f"Optimal total cost: {pyo.value(model.obj):.2f}\n\n"132 133 # Create a dataframe with assignments134 assignments = []135 for i in model.I:136 assigned_shift = None137 for j in model.J:138 if pyo.value(model.x[i, j]) > 0.5:139 assigned_shift = j140 break141 142 if assigned_shift is not None:143 employee_data = {144 'Employee_ID': i,145 'Name': employees_df.loc[i, 'name'] if 'name' in employees_df.columns else i,146 'Assigned_Shift': assigned_shift,147 'Shift_Start': shifts_df.loc[assigned_shift, 'start_time'],148 'Shift_End': shifts_df.loc[assigned_shift, 'end_time'],149 'Assignment_Cost': model.c[i, assigned_shift]150 }151 assignments.append(employee_data)152 153 assignments_df = pd.DataFrame(assignments)154 155 # Summary by shift156 output_text += "Staff Assignments by Shift:\n"157 shift_summary = {}158 for j in model.J:159 assigned_employees = [i for i in model.I if pyo.value(model.x[i, j]) > 0.5]160 shift_summary[j] = {161 'Assigned_Staff': len(assigned_employees),162 'Min_Required': model.r[j],163 'Employees': ', '.join([str(employees_df.loc[i, 'name']) if 'name' in employees_df.columns else str(i) for i in assigned_employees])164 }165 output_text += f" Shift {j}: {len(assigned_employees)} staff assigned (minimum: {model.r[j]})\n"166 output_text += f" Employees: {shift_summary[j]['Employees']}\n"167 168 shift_summary_df = pd.DataFrame(shift_summary).T169 shift_summary_df.index.name = 'Shift'170 shift_summary_df = shift_summary_df.reset_index()171 172 # Create visualization of the schedule173 fig = create_schedule_visualization(assignments_df, shifts_df)174 175 # Save results to Excel176 temp_file_path = "shift_scheduling_results.xlsx"177 with pd.ExcelWriter(temp_file_path) as writer:178 assignments_df.to_excel(writer, sheet_name='Assignments', index=False)179 shift_summary_df.to_excel(writer, sheet_name='Shift_Summary', index=False)180 181 return output_text, fig, temp_file_path182 183def create_schedule_visualization(assignments_df, shifts_df):184 """Create a Plotly visualization showing the shift schedule."""185 # Create a dataframe for visualization186 gantt_data = []187 188 # Create a reference date for visualization (doesn't matter which date)189 base_date = datetime.today().replace(hour=0, minute=0, second=0, microsecond=0)190 191 for _, row in assignments_df.iterrows():192 # Get shift start and end times193 start_hour = int(shifts_df.loc[row['Assigned_Shift'], 'start_time'])194 end_hour = int(shifts_df.loc[row['Assigned_Shift'], 'end_time'])195 196 # Create datetime objects for start and end197 start_time = base_date + timedelta(hours=start_hour)198 199 # Handle overnight shifts (where end < start)200 if end_hour < start_hour:201 end_time = base_date + timedelta(days=1, hours=end_hour)202 else:203 end_time = base_date + timedelta(hours=end_hour)204 205 gantt_data.append({206 'Employee': row['Name'] if 'Name' in assignments_df.columns else row['Employee_ID'],207 'Start': start_time,208 'Finish': end_time,209 'Shift': row['Assigned_Shift']210 })211 212 gantt_df = pd.DataFrame(gantt_data)213 214 # Create a color map for shifts215 shift_colors = px.colors.qualitative.Plotly[:len(shifts_df)]216 color_map = {shift: color for shift, color in zip(shifts_df.index, shift_colors)}217 218 # Create Gantt chart219 fig = px.timeline(220 gantt_df, 221 x_start='Start', 222 x_end='Finish', 223 y='Employee',224 color='Shift',225 title='Employee Shift Schedule',226 color_discrete_map=color_map227 )228 229 # Update layout for better time display230 fig.update_layout(231 xaxis_title='Time',232 yaxis_title='Employee',233 yaxis={'categoryorder': 'category ascending'},234 legend_title='Shift',235 height=600,236 xaxis={237 'tickformat': '%H:%M',238 'dtick': 3600000, # 1 hour in milliseconds239 }240 )241 242 # Add vertical lines at shift boundaries for easier visualization243 for _, row in shifts_df.iterrows():244 start_hour = int(row['start_time'])245 start_time = base_date + timedelta(hours=start_hour)246 247 fig.add_vline(248 x=start_time,249 line_dash='dash',250 line_color='gray',251 opacity=0.5252 )253 254 return fig255 256# Create Gradio interface257with gr.Blocks(title="Data-Driven Shift Scheduling") as demo:258 gr.Markdown("# Data-Driven Shift Scheduling")259 260 with gr.Row():261 gr.Markdown(r"""262 ## Mathematical Formulation263 264 Minimize $\sum_{i \in I, j \in J} c_{ij} \cdot x_{ij}$265 266 Subject to:267 - $\sum_{j \in J} x_{ij} = 1$ for all $i \in I$ (each employee gets exactly one shift)268 - $\sum_{i \in I} x_{ij} \geq r_j$ for all $j \in J$ (each shift meets minimum staffing requirement)269 - $x_{ij} \in \{0,1\}$ for all $i \in I, j \in J$270 271 Where:272 - $I$ is the set of employees273 - $J$ is the set of shifts274 - $c_{ij}$ is the cost of assigning employee $i$ to shift $j$275 - $r_j$ is the minimum staffing requirement for shift $j$276 - $x_{ij}$ is the decision variable: 1 if employee $i$ is assigned to shift $j$, 0 otherwise277 """, latex_delimiters=[{"left": "$", "right": "$", "display": False}])278 279 gr.Markdown("""280 ## Instructions281 Upload an Excel file with the following sheets ([template data](https://docs.google.com/spreadsheets/d/1trr2j4iOFQGwQWevRv01y5JJ--WP7ECx/edit?usp=sharing&ouid=108951544316632731762&rtpof=true&sd=true)):282 - 'costs' sheet: Cost matrix for assigning employees to shifts (employees as rows, shifts as columns)283 - 'employees' sheet: Information about employees (ID as index, with employee attributes)284 - 'shifts' sheet: Information about shifts (ID as index, with min_staff, start_time, and end_time)285 - 'params' sheet (optional): General parameters for the model286 - 'preferences' sheet (optional): Employee shift preferences (1=preferred, 0=not preferred)287 """)288 289 with gr.Row():290 input_file = gr.File(label="Upload Excel File")291 submit_btn = gr.Button("Solve Shift Scheduling Problem")292 293 with gr.Row():294 with gr.Column(scale=1):295 output_text = gr.Textbox(label="Optimization Results", lines=20)296 output_file = gr.File(label="Download Results")297 with gr.Column(scale=2):298 output_plot = gr.Plot(label="Shift Schedule Visualization")299 300 submit_btn.click(301 solve_shift_scheduling_model,302 inputs=[input_file],303 outputs=[output_text, output_plot, output_file]304 )305 306# Launch the app307if __name__ == "__main__":308 demo.launch()