Job sequencing problem

Problem statement

There are n jobs to be processed on a machine. Each job i has a deadline d_{i} >= 0 and profit p_{i} >= 0. p_{i} is earned if the job is completed by its deadline. Job is completed if it is processed on a machine for unit time. Only one job is processed at a time on the machine.

A feasible solution is a subset of jobs J such that each job is completed by its deadline. An optimal solution is a feasible solution with maximum value.

Solving algorithm

  1. Sort   p_{i} in non-increasing order. So that, after sorting profit array look like p_{1} >= p_{2} p_{n}
  2. Add the next job i to the solution if i can be completed by its deadline. Assign i to time slot [r-1, r] such that 1<= r <= d_{i} and [r-1, r] is free.
  3. Stop if all jobs are examined. Otherwise go to step 2.

Time complexity: O(n^2)

Code

//
//  main.cpp
//  Job sequencing
//
//  Created by Himanshu on 14/08/21.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5;

struct node {
    int p,d;
};

bool cmp (const struct node &a, const struct node &b) {
    return a.p> b.p;
}

void solve (int p[], int d[]) {
    struct node q[N];
    int slot[N] = {0};
    int ans = 0;
    vector<int> sol;
    for (int i=0; i<N; i++) {
        q[i].p = p[i];
        q[i].d = d[i];
    }
    sort(q, q+N, &cmp);
    
    for (int i=0; i<N; i++) {
        if (slot[q[i].d-1] == 0) {
            ans += q[i].p;
            sol.push_back(i);
            slot[q[i].d-1] = 1;
        } else {
            int j = q[i].d -1;
            while (j>=0 && slot[j] != 0) {
                j--;
            }
            if (j >= 0) {
                ans += q[i].p;
                sol.push_back(i);
                slot[j] = 1;
            }
        }
    }
    cout<<"Job selected\n";
    for (int i=0; i<sol.size(); i++) {
        cout<<q[sol[i]].p<<" ";
    }
    cout<<"\nProfit: "<<ans<<"\n";
}
 
int main() {
    int p[] = {10, 5, 20, 15, 1};
    int d[] = {1, 3, 2, 2, 3};
    solve(p, d);
    return 0;
}

Here’s working example:

https://ideone.com/uxigXM

One thought on “Job sequencing problem

Leave a Reply

Your email address will not be published.