16-4 Scheduling variations

Consider the following algorithm for the problem from Section 16.5 of scheduling unit-time tasks with deadlines and penalties. Let all \(n\) time slots be initially empty, where time slot \(i\) is the unit-length slot of time that finishes at time \(i\). We consider the tasks in order of monotonically decreasing penalty. When considering task \(a_j\), if there exists a time slot at or before \(a_j\)'s deadline \(d_j\) that is still empty, assign \(a_j\) to the latest such slot, filling it. If there is no such slot, assign task \(a_j\) to the latest of the as yet unfilled slots.

a. Argue that this algorithm always gives an optimal answer.

b. Use the fast disjoint-set forest presented in Section 21.3 to implement the algorithm efficiently. Assume that the set of input tasks has already been sorted into monotonically decreasing order by penalty. Analyze the running time of your implementation.

a. Let \(O\) be an optimal solution. If \(a_j\) is scheduled before its deadline, we can always swap it with whichever activity is scheduled at its deadline without changing the penalty. If it is scheduled after its deadline but \(a_j.deadline \le j\) then there must exist a task from among the first \(j\) with penalty less than that of \(a_j\) . We can then swap aj with this task to reduce the overall penalty incurred. Since \(O\) is optimal, this can't happen. Finally, if \(a_j\) is scheduled after its deadline and \(a_j.deadline > j\) we can swap \(a_j\) with any other late task without increasing the penalty incurred. Since the problem exhibits the greedy choice property as well, this greedy strategy always yields on optimal solution.

b. Assume that \(\text{MAKE-SET}(x)\) returns a pointer to the element \(x\) which is now it its own set. Our disjoint sets will be collections of elements which have been scheduled at contiguous times. We'll use this structure to quickly find the next available time to schedule a task. Store attributes \(x.low\) and \(x.high\) at the representative \(x\) of each disjoint set. This will give the earliest and latest time of a scheduled task in the block. Assume that \(\text{UNION}(x, y)\) maintains this attribute. This can be done in constant time, so it won't affect the asymptotics. Note that the attribute is well-defined under the union operation because we only union two blocks if they are contiguous.

Without loss of generality we may assume that task \(a_1\) has the greatest penalty, task \(a_2\) has the second greatest penalty, and so on, and they are given to us in the form of an array \(A\) where \(A[i] = a_i\). We will maintain an array \(D\) such that \(D[i]\) contains a pointer to the task with deadline \(i\). We may assume that the size of \(D\) is at most \(n\), since a task with deadline later than \(n\) can't possibly be scheduled on time. There are at most \(3n\) total \(\text{MAKE-SET}\), \(\text{UNION}\), and \(\text{FIND-SET}\) operations, each of which occur at most \(n\) times, so by Theorem 21.14 the runtime is \(O(n\alpha(n))\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

SCHEDULING-VARIATIONS(A)
    let D[1..n] be a new array
    for i = 1 to n
        a[i].time = a[i].deadline
        if D[a[i].deadline] != NIL
            y = FIND-SET(D[a[i].deadline])
            a[i].time = y.low - 1
        x = MAKE-SET(a[i])
        D[a[i].time] = x
        x.low = x.high = a[i].time
        if D[a[i].time - 1] != NIL
            UNION(D[a[i].time - 1], D[a[i].time])
        if D[a[i].time + 1] != NIL
            UNION(D[a[i].time], D[a[i].time + 1])

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用