Earliest Due Date (EDD) Scheduling Algorithm Code in C++

If you’re a programmer and looking to learn about the EDD scheduling algorithm and how to implement it in C++, this blog post is for you. EDD stands for Earliest Due Date scheduling and is a way of prioritizing tasks based on their due date. It is an important technique for scheduling tasks in real-time systems. In this blog post, we will look at what EDD scheduling is, how it works, and how to implement it in C++. We will go through the steps of how to code it, including inputting task information, prioritizing tasks based on the due date, and outputting the schedule.

So let’s get started with a basic introduction to the EDD Scheduling Algorithm.

EDD Scheduling Algorithm

The Earliest Due Date (EDD) is a scheduling algorithm that assigns priority to tasks based on their due dates. All the tasks consist of a single job, having synchronous (same) arrival times, but have different computation or execution times and deadlines. Since in EDD, all tasks arrive at the same time hence there is no preemption of tasks.

The algorithm executes the tasks in order of increasing deadlines is optimal with respect to minimizing the maximum lateness.

Example

Consider a set of five tasks, all the tasks arrived at time t=0. The other parameters (computation and deadlines) are given in the table below.

If we find maximum lateness (Lmax) we get, -1 and that is due to J4, which completes a unit of time before its deadline. Since the maximum lateness is negative, we concluded that all the tasks have been completed within their deadlines.

EDD Implementation in C++

Here is the EDD scheduling algorithm code in C++ programming language.

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

const int MAX = 5;

struct EDD {
    int id;
    int ai;
    int ci;
    int di;
};
bool sortdeadline(EDD a, EDD b) {
    return a.di < b.di;
}
int main() {
    srand(time(NULL));
    cout << "**** EDD Algorithm ****" << endl;
    cout << endl;

    EDD e[MAX];

    //Get Tasks

    for (int i = 0; i < MAX; i++) {
        e[i].id = i + 1;
        e[i].ai = 0;

        cout << "Getting Computation for task " << i + 1 << "..." << endl;
        e[i].ci = 1 + (rand() % 3);

        cout << "Getting Deadline time for task " << i + 1 << "..." << endl;
        e[i].di = (5 + (rand() % 10)) + e[i].ci;

        cout << endl;

    }

    cout << endl;

    //showing output of tasks set
    cout << "___________________________________________" << endl;
    cout << "Tasks Set" << endl;
    cout << "___________________________________________" << endl;
    cout << "ID     Arrival      Execution      Deadline     " << endl;
    cout << "___________________________________________" << endl;
    for (int i = 0; i < MAX; i++) {
        cout << e[i].id << "            "
            << e[i].ai << "             "
            << e[i].ci << "            "
            << e[i].di << "           "
            << endl;
    }
    cout << "____________________________________________" << endl;

    sort(e, e + 5, sortdeadline);
    
    cout << endl;


    //showing output of tasks set after sorting
    
    cout << "Tasks Set after sorting" << endl;
    cout << "___________________________________________" << endl;
    cout << "ID     Arrival      Execution      Deadline     " << endl;
    cout << "___________________________________________" << endl;
    for (int i = 0; i < MAX; i++) {
        cout << e[i].id << "            "
            << e[i].ai << "             "
            << e[i].ci << "            "
            << e[i].di << "           "
            << endl;
    }
    cout << "____________________________________________" << endl;
    int time = 0;
    cout << endl;
    for (int i = 0; i < MAX; i++) {
        if (time + e[i].ci <= e[i].di) {
            cout << "Task " << e[i].id << " Executed from time " << time << " to " << time + e[i].ci << endl;
            time = time + e[i].ci;
        }
    }
    cout << "********************************************" << endl;
    cout << "All tasks executed successfully!" << endl;
    return 0;
}

Output

Code Explanation

• The program takes random values for computation (ci) and deadline (di) by using the built-in function rand(). Notice that by getting a random value for the deadline we have added ci (computation time) so that deadlines must be in increasing order.
• We’ve defined a Boolean function that sorts the tasks based on their deadlines.
• Declare a variable ‘time‘ and initialize with 0. This variable keeps track of the current time.
• Use a for loop to schedule the tasks one by one. In each iteration, check the tasks if they can be executed before their deadline. If it can, print the scheduling information and update the ‘time‘ to the end of the task.

Overall, this EDD scheduling algorithm code in C++ proved to be a feasible solution for scheduling tasks in a timely manner. It was able to meet all deadlines and minimize idle time, which can be beneficial for any organization or individual looking to complete projects efficiently. Additionally, the code is flexible and can be easily modified to suit different scheduling requirements.