Given
Each task
Each machine
The objective is to maximize all tasks' that can be run on the machine cores multiplied by the duration of the task, i.e.
The constraints are:
-
Each time slot, the sum of cores of all tasks running on the machine cannot exceed the machine cores.
-
Each task can only be run on the machine if the start time of the task is later than the start time of the machine.
-
Each task can only be run on the machine if the end time of the task is earlier than the end time of the machine.
-
Each task can only be run on the machine if the sum of cores of all tasks running on the machine cannot exceed the machine cores.
-
Each task can only be run on the machine if the start time of the task is later than or equal the earliest start time of the task.
-
Each task can only be run on the machine if the start time of the task is earlier than or equal the latest start time of the task.
Formally, the constraints are (maybe not complete):
- Core constraint:
$\forall k \in [M], \forall t \in [T_s^{(k)}, T_e^{(k)}], \sum_{i \in A_k}c_i \leq M_k$ , where$A_k$ is the set of tasks that can be run on machine$k$ at time$t$ . - Start time constraint:
$\forall i \in [N], \max{(h_s^{(i)},T_s^{(k)})} \leq t \lt h_e^{(i)} \Rightarrow i \in A_k$ , where$A_k$ is the set of tasks that can be run on machine$k$ at time$t$ . - End time constraint:
$\forall i \in [N],T_e^{k} \geq t + d_i \Rightarrow i \in A_k$ , where$A_k$ is the set of tasks that can be run on machine$k$ at time$t$ , and$t$ is the start time of task$i$ on machine$k$ .
Main code is in src/.main.py
, just run python main.py
to run the code.
The code does not implement the local search strategy, just the greedy strategy.
Also, there is a gurobi implementation in src/gurobi.py
, before run, you should make sure install the gurobipy
package, and run python gurobi.py
to run the code.