Scheduling Jobs on Identical Parallel Machines

Problem definition.

In scheduling jobs on identical parallel machines we have M identical machines and N jobs to be processed. Each job must be processed on one of these machines for \(p_{j}\) time units without interruption, and each job is available for processing at time 0. The aim is to complete all jobs as soon as possible.

Solution

Scheduling Jobs on Identical Parallel Machines problem is solved by greedy algorithm. We sort all jobs from longest to shortest. And we assign longest not assigned job to machine which has smallest load, until all jobs are assigned.

Example

#include "paal/greedy/scheduling_jobs_on_identical_parallel_machines/scheduling_jobs_on_identical_parallel_machines.hpp"

#include <iostream>
#include <utility>

int main() {
    typedef double Time;
    typedef std::pair<Time, char> Job;

    auto returnJobTimeFunctor = [](Job job) { return job.first; };

    // sample data
    int numberOfMachines = 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<int, decltype(jobs)::iterator>> result;

    paal::greedy::scheduling_jobs_on_identical_parallel_machines(
        numberOfMachines, jobs.begin(), jobs.end(), back_inserter(result),
        returnJobTimeFunctor);

    std::vector<Time> sumOfMachine;
    sumOfMachine.resize(numberOfMachines);
    for (auto machineJobPair : result) {
        auto machine = machineJobPair.first;
        auto job = machineJobPair.second;
        sumOfMachine[machine] += job->first;
        std::cout << "On machine: " << machine << " do job: " << job->second
                  << std::endl;
    }
    Time maximumLoad =
        *std::max_element(sumOfMachine.begin(), sumOfMachine.end());

    // print result
    std::cout << "Solution:" << maximumLoad << std::endl;
    return 0;
}

example file is scheduling_jobs_on_identical_parallel_machines_example.cpp

Parameters

IN: int n_machines IN: InputIterator first iterator to collection of jobs is not const because we sort given collection IN: InputIterator last OUT: OutputIterator result pair of machine id and job iterator IN: GetTime getTime

Approximation Ratio equals 4/3.

Complexity

Complexity of the algorithm is \(O(|N|*log(|N|))\) where N is size of input

References

The algorithm analysis is described in [23]