Job Sequencing with Deadlines (ASP) – Greedy Method

Job Sequencing with deadlines
Spread the love

Job Sequencing with deadlines is an activity selection problem. Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. An optimization problem can be solved using Greedy if the problem has the following property: At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem

In this tutorial, I am going to show you how to solve a greedy problem. In this problem, Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

Read More : Implement Dijkstra Algorithm using Python- Single source path

Look at this image, we are going to find the maximum job sequence.

Algorithm of Job Sequcence

  • Sort the activities in ascending order according to their finishing order.
  • Select the first activity from the sorted list and print it
  • Do same task if the start time of this activity is greater than or equal to the finish time of previous activity

So according to this image, our output will be BECD. Why BECD? Well, Look at this sorted array, In this array the first activity is B then E. E’s start time is greater than the B. Then the next activity is A whose start time smaller than B, so we can’t print A according to our conditions. We do the same task repeatedly until the activity is ended.

Code of Job Sequencing with deadlines

def optimal_solution(list):
    print(list[0][2], end=" ")
    temp = list[0]
    for i in range(1, len(list)):
        if temp[1] <= list[i][0]:
            temp = list[i]
            print(list[i][2], end=" ")

The optimal solution method is the main function of this algorithm. Inside the function, first I print the first actively then store this activity in a temporary variable. After then I execute a loop, inside the loop I compared conditions according to our algorithm.

Full Code

def bubble_sort_asc(list):
    for i in range(0, len(list)):
        for j in range(i+1, len(list)):
            if list[i][1] > list[j][1]:
                list[i], list[j] = list[j], list[i]


def optimal_solution(list):
    print(list[0][2], end=" ")
    temp = list[0]
    for i in range(1, len(list)):
        if temp[1] <= list[i][0]:
            temp = list[i]
            print(list[i][2], end=" ")


activities = [
    (0, 6, "A"),
    (1, 2, "B"),
    (5, 7, "C"),
    (8, 9, "D"),
    (3, 4, "E"),
    (5, 9, "F"),
]

bubble_sort_asc(activities)
optimal_solution(activities)
Github : https://github.com/AR-Shahin

Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.