If there are two different schedules which have neither inversions nor idle time, then they might differ by the order in which the requests are scheduled in them. Here as the slack time of t 2 is smaller than t 1 (0 d j and i is scheduled before j and Idle time is the time lag when the resource is not working yet there are requests which need to be scheduled. This do works in the above scenario though. A solution could be considering the difference between the deadline and its processing time to choose a request(i.e., slack time) and adding requests with increasing slack time. Minimum Slack Time FirstĬoming to the next strategy, we would like to consider the deadlines while scheduling. You can clearly see that according to this strategy, we will choose t 1 instead of t 2 due to its lesser processing time but t 2 will miss its deadline this way contributing towards a positive lateness which could have been 0 if we scheduled t 2 before t 1 (refer to the image above). Yes, it won't work for us! It doesn't consider the deadlines of requests and this is where it looses the sprint.
With a little thought, one could claim a strategy which sorts the Processing time in ascending order will give us optimal solution since this way, we would be able to finish the smaller requests quickly. Hence, we will now see if we could get an efficient greedy algorithm for our problem. Needless to say, there would be many greedy approaches that will give optimal solution in certain situations but our task is to find one that will work in every situation.
Greedy StrategiesĪ Greedy Algorithm works in stages and at every stage, it makes the best local choice depending on the past ones and assures to give a globally optimal solution.
FILE MINIMIZER ALGORITHM HOW TO
In above example, we could intuitively see the solution but how to proceed when n is sufficiently large? Here comes the need to define an Algorithm that will give the expected solution in almost every situation. In this case, since every request managed to finish before its deadline, the lateness of every request is 0 and hence the maximum lateness is also 0, which is minimum. We could schedule the requests in many ways but we choose the shown solution since it fulfills our motive to complete all the requests within the assigned deadlines. We are interested to find a schedule such that the maximum lateness (max(l i*) where i ∈ ) is minimized.Ĭonsider below example, we are given 3 requests(i=3) along with the time required to complete each one( t i) and their respective deadlines( d i). If a request finishes before its deadline, we consider its lateness( l i) to be zero and f i - d i otherwise. We claim a request i to be late if f i > d i. We are willing to schedule maximum requests before their respective deadlines or at least in a way to decrease the time lag in finish time and deadline of the chosen request (i.e., lateness).
Also, one must note that since we are scheduling the requests on one resource, we could find the starting(s i) and finishing time(f i) of each by the relation f i = s i + t i. Each request i must be assigned an interval of time t i which must not overlap with other accepted requests. Each request i has a deadline d i and time required to finish the request t i. According to the problem, We have a single resource and a set of n requests to use the resource for an interval of time. We will look into one such problem where greedy proves its worth.
0 kommentar(er)
