I tried to add preemption rules with the following code, but it had no effect. According to the Shortest Remaining Time rule, a job that has already arrived and has less remaining execution time than the currently running job should be prioritized. However, when I run the code, the result is that the jobs are executed in sequential order based on their arrival time only. I have searched online for a lot of information, but I have not yet found an example of implementing preemption with gurobipy. I would like to ask the experts here if gurobipy can be used to implement preemption in job scheduling.
import gurobipy as gp
from gurobipy import GRB
# Define the job data: arrival times and processing times for 5 jobs
arrival_times = [0, 2, 4, 5, 7] # Replace with your actual data
processing_times = [3, 2, 1, 4, 2] # Replace with your actual data
# Create a Gurobi model
model = gp.Model("JobScheduling")
# Set the time limit (e.g., 3600 seconds or 1 hour)
time_limit_seconds = 3600
model.Params.TimeLimit = time_limit_seconds
model.update()
# Create a variable for each job
jobs = range(len(arrival_times))
x = {}
for i in jobs:
x[i] = model.addVar(vtype=GRB.BINARY, name=f"x[{i}]")
# Remaining processing times for each job
remaining_times = [processing_times[i] for i in jobs]
model.update()
# Set the objective to minimize total completion time
model.setObjective(
gp.quicksum((arrival_times[i] + processing_times[i] - remaining_times[i]) * x[i] for i in jobs),
GRB.MINIMIZE
)
# Constraint 1: Each job starts only once
for i in jobs:
model.addConstr(x[i] == 1, name=f"StartOnce[{i}]")
# Constraint 2: Jobs start after the previous job has finished
for i in jobs[:-1]:
model.addConstr(x[i] <= gp.quicksum(x[j] for j in jobs if j <= i), name=f"JobDependency[{i}]")
# Constraint 3: Job starts after its arrival time
for i in jobs:
model.addConstr(x[i] == 1, name=f"StartAfterArrival[{i}]")
model.update()
# Solve the model with preemption
while True:
model.optimize()
if model.status == GRB.OPTIMAL:
preempted_jobs = []
current_time = 0
print("Optimal Solution Found:")
for i in jobs:
if x[i].x > 0.5:
start_time = max(current_time, arrival_times[i])
completion_time = start_time + remaining_times[i]
print(f"Job {i} starts at time {start_time}, completion time: {completion_time}")
current_time = completion_time
remaining_times[i] = 0 # Job is completed
else:
remaining_times[i] = max(0, remaining_times[i] - 1) # Preempt the job
if remaining_times[i] > 0:
preempted_jobs.append(i)
if not preempted_jobs:
break # No remaining preempted jobs
else:
for i in preempted_jobs:
model.addConstr(x[i] == 1) # Reschedule preempted jobs
remaining_times[i] = processing_times[i] # Reset remaining time
else:
break # No optimal solution found
print("All jobs have been completed.")```
I would like the job scheduling to follow the SRT (Shortest Remaining Time) preemption rule. I'm also curious if Gurobi can be used to implement preemption.