11.4 Multiprocessor Scheduling¶
In this case study we consider a simple scheduling problem in which a set of jobs must be assigned to a set of identical machines. We want to minimize the makespan of the overall processing, i.e. the latest machine termination time.
The main aims of this case study are
to show how to define a Integer Linear Programming model,
to take advantage of Fusion operators to compactly express sets of constraints,
to provide the solver with an incumbent integer feasible solution.
Mathematical formulation
We are given a set of jobs \(J\) with \(|J|=n\) to be assigned to a set \(M\) of identical machines with \(|M|=m\). Each job \(j\in J\) has a processing time \(T_j>0\) and can be assigned to any machine. Our aim is to find the job scheduling that minimizes the overall makespan, i.e. the maximum completion time among all machines.
Formally, we introduce a binary variable \(x_{ij}\) that takes value \(1\) if the job \(j\) is assigned to the machine \(i\), zero otherwise. The only constraint we need to set is the requirement that a job must be assigned to a single machine. The optimization model takes the following form:
Model (11.17) can be easily transformed into an integer linear programming model as follows:
The implementation of this model in Fusion is straightforward:
with Model('Multi-processor scheduling') as M:
x = M.variable('x', [m, n], Domain.binary())
t = M.variable('t', 1, Domain.unbounded())
M.constraint(Expr.sum(x, 0), Domain.equalsTo(1.))
M.constraint(Expr.sub(Var.repeat(t, m), Expr.mul(x, T)),
Domain.greaterThan(0.))
M.objective(ObjectiveSense.Minimize, t)
Most of the code is self-explanatory. The only critical point is
M.constraint(Expr.sub(Var.repeat(t, m), Expr.mul(x, T)),
Domain.greaterThan(0.))
that implements the set of constraints
To fit in Fusion we restate the constraints as
which corresponds in matrix form to
The function Var.repeat creates a vector of length \(m\), as required for (11.19). The same result can be obtained via matrix multiplication, i.e. using Expr.mul (*,@), but in this particular case Var.repeat is faster as it only performs a logical operation.
Longest Processing Time first rule (LPT)
The multiprocessor scheduling is known to be an NP-complete problem (see [GJ79]). Nevertheless there are effective heuristics, with provable worst case bounds, that are able to provide a good integer solution quickly. In particular, we will use the so-called Longest Processing Time first rule (LPT, proposed in [Gra69]).
The informal algorithm sketch is the following:
while
Mis not empty dolet
kbe the machine with the smallest load so far,let
ibe the job inMwith the longest completion time,assign job
ito machinek,update the load of machine
k,remove
ifromM.
This simple algorithm is a \(\frac{1}{3}(4-\frac{1}{m})\) approximation. So for \(m=1\) we get the optimal solution (indeed there is no choice with a single machine); for \(m\rightarrow\infty\) the approximation factor is no worse than \(4/3\) (again see [Gra69]).
A simple implementation is given below.
#LPT heuristic
schedule = [0. for i in range(m)]
init = [0. for i in range(n * m)]
for i in range(n):
mm = schedule.index(min(schedule))
schedule[mm] += T[i]
init[n * mm + i] = 1.
An efficient implementation of the LPT rule is beyond the scope of this section. The important part is that the scheduling produced by the LPT algorithm can be used as incumbent solution for the MOSEK mixed-integer linear programming solver. The availability of an integer feasible solution can significantly improve the performance of the solver.
To input the solution we only need to use the Variable.setLevel method, as shown below
x.setLevel(init)
We can test the program with and without providing the initial LPT solution. Our random datasets consists of a mix of tasks with long and short processing times and we accept a solution at relative optimality tolerance \(0.01\). Some results are shown in the table below.
\(n\) |
\(m\) |
long tasks |
short tasks |
No LPT |
With LPT |
|---|---|---|---|---|---|
1000 |
8 |
\(20\%\) |
\(80\%\) |
|
|
1000 |
8 |
\(80\%\) |
\(20\%\) |
|
|
100 |
12 |
\(20\%\) |
\(80\%\) |
|
|
100 |
12 |
\(80\%\) |
\(20\%\) |
|
|
20 |
20 |
\(0\%\) |
\(100\%\) |
|
|
We can see that depending on the structure and parameters of the problem it may pay off to provide an initial LPT solution. Therefore it is always recommended to test the mixed-integer solver with different settings to find the most efficient setup for a given problem.
import sys
import random
from mosek.fusion import *
def main():
#Parameters:
n = 30 #Number of tasks
m = 6 #Number of processors
lb = 1. #Range of short task lengths
ub = 5.
sh = 0.8 #Proportion of short tasks
n_short = int(n * sh)
n_long = n - n_short
random.seed(0)
T = sorted([random.uniform(lb, ub) for i in range(n_short)]
+ [random.uniform(20 * lb, 20 * ub) for i in range(n_long)], reverse=True)
print("# jobs(n) : ", n)
print("# machine(m): ", m)
with Model('Multi-processor scheduling') as M:
x = M.variable('x', [m, n], Domain.binary())
t = M.variable('t', 1, Domain.unbounded())
M.constraint(Expr.sum(x, 0), Domain.equalsTo(1.))
M.constraint(Expr.sub(Var.repeat(t, m), Expr.mul(x, T)),
Domain.greaterThan(0.))
M.objective(ObjectiveSense.Minimize, t)
#LPT heuristic
schedule = [0. for i in range(m)]
init = [0. for i in range(n * m)]
for i in range(n):
mm = schedule.index(min(schedule))
schedule[mm] += T[i]
init[n * mm + i] = 1.
#Comment this line to switch off feeding in the initial LPT solution
x.setLevel(init)
M.setLogHandler(sys.stdout)
M.setSolverParam("mioTolRelGap", .01)
M.solve()
print('initial solution:')
for i in range(m):
print('M', i, init[i * n:(i + 1) * n])
print('MOSEK solution:')
for i in range(m):
print('M', i, [y for y in x.slice([i, 0], [i + 1, n]).level()])
if __name__ == '__main__':
main()
