This project implements the Branch and Bound algorithm to Visualize and to solve the Job Sequencing Problem, a classic optimization problem in computer science and operations research. The Job Sequencing Problem involves scheduling a job to a employee to minimize a total completion time.
Given a set of jobs and a set of workers(employees) in form of matrix which cell show the completion time of a job by a worker. The objective is to schedule the jobs to a unemployeed worker in way that minimize the total compltion time. Each worker do only one job.
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
Node* par; //for print solution
int cost; //actual cost + estimate cost
int job;
int emp;
int pathcost; //actual cost
vector<bool> assign;
Node(Node* p, int j, int e, vector<bool> a, int n){
par=p;
job=j;
emp=e;
assign=a;
}
};
class Compare{
public:
bool operator()(Node* l, Node* r){
return l->cost > r->cost;
}
};
int clac_cost(int **t, int job, int emp, vector<bool> assign, int n){
int cost=0, i, j;
for(i=emp+1; i<n; i++){
int min=1e9;
for(j=0; j<n; j++){
if(!assign[j] && t[i][j]<min){
min=t[i][j];
}
}
cost+=min;
}
return cost;
}
void print(Node* min){
if(min->par == NULL)
return;
print(min->par);
cout<<"Employee "<<min->emp +1 <<" have Job "<<min->job +1<<"."<<endl;
}
int main(){
int n, i, j;
cin>>n;
int **t=new int*[n];
for(i=0; i<n; i++)
{
t[i]=new int[n];
for(j=0; j<n; j++)
cin>>t[i][j];
}
priority_queue<Node*, vector<Node*>, Compare> pq;
vector<bool> assign(n, false);
Node* root=new Node(NULL, -1, -1, assign, n);
root->cost=root->pathcost=0;
pq.push(root);
while(!pq.empty()){
Node* min=pq.top();
pq.pop();
int i=min->emp + 1;
if(i==n){
print(min);
cout<<endl<<min->cost;
exit(0);
}
int j;
for(j=0; j<n; j++){
if(!min->assign[j]){
vector<bool> new_assign = min->assign;
new_assign[j] = true;
Node* child=new Node(min, j, i, new_assign, n);
child->pathcost=min->pathcost + t[i][j];
child->cost = child->pathcost + clac_cost(t, j, i, new_assign, n);
pq.push(child);
}
}
}
}
Given 2D Matrix's dimensions is worker * job. Input
4
11 12 18 40
14 15 13 22
11 17 19 23
17 14 20 28
Output
Employee 1 have Job 1.
Employee 2 have Job 3.
Employee 3 have Job 4.
Employee 4 have Job 2.
61
Here 11 + 13 + 23 + 14 = 61 is result by shown in output.
Vrund Dobariya...... https://github.com/VGD3626
Kishan Dervaliya.... https://github.com/Kdenius
Divyang Dhameliya... https://github.com/Divyang029
Yug Vithani......... https://github.com/yugvithani