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:
Model M = new Model("Multi-processor scheduling");
Variable x = M.Variable("x", new int[] {m, n}, Domain.Binary());
Variable t = M.Variable("t", 1, Domain.Unbounded());
M.Constraint( Expr.Sum(x, 0), Domain.EqualsTo(1.0) );
M.Constraint( Expr.Sub( Var.Repeat(t, m), Expr.Mul(x, T)), Domain.GreaterThan(0.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.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
M
is not empty dolet
k
be the machine with the smallest load so far,let
i
be the job inM
with the longest completion time,assign job
i
to machinek
,update the load of machine
k
,remove
i
fromM
.
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.
//Computing LPT solution
double [] init = new double[n * m];
double [] schedule = new double[m];
for (int i = n - 1; i >= 0; i--)
{
int next = 0;
for (int j = 1; j < m; j++)
if (schedule[j] < schedule[next]) next = j;
schedule[next] += T[i];
init[next * n + 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.
namespace mosek.fusion.example
{
public class lpt
{
public static void Main(string [] args)
{
int n = 30; //Number of tasks
int m = 6; //Number of processors
double lb = 1.0; //The range of lengths of short tasks
double ub = 5.0;
double sh = 0.8; //The proportion of short tasks
int n_short = (int)(n * sh);
int n_long = n - n_short;
double[] T = new double[n];
Random gen = new Random(0);
for (int i = 0; i < n_short; i++)
T[i] = gen.NextDouble() * (ub - lb) + lb;
for (int i = n_short; i < n; i++)
T[i] = 20 * (gen.NextDouble() * (ub - lb) + lb);
Array.Sort<double>(T);
Model M = new Model("Multi-processor scheduling");
Variable x = M.Variable("x", new int[] {m, n}, Domain.Binary());
Variable t = M.Variable("t", 1, Domain.Unbounded());
M.Constraint( Expr.Sum(x, 0), Domain.EqualsTo(1.0) );
M.Constraint( Expr.Sub( Var.Repeat(t, m), Expr.Mul(x, T)), Domain.GreaterThan(0.0) );
M.Objective( ObjectiveSense.Minimize, t );
//Computing LPT solution
double [] init = new double[n * m];
double [] schedule = new double[m];
for (int i = n - 1; i >= 0; i--)
{
int next = 0;
for (int j = 1; j < m; j++)
if (schedule[j] < schedule[next]) next = j;
schedule[next] += T[i];
init[next * n + i] = 1;
}
//Comment this line to switch off feeding in the initial LPT solution
x.SetLevel(init);
M.SetLogHandler(Console.Out);
M.SetSolverParam("mioTolRelGap", 0.01);
M.Solve();
try
{
Console.Write("initial solution: \n");
for (int i = 0; i < m; i++)
{
Console.Write("M {0} [", i);
for (int y = 0; y < n; y++)
Console.Write( "{0}, ", (int) init[i * n + y]);
Console.Write("]\n");
}
Console.Write("MOSEK solution:\n");
for (int i = 0; i < m; i++)
{
Console.Write("M {0} [", i);
for (int y = 0; y < n; y++)
Console.Write( "{0}, ", (int)x.Index(i, y).Level()[0]);
Console.Write("]\n");
}
}
catch (SolutionError e) {}
}
}
}