Job Sequencing Problem using Greedy method in Python

By Saumitra Deshpande

In 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