Monthly Archives: December 2017

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:

https://npcomplete.owu.edu/wp-content/uploads/sites/109/2015/03/OLA-equation1.png

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.