Generalised Assignment

Problem definition.

In the Generalized Assignment problem we are given a set of jobs \(J\) and a set of machines \(M\). For each job \(j\in J\) and machine \(i\in M\) we are given a processing time \(t_{ij}\) and cost \(c_{ij}\). For each machine \(i\) we are also given a maximum time \(T_{i}\) for which the machine is available. The goal is to assign each job to some machine, so that the total cost is minimized and no machine is used for more than its available time. Both finding the optimal assignment and deciding whether a feasible assignment exists are NP-complete problems.

An LP relaxation of the problem is as follows. We introduce a binary variable \(x_e\) for every \(e=(i,j)\) job-machine pair such that \(t_{ij} \leq T_i\).

\begin{eqnarray*} \mbox{minimize:} & & \\ & \sum_{e=(i,j)} c_e x_e & \\ \mbox{subject to:} & & \\ & \sum_{e\in\delta(j)} x_e = 1 & \mbox{ for every } j\in J\\ & \sum_{e\in\delta(i)} t_e x_e \leq T_i & \mbox{ for every } i\in M\\ & x_e \geq 0 & \mbox{ for every } e\\ \end{eqnarray*}

Solution

We solve the problem using the Shmoys and Tardos approximation iterative rounding algorithm (using the above LP formulation).

Example

#include "paal/iterative_rounding/generalised_assignment/generalised_assignment.hpp"

#include <iostream>
#include <vector>

int main() {
    // sample problem
    std::vector<int> machines = {0,1};
    std::vector<int> jobs = {0,1};

    std::vector<std::vector<int>> cost(2, std::vector<int>(2));
    cost[0][0] = 2;
    cost[0][1] = 3;
    cost[1][0] = 1;
    cost[1][1] = 3;
    auto costf = [&](int i, int j) { return cost[i][j]; };

    std::vector<std::vector<int>> time(2, std::vector<int>(2));
    time[0][0] = 2;
    time[0][1] = 2;
    time[1][0] = 1;
    time[1][1] = 1;
    auto timef = [&](int i, int j) { return time[i][j]; };

    std::vector<int> T = { 2, 2 };
    auto Tf = [&](int i) { return T[i]; };

    std::vector<std::pair<int, int>> jobs_to_machines;

    // solve it
    auto result = paal::ir::generalised_assignment_iterative_rounding(
        machines.begin(), machines.end(), jobs.begin(), jobs.end(), costf,
        timef, Tf, std::back_inserter(jobs_to_machines));

    // print result
    if (result.first == paal::lp::OPTIMAL) {
        for (auto jm : jobs_to_machines) {
            std::cout << "Job " << jm.first << " assigned to Machine "
                << jm.second << std::endl;
        }
        std::cout << "Cost of the solution: " << *(result.second) << std::endl;
    } else {
        std::cout << "The instance is infeasible" << std::endl;
    }
    paal::lp::glp::free_env();
    return 0;
}

complete example of the usage can be found in file generalised_assignment_example.cpp

Approximation Ratio

The cost of the solution is at most the cost of the optimal solution and each time limit \(T_i\) is violated at most by a factor of 2.

Complexity

The time complexity of the algorithm is \(O((|J|+|M|)*(|J|*|M|+LP_{time}(|J|*|M|,|J|+|M|)))\), where \(|J|\) and \(|M|\) are respectively the numbers of jobs and machines and \(LP_{time}(col, row)\) is the time of solving the LP with \(O(col)\) columns and \(O(row)\) rows.

The memory complexity of the algorithm is \(O(|J|*|M|+LP_{mem}(|J|*|M|,|J|+|M|))\), where \(LP_{mem}(col, row)\) is the memory complexity of solving the LP with \(O(col)\) columns and \(O(row)\) rows.

References

The iterative rounding approximation by Shmoys and Tardos is described in [18].