I am working on solving a scheduling problem using OptaPy. This scheduling problem is based on assigning and scheduling unassigned task orders, each of which represents a cleaning job. The reference for this task is the "scheduling dataset." Each task order has a set of features, which you can find later in this document.
Problem Statement:
The goal is to build a scheduling algorithm for assigning unassigned jobs to available vehicles in a way that ensures completion of all the task orders between their created datetime and estimated completion date and time. We are dealing with 35 incomplete jobs which are to be assigned to the available 10 vehicles as per the scheduling dataset.
Detailed Constraints and Goals:
- A TaskOrder cannot start before its creation date time.
- A TaskOrder must finish before its estimated completion date.
- A TaskOrder cannot be assigned to a crew if the crew's vehicle is not available.
- A vehicle capacity cannot exceed the volume of sand to be cleaned.
- Vehicles can work 24*7 including weekends, however there are two breaks, one between 12:00PM to 1:00PM and the other at 7PM-8PM. So vehicle should not work during these two intervals.
- No two or more vehicles should be assigned jobs at the same place and same time, that means job should not overlap.
- Every vehicle has a shift start time, so they should not be allocated jobs before their start "vehicle_shift_start" time.
- Although the clean up activities can happen 24*7, we should keep in mind, that for each vehicle it cannot exceed the shift time allocated for that vehicle. That means if a task order has 50 units of sand to clean, and the vehicle capacity is 20 units, it implies that the vehicle must do at-least three trips to clean up the sand. This trips can be back to back for a vehicle, but they cannot work during two break times.
Task order Attributes (scheduling_data.csv):
- work_order_id (str): Unique identifier for each task order. (Example Value - 5954)
- task_id(str): Unique identifier for each task. (Example Value - 3781)
- status(str): The current status of the task order, indicating whether it is completed. (Example Value - Incomplete)
- created_date(datetime): Date and time the task order was created. (Example Value - 4/13/2023 1:36:53 AM)
- severity(str): This indicates the severity of the task order and can be either "LOW," "MEDIUM," or "HIGH." (Example Value - HIGH) priority(str): This shows the priority of the task order, which can be "LOW," "HIGH," or "EMERGENCY." (Example Value - EMERGENCY)
- area_code(str): An identifier that can be considered as the area name. Each area code corresponds to a road name in a separate database. (Example Value - Area 60)
- sand_volume(int): The amount of sand that needs to be cleaned from the designated area. (Example Value - 30)
- time_taken_for_cleaning(float): The time required in hours to clean up the sand from the respective area code. We are assuming that every 20 units of sand takes 1 hour to clean (Example Value - 1.5)
- est_cmp_datetime(datetime): The estimate completion datetime, before which a given job has to be completed. (Example Value - 4/15/2023 11:59:59 PM)
Crew/Vehicle Parameters(crew_data.csv):
The task orders are assigned to crews, which in this scenario are vehicles. The attributes of each vehicle are:
- vehicle_num(str): A unique identifier vehicle id for each vehicle. (Example Value - 1001) speed(int): The average speed of the vehicle in km/hr. (Example Value - 20)
- vehicle_capacity(int): The amount of sand that the vehicle can carry. (Example Value - 25) vehicle_depot_name(str): The depot id where the vehicle is currently stationed. (Example Value - 2403)
- shift_time(int): The total working hours for the vehicle in a given day. This is given by hours. (Example Value - 10)
- vehicle_return_depot: The depotid where the vehicle must return after performing its cleaning activities. (Example Value - 2403)
- vehicle_shift_start(datetime): The time of day when the vehicle starts its job. (Example Value - 10:00:00 AM)
I need some help to understand how to model this problem, and if my planning entities, problem facts, etc are correct. Below is the code I have written, but I am always getting a Java Runtime Exception.
Error
java.lang.IllegalArgumentException: java.lang.IllegalArgumentException: The entityClass (class org.jpyinterpreter.user.WorkOrder) has a @PlanningVariable annotated property (assigned_start_time) with a valueRangeProviderRef (datetime) that does not exist in a @ValueRangeProvider on the solution class (Schedule) or on that entityClass.
The valueRangeProviderRef (datetime) does not appear in the valueRangeProvideIds ([crew]).
Code :
# Vehicle class definition
@problem_fact
class Vehicle:
def __init__(self,
vehicle_num: int,
speed: int,
vehicle_capacity: int,
vehicle_depot_name: str,
shift_time: int,
vehicle_return_depot: str,
vehicle_shift_start: time): # Change to time
self.vehicle_num = vehicle_num
self.speed = speed
self.vehicle_capacity = vehicle_capacity
self.vehicle_depot_name = vehicle_depot_name
self.shift_time = shift_time
self.vehicle_return_depot = vehicle_return_depot
self.vehicle_shift_start = vehicle_shift_start
self.vehicle_shift_end = (datetime.combine(datetime.today(), vehicle_shift_start) + timedelta(hours=shift_time)).time()
# Crew class definition
@problem_fact
class Crew:
def __init__(self, vehicles: List[Vehicle]):
self.vehicles = vehicles
# WorkOrder class definition
@planning_entity
class WorkOrder:
def __init__(self,
work_order_id: int,
task_id: int,
status: str,
created_date: datetime,
severity: str,
priority: str,
area_code: str,
sand_volume: int,
time_taken_for_cleaning: int,
crew: Optional[Crew] = None,
assigned_start_time: Optional[datetime] = None,
est_cmp_datetime: Optional[datetime] = None):
self.work_order_id = work_order_id
self.task_id = task_id
self.status = status
self.created_date = created_date
self.severity = severity
self.priority = priority
self.area_code = area_code
self.sand_volume = sand_volume
self.time_taken_for_cleaning = time_taken_for_cleaning
self.crew = crew
self.assigned_start_time = assigned_start_time
self.est_cmp_datetime = est_cmp_datetime
# Planning variable: changes during planning, between score calculations.
@optapy.planning_variable(Crew, ["crew"])
def get_crew(self):
return self.crew
def set_crew(self, crew):
self.crew = crew
# Planning variable: changes during planning, between score calculations.
@optapy.planning_variable(datetime, ["datetime"])
def get_assigned_start_time(self):
return self.assigned_start_time
def set_assigned_start_time(self, assigned_start_time):
self.assigned_start_time = assigned_start_time
@planning_solution
class Schedule:
def __init__(self, work_orders: List[WorkOrder], vehicles: List[Vehicle], crews: List[Crew], score=None):
self.work_orders = work_orders
self.vehicles = vehicles
self.crews = crews
self.score = score
@optapy.planning_entity_collection_property(WorkOrder)
def get_work_orders(self):
return self.work_orders
@optapy.problem_fact_collection_property(Vehicle)
def get_vehicles(self):
return self.vehicles
@optapy.problem_fact_collection_property(Crew)
@optapy.value_range_provider('crew')
def get_crews(self):
return self.crews
@optapy.planning_score(HardMediumSoftScore)
def get_score(self):
return self.score
def set_score(self, score):
self.score = score
@constraint_provider
def scheduling_constraints(constraint_factory: ConstraintFactory):
return [
# Hard constraints
work_order_constraints(constraint_factory),
vehicle_capacity(constraint_factory),
shift_time(constraint_factory),
lunch_break(constraint_factory),
no_overlapping_jobs(constraint_factory),
# Soft constraints
maximize_sand_cleaning(constraint_factory),
avoid_too_many_tasks_in_a_row(constraint_factory),
]
def vehicle_capacity(constraint_factory):
return constraint_factory \
.from_(WorkOrder) \
.filter(lambda work_order: work_order.sand_volume > work_order.crew.vehicles[0].vehicle_capacity) \
.penalize("Vehicle capacity", HardMediumSoftScore.ONE_HARD)
def shift_time(constraint_factory):
return constraint_factory \
.from_(WorkOrder) \
.filter(lambda work_order:
work_order.assigned_start_time.time() < work_order.crew.vehicles[0].vehicle_shift_start or
work_order.assigned_start_time + timedelta(minutes=work_order.time_taken_for_cleaning) >
datetime.combine(work_order.assigned_start_time.date(), work_order.crew.vehicles[0].vehicle_shift_end)
) \
.penalize("Shift time", HardMediumSoftScore.ONE_HARD)
def lunch_break(constraint_factory):
return constraint_factory \
.from_(WorkOrder) \
.filter(lambda work_order: 12 <= work_order.assigned_start_time.hour < 13) \
.penalize("Lunch break", HardMediumSoftScore.ONE_HARD)
def no_overlapping_jobs(constraint_factory):
return constraint_factory \
.from_(WorkOrder) \
.join(WorkOrder) \
.filter(lambda wo1, wo2:
wo1.crew == wo2.crew and
wo1.assigned_start_time < wo2.assigned_start_time <
wo1.assigned_start_time + timedelta(hours=wo1.time_taken_for_cleaning)
) \
.penalize("No overlapping jobs", HardMediumSoftScore.ONE_HARD)
def maximize_sand_cleaning(constraint_factory):
return constraint_factory \
.from_(WorkOrder) \
.reward("Maximize sand cleaning", HardMediumSoftScore.ONE_SOFT, lambda work_order: work_order.sand_volume)
def avoid_too_many_tasks_in_a_row(constraint_factory):
return constraint_factory \
.from_(WorkOrder) \
.join(WorkOrder) \
.filter(lambda wo1, wo2:
wo1.crew == wo2.crew and
wo1.assigned_start_time + timedelta(hours=wo1.time_taken_for_cleaning) == wo2.assigned_start_time
) \
.penalize("Avoid too many tasks in a row", HardMediumSoftScore.ONE_SOFT)
def work_order_constraints(constraint_factory):
return [
# A WorkOrder cannot start before its creation time.
constraint_factory
.from_(WorkOrder)
.filter(lambda wo: wo.assigned_start_time < wo.created_date)
.penalize("Cannot start before creation", HardMediumSoftScore.ONE_HARD),
# A WorkOrder must finish before its estimated completion date.
constraint_factory
.from_(WorkOrder)
.filter(lambda wo: wo.assigned_start_time + timedelta(minutes=wo.time_taken_for_cleaning) > wo.est_cmp_datetime)
.penalize("Must finish before estimated completion", HardMediumSoftScore.ONE_HARD),
# A WorkOrder cannot be assigned to a crew if the crew's vehicle is not available.
constraint_factory
.from_(WorkOrder)
.join(Crew,
Joiners.equal(lambda wo: wo.crew),
Joiners.lessThan(lambda wo: wo.assigned_start_time, lambda crew: crew.vehicles[0].vehicle_shift_start),
Joiners.greaterThan(lambda wo: wo.assigned_start_time + timedelta(minutes=wo.time_taken_for_cleaning), lambda crew: crew.vehicles[0].vehicle_shift_end))
.penalize("Vehicle not available", HardMediumSoftScore.ONE_HARD)
]
import pandas as pd
"""PREPARE DATA STAGE"""
vehicle_df = pd.read_csv('D:/CVRP_May/Scheduling/Data/crew_data.csv')
vehicle_df = vehicle_df.dropna()
work_order_df = pd.read_csv('D:/CVRP_May/Scheduling/Data/scheduling_data.csv')
work_order_df = work_order_df.dropna()
# Convert vehicle_shift_start from string to datetime.time
vehicle_df['vehicle_shift_start'] = pd.to_datetime(vehicle_df['vehicle_shift_start']).dt.time
vehicle_data = vehicle_df.to_dict('records') # This will give a list of dictionaries
work_order_df['created_date'] = pd.to_datetime(work_order_df['created_date'])
work_order_df['est_cmp_datetime'] = pd.to_datetime(work_order_df['est_cmp_datetime'])
work_order_data = work_order_df.to_dict('records') # This will give a list of dictionaries
# work_order_df.loc[0]['created_date'] < work_order_df.loc[0]['est_cmp_datetime']
# vehicle_df.loc[0]['vehicle_shift_start'] < vehicle_df.loc[1]['vehicle_shift_start']
vehicles = [Vehicle(**data) for data in vehicle_data]
crews = [Crew([vehicle]) for vehicle in vehicles]
work_orders = [WorkOrder(crew=None, assigned_start_time=None, **data) for data in work_order_data]
"""SOLVE STAGE"""
# Define the problem
problem = Schedule(work_orders, vehicles, crews)
# Configure and load the solver config
timeout = 10
solver_config = solver.SolverConfig()
solver_config.withSolutionClass(Schedule).withEntityClasses(WorkOrder).withConstraintProviderClass(
scheduling_constraints).withTerminationSpentLimit(Duration.ofSeconds(timeout))
solver_factory = optapy.solver_factory_create(solver_config)
solution = solver_factory.buildSolver().solve(problem)
print("Score Explanation.")
print("Final Score: {}".format(solution.get_score()))
