How to use gurobipy to implement a job scheduling with SRT preemption?

51 views Asked by At

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.
0

There are 0 answers