Write a program in python, c++ or java that use\'s a greedy algorithm or a hill

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: Job shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science and operations research in which ideal jobs are assigned to resources at particular times. The most basic version is as follows: We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing)

Explanation / Answer

#include<iostream>
#include<algorithm>
using namespace std;

// A structure to represent a job
struct Job_scheduling
{
char ID; // Job Id
int makespan; // Deadline of job
int profit; // Profit if job is over before or on deadline
};

// This function is used for sorting all jobs according to profit
bool compare_two_job(Job_scheduling a, Job_scheduling b)
{
return (a.profit > b.profit);
}

// Returns job schedule
void Job_Scheduling_display(Job_scheduling a[], int n)
{
// Sort all jobs according to decreasing order of prfit
sort(a, a+n, compare_two_job);

int result[n]; // Sequence of jobs
bool slot[n]; // track free time slots

// Initializing slots
for (int i=0; i<n; i++)
slot[i] = false;

// Iterate through all jobs
for (int i=0; i<n; i++)
{
// Find a free slot for this job (Note that we start
// from the last possible slot)
for (int j=min(n, a[i].makespan)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add job to result
slot[j] = true; // slot occupied
break;
}
}
}

// Print the schedule job on screen
for (int i=0; i<n; i++)
if (slot[i])
cout << a[result[i]].ID << " ";
}

// Driver program to test methods
int main()
{
Job_scheduling arr[] = { {'a', 2, 100}, {'b', 3, 190}, {'c', 1, 127},
{'d', 1, 10}, {'e', 3, 1}};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Job must be sechudule as: ";
Job_Scheduling_display(arr, n);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.