Tag Archives: Optimal Linear Arrangement

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.

Protected: Consecutive Ones Matrix Augmentation

This content is password protected. To view it please enter your password below:

Protected: Quadratic Assignment Problem

This content is password protected. To view it please enter your password below:

Protected: Rooted Tree Arrangement

This content is password protected. To view it please enter your password below:

Protected: Directed Optimal Linear Arrangement

This content is password protected. To view it please enter your password below:

Protected: Interval Graph Completion

This content is password protected. To view it please enter your password below:

Protected: Optimal Linear Arrangement

This content is password protected. To view it please enter your password below: