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

Input: Four Jobs with following deadlines and profits
JobID Deadline Profit
a 4 20
b 1 10
c 1 40  
d 1 30
Output: Following is maximum profit sequence of jobs
c, a

Input: Five Jobs with following deadlines and profits
JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
Output: Following is maximum profit sequence of jobs
c, a, e

Defination with C++ Implemetation

A Simple Solution is to generate all subsets of given set of jobs and check individual subset for feasibility of jobs in that subset. Keep track of maximum profit among all feasible subsets. The time complexity of this solution is exponential.

This is a standard Greedy Algorithm problem. Following is algorithm.

1) Sort all jobs in decreasing order of profit.
2) Initialize the result sequence as first job in sorted jobs.
3) Do following for remaining n-1 jobs
.......a) If the current job can fit in the current result sequence
without missing the deadline, add current job to the result.
Else ignore the current job.
The Following is C++ implementation of above algorithm.

// Program to find the maximum profit job sequence from a given array
// of jobs with deadlines and profits
#include<iostream>
#include<algorithm>
using namespace std;

// A structure to represent a job
struct Job
{
char id; // Job Id
int dead; // 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 comparison(Job a, Job b)
{
return (a.profit > b.profit);
}

// Returns minimum number of platforms reqquired
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to decreasing order of prfit
sort(arr, arr+n, comparison);

int result[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots

// Initialize all slots to be free
for (int i=0; i<n; i++)
slot[i] = false;

// Iterate through all given 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, arr[i].dead)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}

// Print the result
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}

// Driver program to test methods
int main()
{
Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},
{'d', 1, 25}, {'e', 3, 15}};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Following is maximum profit sequence of jobsn";
printJobScheduling(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.