Job Sequencing Problem using Greedy method in Python
By Saumitra DeshpandeIn this blog, we are going to see how we can solve the Job Sequencing Problem using the greedy method in Python.
We are going to do this in Python language.
An array of jobs is given where every job has an associated profit.
The job has a deadline.
1 is the max deadline for any given job.
This is so because each takes only a single unit of time.
The following is the Greedy Algorithm,
1) Jobs are to be sorted in a decreased order of profit.
2) Repetition is done on jobs as per the decrease in profit value.
For each job:
a) A time slot is selected, such that the slot is empty.
It also has to be lesser than the given deadline.
Now the job is placed in that slot.
Then it is marked as a filled slot.
b)The job is ignored if no such time is found to exists.
Input:
JobId Deadline Profit
a 7 202
b 5 29
c 6 84
d 1 75
e 2 43
Output:
Maximum profit sequence of job is a, c, d
Python program: Job Sequencing Problem using Greedy method
# Job sequence
# Function to schedule the jobs
def printjobschedule(array, t):
m = len(array)
# Sort all jobs accordingly
for j in range(m):
for q in range(m - 1 - j):
if array[q][2] < array[q + 1][2]:
array[q], array[q + 1] = array[q + 1], array[q]
res = [False] * t
# To store result
job = ['-1'] * t
for q in range(len(array)):
# Find a free slot
for q in range(min(t - 1, array[q][1] - 1), -1, -1):
if res[q] is False:
res[q] = True
job[q] = array[q][0]
break
# print
print(job)
# Driver
array = [['a', 7, 202],
['b', 5, 29],
['c', 6, 84],
['d', 1, 75],
['e', 2, 43]]
print("Maximum profit sequence of jobs is- ")
printjobschedule(array, 3)
Output
Also read: Python program to solve Quadratic equation
def printjobschedule(array, t):
m = len(array)
for i in range(m):
for j in range(m – 1 – i):
if array[j][2] < array[j + 1][2]:
array[j], array[j + 1] = array[j + 1], array[j]
res = [False] * t
job = ['-1'] * t
for i in range(len(array)):
for j in range(min(t – 1, array[i][1] – 1), -1, -1):
if res[j] is False:
res[j] = True
job[j] = array[i][0]
break
print(job)
array = [['j1', 2, 60],
['j2', 1, 100],
['j3', 3, 20],
['j4', 2, 40],
['j5', 1, 20]]
print("Maximum profit sequence of jobs is- ")
printjobschedule(array, 3)