Exercises going beyond
This chapter presents a set of exercises related to Chapter 8. The main focus
is on approximation results (Section 9.1), and there are also exercises deal-
ing with linear programming, randomized algorithms, and branch-and-bound
techniques (Section 9.2). Solutions are provided in Section 9.3.
9.1 Approximation results
Exercise 9.1: Single machine scheduling (solution p. 219)
We have n independent tasks, T
, . . . , T
, to execute on a single computer. For
any 1 j n, the execution time of task T
and task T
to the system at time r
. In other words, the processing of task T
start earlier than time r
. We denote by C
the completion time of t ask T
that is, the time at which its processing completes. We assume th at w
positive integer and r
is a nonnegative integer.
The objective function is the sum of the completion times: S =
1. We assume in this question that tasks can be preempted (we explain
below in detail what preemption is). P rove that in this framework the
optimal solution is obtained by scheduling during each interval [i; i + 1],
for any nonnegative integer i, the task whose remaining processing time
is the smallest. This scheduling algor ithm is called Shortest Remaining
Processing Time ﬁrst, or SRPT.
To explain preemption, let us consider a task T
that is executed
during the time interval [i; i + 1] (where i is some integer) and whose
processing has not completed at time i + 1. We allow another task T
(with j = k) to be processed during the time interval [i + 1; i + 2].
The execution of task T
will eventually be resumed. The sum of the
durations of the time intervals d uri ng which T
is executed is equal to
; when the execution of T
resumes after a preemption, it restarts
from where it was interrupted.
© 2014 by Taylor & Francis Group, LLC