Task Scheduling

Problem

An OR scientist has started a project consisting of 7 tasks. Some of the tasks can be done independently of others, but some tasks have predecessors. For example, in order to solve a model with a solver, the model must first be mathematically formulated. For example, if it takes 4 days to formulate the model then the solver step can only be started 4 days after the start of formulation.

The OR scientist has set minimum and maximum durations for completion time of each job and he/she has to determine the amount of days to allocate for each. The OR scientist also calculated a cost associated with the completion time of each job. Completing tasks in a shorter period of time is more costly than completing them in a longer period of time. The minimum and maximum time-cost relationship is linear and a cost for any completion time can be calculated.

The OR scientist wants to complete this project in at most 40 days while minimizing the total cost and needs to determine:

  1. When to start each task
  2. Amount of days to allocate for each task
task min_duration max_duration min_cost max_cost predecesor
0 1 6 12 1600 1000 none
1 2 8 16 2400 1800 none
2 3 16 24 2900 2000 2
3 4 14 20 1900 1300 1, 2
4 5 4 16 3800 2000 3
5 6 12 16 2900 2200 3
6 7 2 12 1300 800 4

\[ \begin{split} \begin{align} &I: tasks \\ \\ &s_{i}: \text{starting of task i} \\ &d_{i}: \text{duration of task i} \\ \\ &dmin_{i}: \text{minimum duration for task i} \\ &dmax_{i}: \text{maximum duration for task i} \\ &cmin_{i}: \text{minimum cost for task i} \\ &cmax_{i}: \text{maximum cost for task i} \\ &c_{i}: \text{cost for task i} \\ \end{align} \end{split} \]

\[ \begin{split} \begin{align} \\ &\text{minimize}\ \sum_{i \in I} c_{i} \\ &st \\ \\ &s_{3}\ \ge\ s_{2}\ +\ d_{2} \\ &s_{4}\ \ge\ s_{1}\ +\ d_{1} \\ &s_{4}\ \ge\ s_{2}\ +\ d_{2} \\ &s_{5}\ \ge\ s_{3}\ +\ d_{3} \\ &s_{6}\ \ge\ s_{3}\ +\ d_{3} \\ &s_{7}\ \ge\ s_{4}\ +\ d_{4} \\ &dmin_{i}\ \le\ d_{i}\ \le\ dmax_{i} \qquad \forall i \in I \\ &s_{i}\ +\ d_{i}\ \le\ 40 \qquad \forall i \in I\\ &c_{i} = (\frac{cmin_{i}\ -\ cmax_{i}}{dmax_{i}\ -\ dmin_{i}})(d_{i}\ -\ dmin_{i})\ +\ cmax_{i} \qquad \forall i \in I\\ \end{align} \end{split} \]

import pandas as pd
import gurobipy as grb
from gurobipy import GRB
import matplotlib.pyplot as plt

#read the data into a dataframe
tasks_df = pd.read_excel('tasks.xlsx')

#task set
I = tasks_df['task'].to_list()

#parameters
dmin = {tasks_df.loc[_, 'task']: tasks_df.loc[_, 'min_duration'] for _ in range(len(tasks_df))}
dmax = {tasks_df.loc[_, 'task']: tasks_df.loc[_, 'max_duration'] for _ in range(len(tasks_df))}
cmin = {tasks_df.loc[_, 'task']: tasks_df.loc[_, 'min_cost'] for _ in range(len(tasks_df))}
cmax = {tasks_df.loc[_, 'task']: tasks_df.loc[_, 'max_cost'] for _ in range(len(tasks_df))}
#model
model = grb.Model('Task Scheduling')

#dvar
s = model.addVars(I, name = 's')
d = model.addVars(I, name = 'd')

#obj
objective = grb.quicksum(cmax[i] + (d[i]-dmin[i])*((cmin[i]-cmax[i])/(dmax[i]-dmin[i])) for i in I) #total cost
model.setObjective(objective, GRB.MINIMIZE)

#constr
model.addConstr(s[3] >= s[2] + d[2]) #predecessors
model.addConstr(s[4] >= s[1] + d[1])
model.addConstr(s[4] >= s[2] + d[2])
model.addConstr(s[5] >= s[3] + d[3])
model.addConstr(s[6] >= s[3] + d[3])
model.addConstr(s[7] >= s[4] + d[4])
for i in I:
    model.addConstr(d[i] >= dmin[i]) #min and max durations 
    model.addConstr(d[i] <= dmax[i])   
for i in I:
    model.addConstr(s[i] + d[i] <= 40) #latest task must be completed before or on day 40
    
model.optimize()    
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 27 rows, 14 columns and 46 nonzeros
Model fingerprint: 0x0e238fe0
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [5e+01, 2e+02]
  Bounds range     [0e+00, 0e+00]
  RHS range        [2e+00, 4e+01]
Presolve removed 27 rows and 14 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    1.1100000e+04   0.000000e+00   0.000000e+00      0s

Solved in 0 iterations and 0.01 seconds (0.00 work units)
Optimal objective  1.110000000e+04
for i in I:
    print(f"Task {i} starts at day {int(s[i].x)}, duration: {int(d[i].x)} days, ends at day {int(s[i].x + d[i].x)}")
Task 1 starts at day 0, duration: 6 days, ends at day 6
Task 2 starts at day 0, duration: 8 days, ends at day 8
Task 3 starts at day 8, duration: 16 days, ends at day 24
Task 4 starts at day 8, duration: 14 days, ends at day 22
Task 5 starts at day 24, duration: 4 days, ends at day 28
Task 6 starts at day 24, duration: 12 days, ends at day 36
Task 7 starts at day 22, duration: 2 days, ends at day 24
fig, ax = plt.subplots(figsize = (10,4))
colors = ['tab:red', 'tab:orange', 'tab:olive', 'tab:green', 'tab:cyan', 'tab:blue', 'tab:purple']

for i in I:
    start = s[i].x
    duration = d[i].x
    ax.barh(i, duration, left = start, color = colors[i-1])
    ax.text(start + duration / 2, i, str(i), ha='center', va='center', color='white')

Back to top