Write a program in python, c++ or java that use\'s a greedy algorithm or a hill
ID: 3599042 • Letter: W
Question
Write a program in python, c++ or java that use's a greedy algorithm or a hill climber in order to solve the Job shop scheduling problem The problem is as follows, JOB-SHOP SCHEDULING: Given a collection of stations, each of which performs a particular task, and a collection of jobs, each of which requires a sequence of operations of various lengths at some of the stations, find a schedule---an assignment of operations to stations that satisfies all the tasks' sequence requirements---that minimizes the total time to complete all the tasks, called the "makespan". Note that there are versions of this problem.
Explanation / Answer
#include<iostream>
using namespace std;
int main() {
int t,n,max=0,i,d,job,max_p=0,c,k,max_profit,pos,count; //variable declaration
cin>>t; //t denotes the number of test cases
while(t--) {
max_profit=0,c=0,count=0;
cin>>n; //n is the number of jobs that has to be sequenced
int op[n],dl[n]; // op is set of operations and dl is the time taken by operations
for(i=1;i<=n;i++) {
cin>>op[i]>>dl[i]; //Input the set of operations and time
}
for(i=1;i<=n;i++) {
if(dl[i]>max)
max=dl[i];
}
d=max;int res[d]; //res is the sequence of jobs that are executed in minimum time span
for(i=1;i<=d;i++) {
res[i]=0;
}
// the following code is used to find the resultant job sequence
for(i=1;i<=d;i++) {
max_p=0;
for(k=1;k<=n;k++) {
if(op[k]>max_p) {
max_p=op[k];job=k;
}
}
pos=dl[job];
if(c<=d) {
if(res[pos]==0) {
res[pos]=job;
max_profit=max_profit+op[job];count++;
op[job]=0;c++;
}
else {
while(res[pos]!=0 && pos)
pos--;
if(pos>=1) {
res[pos]=job;
max_profit=max_profit+op[job];count++;
op[job]=0;c++;
}
else {
op[job]=0;i--;
}
}
}
}
for(i=1;i<=d;i++) {
cout<<res[i]<<" "; //resultant job sequence
}
cout<<endl;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.