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 on each task. Each task t 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 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:
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 ||. Next, we can replace each vertex task with || 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.