Problem definition.
In scheduling jobs, N jobs are to be assigned to M machines, where job j consumes \(p_j\) time-units, and machine i has speed \(s_i\). Thus machine i requires \(\frac{p_j}{s_i}\) time-units to complete job j. Let \(l_i = \sum_{\mbox{j: j is assigned to i}}p_j\) be the load on machine i. The aim is to minimize makespan \(max_i\frac{l_i}{s_i}\).
Solution
We calculate the lower bound for the solution \(T_{LB} = max_jT_j\) ,where \(T_j = min_i max\{\frac{p_j}{s_i}, \frac{\sum_{k=1}^{j}p_k}{\sum_{l=1}^{i}s_k}\}\). We then obtain the fractional allocation in the following way:
-
Let j be the first job such that \(\sum_{k=1}^{j}p_k > T_{LB} \cdot s_1\).
-
Assign to machine 1 jobs 1, \(\dots\), j-1, plus a fraction of j in order to equate \(l_1=T_{LB} \cdot s_1\).
-
Continue recursively with the unassigned fractions of jobs and machines 2, \(\dots\), m.
Finally we round to an integral schedule. Function scheduleDeterministic uses the natural rounding, of integrally placing each job on the first machine that got some fraction of it. Function scheduleRandomized uses the randomized rounding which works as follows. We first choose \(\alpha \in [0,1]\) uniformly at random. Then for each job we either place it on the first machine that got some fraction of it, if this fraction is bigger than \(alpha\), or otherwise we place it on the second machine that got some fraction of it.
Attention Our solution needs the value of \(\sum_{j=1}^{N}p_j \cdot \sum_{i=1}^{M}s_i\) to not overflow its value type.
Example
#include <iostream>
#include <unordered_map>
#include <utility>
typedef std::pair<Time, char> Job;
typedef int Machine;
template <class Result> void print_result(const Result &result) {
std::unordered_map<Machine, Time> machineTime;
for (auto const &machineJobpair : result) {
Machine machine = *machineJobpair.first;
Job job = *machineJobpair.second;
machineTime[machine] += job.first / machine;
std::cout << "On machine: " << machine << " do job: " << job.second
<< std::endl;
}
Time max_time = 0;
for (auto const &it : machineTime) {
max_time = std::max(max_time, it.second);
}
std::cout << "Solution: " << max_time << std::endl;
}
int main() {
auto returnJobLoadFunctor = [](Job job) { return job.first; };
std::vector<Machine> machines = { 1, 2, 3 };
std::vector<Job> jobs = { { 2.1, 'a' }, { 3.1, 'b' }, { 4.1, 'c' },
{ 5.1, 'd' }, { 6.1, 'e' }, { 7.1, 'f' },
{ 8.1, 'g' } };
std::vector<std::pair<decltype(machines) ::iterator,
decltype(jobs) ::iterator>> deterministicResult,
randomizedResult;
std::cout << "Deterministic schedule:" << std::endl;
machines.begin(), machines.end(), jobs.begin(), jobs.end(),
returnJobLoadFunctor);
print_result(deterministicResult);
std::cout << "Randomized schedule:" << std::endl;
paal::greedy::schedule_randomized(
machines.begin(), machines.end(), jobs.begin(), jobs.end(),
returnJobLoadFunctor);
print_result(randomizedResult);
return 0;
}
example file is scheduling_jobs_example.cpp
Approximation Ratio equals 2.
Complexity
Time Complexity of the algorithm is \(O(|N|*log(|N|) + |M|*log(|M|))\). Memory Complexity of the algorithm is \((O(|N| + |M|))\).
Game-theoretic Properties
Randomized version of the algorithm is thruthful in expectation: i.e. expected load on any given machine is a monotone (decreasing) function of its speed (when all other machines' speeds are fixed).
References
The algorithm analysis is described in [17], chapter 12.
1.8.5
