Category Archives: Appendix: Sequencing and Scheduling

Sequencing to Minimize Weighted Tardiness

Happy New Year, everyone!  I just checked ahead in the appendix, and at my current pace of about 1 problem a week, we should get through appendices A5 (Sequencing and Scheduling), A6 (Mathematical Programming), and possibly A7 (Algebra and Number Theory) this year.  The appendix goes through A12, so it looks like I have plenty of work ahead of me.

The problem: Sequencing to Minimize Weighted Tardiness.  This is problem SS5 in the appendix.

The description: Given a set T of tasks, each task t  has a length l(t), a weight w(t) (which is really a penalty for finishing a task late) and a deadline d(t), and a positive integer K.  Is there a one-processor schedule for all tasks in T where each task is penalized by w(t) for each time unit it goes beyond its deadline, such that the total penalty is K or less?

Example: Suppose I have 3 tasks:

Task Length Deadine Weight
1 3 3 100
2 1 4 3
3 2 4 1

If task 1 is going to not miss its deadline, it needs to start right away.  Since the weight penalty for missing the deadline is pretty disastrous, we should do that.

At time 3, when task 1 is done, we have a choice: Schedule task 2, and have task 2 finish 2 time units late, or schedule task 3, have it finish just 1 time unit late and schedule task 2 afterward.  With these weights, scheduling task 2 first gives a penalty of 2 (task 3 finishes 2 time units late, for a penalty of 1, and 1×2=2).  The other plan would have a penalty of 7 (Task 3 finishes 1 unit late, and task 2 finishes 2 units late).

If the weight of task 2 was 1, and the weight of task 3 was 5, then scheduling task 2 first gives a penalty of 10, but scheduling task 3 first gives a penalty of 6.

Reduction: G&J reference a paper by Lawler, which itself references G&J.  Weird.   Anyway, they reduce from 3-Partition.  Given a 3-Partition instance (a set of 3n elements, and a bound B.  Each element is between B/4 and B/2, and the sum of all elements is m*B), we create 4n jobs.  3n of them will be “A” jobs, each one corresponding to an element in the 3-Partition instance.  We will also have n “X” jobs.

Each “A” job Ai corresponds to an element in the 3-partition instance ai.  These jobs have weight and length B+ai and deadline 0.

The X jobs all have processing time 16B2+n(n+1)/2 + 1.  Call this number L.  The X jobs have weight (L+4B)*(4B)*n(n+1)/2 + 1.  Call this number W. Each X job Xi has deadline iL+(i-1)*4B.    Notice that these X jobs don’t depend on the values in the partition instance at all (they do depend on the size).

Our K value is W-1.

If the original set has a partition, then we can make a schedule of: X1 then the A jobs corresponding to a 3 element partition, then X2, then another set of 3 A jobs corresponding to another 3 element partition, and so on down.  Since we know the  3 elements in a partition sum to exactly B, we know that the processing time of each set of 3 A jobs is exactly 4B.  So each X job will finish at time i*L+(i-1)*4B, and not be tardy.  The A jobs all have deadline 0 and will all be tardy and will pay penalties related to their completion times, but that will sum to less than K.

In the other direction, suppose that we have a legal schedule.  Since all of the X jobs have weight > K, they all have to be scheduled before their deadlines.  Then we can talk about the weights and completion times that the A jobs need to have to fit around these X jobs.  It’s a lot of algebra to make it all work out, but the math isn’t too hard.

Difficulty: 7.  While the algebra is followable, the idea that you’d need to come up with these numbers in the first place is a hard one- I know they’re picked because they “work”, but I feel like there must be an easier way.

Scheduling to Minimize Weighted Completion Time

There probably will not be a post next week, since I won’t be at work over the holidays.  See you when I get back!

The problem: Sequencing to Minimize Weighted Completion Time.  This is problem SS4 in the appendix.

The description: Given a set T of tasks, and a partial order  \lessdot  on each task.  Each task t \in T has a length l(t) and a weight w(t).  We’re also given a positive integer K.  Can we find a one-processor schedule for T that obeys the precedence rules (so if a \lessdot b, then a is scheduled before b), and the sum of the completion time of each task * the weight of that task is K or less?

Example: Suppose we had 3 tasks:

Task Length Weight
1 2 4
2 3 3
3 4 1

Suppose the only ordering constraint was that 1 had to be scheduled before 2.  Then scheudling 1 first, then 2 seconds, then 3 third gives the following weights:

  • 1 is finished at time 2, so gives weight 8
  • 2 is finished at time 5, so gives  weight 15
  • 3 is finished at time 14, so gives weight 14.

..for total weight 37

If we also add a constraint that 3 had to be scheduled before 2, then there are only 2 feasible schedules (1,3,2) and (3,1,2).  The (1,3,2) schedule has a total weight of  41, and the (3,1,2) schedule gives a total weight of 55.

Reduction: The paper by Lawler reduces from Optimal Linear Arrangement.  So we start with an undirected graph.  Each vertex becomes a task with processing time 1 and weight 0.  Each edge gets an  “in” job with processing time 0 and weight -1, and an “out” job with processing time 0 and weight 1.   The “in” job has to come before the vertex it is going in to and the “out” job has to come afterward.

Recall OLA asks: Can we find an ordering of each vertex where  f(v) is the position of vertex v, such that:

The construction of the tasks gives us the same weighting for the “in” and “out” tasks for each edge (the “out” task contributes f(v) to the total, and the “in” task subtracts f(u) from it).  The only problem is that we should have positive lengths of jobs.

So let the in and out tasks take time 1, and vertices take time |V^4|.  Next, we can replace each vertex task with |V^4| tasks each of time 1, each linked in a precedence chain.  Once that happens, we can increase the weights of all tasks by the same amount and not change the problem.

Difficulty: I think the first part is difficulty 4.  Once you do the tricks with the numberings, it probably becomes a 6.

Sequencing to Minimize Tardy Tasks, Sequencing to Minimize Tardy Task Weight

I don’t want to constantly restate reductions that are done in the G&J book, so I’ll just state that problem SS2, “Sequencing to Minimize Tardy Tasks” is done in G&J on page 73.

The next problem has a very similar title, but is a pretty different problem:

The problem: Sequencing to Minimize Tardy Task Weight.  This is problem SS3 in the appendix.

The description: Given a set  T of tasks, each with a length, a deadline, and a weight (think “penalty”), and an integer K, can we find a one-processor schedule for T such that the sum of the weights of the tasks that are not completed before their deadline is K or less?

Example: Here’s a pretty simple example to show what the hard decision is:

Task Length Deadline Weight
1 1 1 3
2 2 3 4
3 3 3 5

Obviously, we can only do either task 3, or both of task 1 and 2.  The current weights favor doing tasks 1 and 2 (because we want to make the weights of missed tasks small), but changing the weight values can change the decision.

Reduction: This is done in Karp’s paper.  We reduce from Partition. Let S be the set we are trying to Partition.   We’ll have a task for each element in the S.  The length of each task and its weight will be equal to the size of the element in S.  K = half of the sum of all of the elements in S.   The deadline for all tasks is also K.

Notice that the only way to get total weight K (or less) after the deadline is to get total length K (or more) done before the deadline.  We can’t do more than K length before the deadline (since the deadline is K). So the only way to have a feasible schedule is to have a set of tasks whose lengths are exactly K, which is a partition.

Difficulty: 3.  I think this is a little easier than last week’s since you don’t have to make up that boundary task in the middle.  Still, going from one set of things (the elements in S) to 3 values (length, deadline, and weight) gives opportunities for confusion.

Sequencing With Release Times and Deadlines

On to a new section!  This is the “Sequencing and Scheduling” section of the appendix.  The first problem is a bit weird because I think it appears with a differnt name elsewhere in G&J.

The problem: Sequencing with Release Times and Deadlines.  This is problem SS1 in the appendix.

Description: Given a set of tasks, where each task t has a “release time” r(t), a “deadline” d(t), and a length(t), all positive integers, can we create a one-processor feasible schedule for these tasks that meets all deadlines?

The definition of “feasible” is pretty straightforward:

  • No task can start before its release time.
  • No two tasks can be running at the same time (and there is no preemption, so once a task starts running, it must complete)
  • All tasks finish before (or equal to) their deadline.

Example: Here’s an example that will relate to the reduction:

Suppose I have 5 tasks: The first 4 tasks are similar: All of them start at time 1, all of them have a deadline at time 11, and the lengths are 1,2,3, and 4.  Our fifth task starts at time 5, has a length of 1, and a deadline of 6.  (So every feasible schedule must have this task own the processor between times 5 and 6)

A feasible schedule would be: {1,4,5,2,3}.  5 minutes of tasks before the 5th task, then 5 minutes of tasks afterward.

Reduction: Like I said above, I think this equivalent to the G&J “Sequencing Within Intervals” problem- at least I can’t see a difference.  The reduction for that problem is on page 70 of the G&J book, and it’s pretty elegant.

We reduce from Partition.  Let B = the sum of all elements in the Partition instance.  Each element in the set will become a task with starting time 1, deadline B+1, and a length equal to the value of the set element.  We have one extra task that is released at time B/2, has a length of 1, and a deadline of B/2 + 1 (this is like our 5th task in the example above).

The idea is that the only way to fit all of the tasks feasibly is to have some subset of the tasks start at time 1 and take (collectively) exactly B/2 time, then we have our 1 extra task, then we fill the time from B/2+1 to B+1 with the rest of the tasks (which also take collectively exactly B/2+1 time).  This forms a partition of B.

Difficulty: 3.  I think this is a good reduction students can come up with on their own.  I like the slickness of the extra element to force the partition.  If the problem we’re talking about is actually different than the one done in G&J, we’d have to see just where the differences lie.