Search code examples
algorithmdata-structuresgreedy

Preemptive task scheduling in C

I have a list of tasks which have 3 parameters to be taken into account while scheduling: release time, duration and deadline.

Release time is the earliest possible start time of the task. Duration is the amount of time taken for the execution of the task. Deadline is the latest possible finish time of the task.

For example, the input is:

4  
2   3   5  
4   2   8  
1   2   6  
6   4   11

This means that there are 4 tasks, as indicated by the first line. From the next line onward, the first column is the release time, second column is duration and third column is deadline for each task.

The way to schedule these tasks would be:

Time    Task

1-2     3
2-5     1
5-6     3
6-8     2
8-12    4 <--- Deadline Violation

The goal is to write an algorithm to schedule tasks so that the number of deadline violations is minimised.

So, for the above case we must have an output:

1   2   3
2   5   1
5   6   3
6   8   2
8   12  4

where the first column is start times, second column is end times and third column is task number.

I think we need to use a greedy algorithm for this purpose, yet I am not entirely sure.

Therefore, I'm looking for possible algorithms/approaches to solve this problem.

Solution

  • In scheduling theory, your problem can be expressed with the following notation: 

    1|r_j|sum(U_j)

    (You can have a look at this wikipage for more explanations on the notation)

    According to this website, your problem is NP-hard since for example 1|r_j|L_max is NP-hard.

    It means that you cannot find a greedy algorithm that will solve your problem in polynomial time (unless P=NP, which is a one-million dollar open question, but no one really believes in it).