Sorry for skipping last week. I got about halfway through the post for the next problem, but forgot that the reduction went through this other problem instead, and then ran out of time to fix it.

**The problem: **Single Execution Time Scheduling. This problem is not in the appendix and is problem “P4” in the paper by Ullman that has this reduction and the problem next week.

**The description: **Given a set S of N jobs, arranged in a partial order, each taking 1 time unit, a deadline D, and a sequence of D “processor slots” arranged in a sequence from 0 to D-1, where the sum of all of the processor slots is exactly N, can we create a feasible schedule for all tasks that respects the partial order?

**Example: **Here’s a simple example of a partial order:

If D=3 and the processor slot sequence was {1,2,1}, then this can be solved: schedule a at time 0, b and c at time 1, and d at time 2. (So d is done by time 3).

If the processor slot sequence was {1.1.2}, then at time 1, we can only schedule 1 of b and c, so we won’t be able to schedule d at time 2.

**Reduction: **The Ullman paper goes from 3SAT. The original formula will have m variables and n clauses. We will create jobs:

- x
_{ij}and ~x_{ij}where i goes from 1 to m and j goes from 0 to m. - y
_{i}and ~y_{i}where i goes from 1 to m - D
_{ij}where i goes from 1 to n and j goes from 1 to 7.

The partial order on these jobs is:

- Each x
_{ij}comes before x_{i,j+1}and each ~x_{ij}comes before ~x_{i,j+1} - Each x
_{i,i-1}comes before y_{i}and each ~x_{i,i-1}comes before ~y_{i} - For each D
_{ij}represent the j index as a binary number (from 1 to 7). The three literals in clause i also have 7 combinations of ways to set their literals to make the clause true, which can also be represented as a binary number. Then for each binary combination, look at the positive or negative settings of the literals that make that combination true. Then take the*last*of the x (or ~x) jobs of the variables corresponding to those literals and make it come before the D_{i}job. So if we are considering job x_{k}, we’d make x_{km}come before the D_{i}job we’re looking at.

That last thing is just a way of saying “there are 7 ways of making the clause true, you need to execute the job of the literals that makes the clause true before you do the clause job.”

The deadline is n+3. The processor slots have:

- m slots at time 0
- 2m+1 slots at time 1
- 2m+2 slots at times 2-m
- n+m+1 slots at time m+1
- 6n slots at timem+2

The idea is that at time 0 we need to run one of either x_{i0} or ~x_{i0} for each i. (The other is run at time 1). These will correspond to whether variable i is set t true or false. We need to do that because we need to run the y jobs as soon as they become available (y_{0} or ~y_{0} – whichever is the same parity as the x variable we ran in time 1- needs to be run at time 1, and so on down). At time 1, we run either x_{i1} of ~x_{i1}, depending on what we do at time 0. So at time m+1, we have one y job left over (the last of the y’s in the sequence we started late), m x jobs left over (the x_{im} or ~x_{im} corresponding to the variable we started at time 1), and hopefully have enough x jobs finished to be able to run n D jobs (one for each clause). This is the way you’ll satisfy each clause. Then at time m+2, everything is done except for the other 6n D jobs.

**Difficulty: **7. I think Ullman does a very good job of explaining his method, which actually obscures a bit how complex this reduction is, and all of the moving parts and algebra going on.