Problem Statement 1
Task 1: Implementation of job sequencing with deadlines using Branch and
Bound
1. Design a state-space tree where each node represents a partial selection
of jobs for a job sequencing with deadlines problem with number of jobs:
n = 5; Profit: (p1, p2, p3, p4, p5) = (6, 3, 4, 8, 5); Deadline: (d1, d2, d3,
d4, d5) = (3, 1, 4, 2, 4). Each job requires one unit of processing time.
2. Define:
a. Branching rule (selecting or rejecting a job)
b. Bounding function to compute an upper bound on achievable profit
3. Use the bound to prune non-promising nodes.
4. Implement the algorithm in C++.
Input Format: Output Format:
n Maximum Profit
p[1..n] // profits Selected Job Sequence
d[1..n] // deadlines
Sample Input Sample Output
5 //instances Maximum Profit = 23
6 3 4 8 5 //profits Selected Jobs (Time Slot : Job ID)
3 1 4 2 4 //deadlines Slot 1 : Job 3
Slot 2 : Job 4
Slot 3 : Job 1
Slot 4 : Job 5
Algorithm:
Algorithm JS(d,j,n)//d[I]>=1,1<=I<=n are the deadlines, n>=1 the jobs are ordered such that
p[1]>=p[2]>=………..>=p[n]. J[i] is the ith job in the optimal solution, 1<=I<=k. also at termination
d[J[i]]<=d[J[i+1]],1<=I<k.
{
d[0]:=J[0]:=0//initialize
J[1]:=k:=1;
For I:=2 to n do{ //consider jobs in nonincreasing order of p[i]. Find position for i and check
feasibility of insertion.
r:=k;
While((d[J[r]]>d[i])and (d[J[r]]!=r]]!=r)) do r:=r-1;
If((d[J[r]]<=d[i]) and (d[i]>r)then{//insert into J[] for q:=k to (r+1) step-1 do J[q+1]:=J[q];
J[r+1]:=i;
k:=k+1;
}}
Return k;
}
Code:
#include<bits/stdc++.h>
using namespace std;
#define MAX 20
int JS(int d[],int J[],int n){
d[0]=J[0]=0;
J[1]=1;
int k,r,q;
k=1;
for(int i=2;i<=n;i++){
r=k;
while((d[J[r]]>d[i]) && (d[J[r]]!=r)) r--;
if((d[J[r]]<=d[i]) and (d[i]>r)){
for(q=k;k>=r+1;q--) J[q+1]=J[q];
J[r+1]=i;
k++;
}
}
return k;
}
int main(){
int n;
int d[MAX],p[MAX],J[MAX];
int totalProfit=0;
cout<<"Enter number of jobs: ";
cin>>n;
cout<<"Enter profits: "<<endl;
for(int i=1;i<=n;i++)cin>>p[i];
cout<<"Enter deadlines: "<<endl;
for(int i=1;i<=n;i++)cin>>d[i];
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (p[j] > p[i]) {
swap(p[i], p[j]);
swap(d[i], d[j]);
}
}
}
int k=JS(d,J,n);
for(int i=1;i<=k;i++){
totalProfit+=p[J[i]];
}
cout<<"Maximum Profit= "<<totalProfit<<endl;
cout<<"Selected Jobs"<<endl;
for(int i=1;i<=k;i++){
cout<<"slot "<<i<<" : Job "<<J[i]<<endl;
}
}
Output:
Task 2: Input Size vs Time Analysis
[Link] job instances of different sizes (for example: n = 10, 20,
30, 40, 50) with corresponding profit and deadline vectors.
[Link] the execution time of your Branch and Bound algorithm for each input
size.
[Link] the results showing:
a. Number of jobs (n)
b. Execution time
5. Plot and analyze how execution time grows with increasing input size.
Code:
#include <bits/stdc++.h>
using namespace std;
#define MAX 200
int JS(int d[], int J[], int n) {
d[0] = J[0] = 0;
J[1] = 1;
int k = 1, r, q;
for (int i = 2; i <= n; i++) {
r = k;
while ((d[J[r]] > d[i]) && (d[J[r]] != r))
r--;
if ((d[J[r]] <= d[i]) && (d[i] > r)) {
for (q = k; q >= r + 1; q--)
J[q + 1] = J[q];
J[r + 1] = i;
k++;
}
}
return k;
}
int main() {
srand(time(0));
for (int n = 10; n <= 100; n += 10) {
int p[MAX], d[MAX], J[MAX];
for (int i = 1; i <= n; i++) {
p[i] = rand() % 100 + 1;
d[i] = rand() % n + 1;
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (p[j] > p[i]) {
swap(p[i], p[j]);
swap(d[i], d[j]);
}
}
}
clock_t start = clock();
int k = JS(d, J, n);
clock_t end = clock();
double time = double(end - start) / CLOCKS_PER_SEC;
cout << n << "\t" << fixed << setprecision(6) << time << endl;
}
return 0;
}
Output:
Size 10 20 30 40 50 60 70 80 90 100
Time(ms) 0.002 0.003 0.01 0.006 0.005 0.009 0.012 0.014 0.016 0.021
Problem Statement 2:
A cloud service provider receives multiple computational tasks from clients. Each task:
requires 1 unit of processing time
must be completed before a given deadline
provides a certain revenue upon successful completion
Due to limited resources, the server can execute only one task at a time. The
objective is to maximize total revenue while meeting all deadlines.
Code:
#include<bits/stdc++.h>
using namespace std;
#define MAX 20
int JS(int d[], int J[], int n) {
d[0] = J[0] = 0;
J[1] = 1;
int k = 1, r, q;
for (int i = 2; i <= n; i++) {
r = k;
while ((d[J[r]] > d[i]) && (d[J[r]] != r))
r--;
if ((d[J[r]] <= d[i]) && (d[i] > r)) {
for (q = k; q >= r + 1; q--)
J[q + 1] = J[q];
J[r + 1] = i;
k++;
}}
return k;
}
int main() {
int n;
int d[MAX], p[MAX], J[MAX];
int totalRevenue = 0;
cout << "Enter number of tasks: ";
cin >> n;
cout << "Enter revenues of tasks:\n";
for (int i = 1; i <= n; i++)
cin >> p[i];
cout << "Enter deadlines of tasks:\n";
for (int i = 1; i <= n; i++)
cin >> d[i];
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (p[j] > p[i]) {
swap(p[i], p[j]);
swap(d[i], d[j]);
}
}}
int k = JS(d, J, n);
for (int i = 1; i <= k; i++)
totalRevenue += p[J[i]];
cout << "Total Revenue Earned = " << totalRevenue << endl;
cout << "\nSelected Tasks (Execution Order):\n";
for (int i = 1; i <= k; i++) {
cout << "Slot " << i << " : Task " << J[i] << endl;
}
return 0;
}
Output: