CO 454 Midterm 1 flashcards

University of Waterloo CO 454

$$p_j$$

Processing time for job $j$

$$d_j$$

Due date for job $j$

$$C_j$$

Completion time for job $j$

$$C_{max}$$

Makespan, i.e. completion time of last job

$$r_j$$

release time (earliest starting time)

$$w_j$$

Weight of job $j$

Preemption

the scheduler is allowed to interrupt the processing of a job (preempt) at any point in time and put a different job on the machine instead

Three field notation $\alpha | \beta | \gamma$

$\alpha$ Machine environment (e.g. number of machines

$\beta$ job characteristics and side constraints (e.g. precedence constraints, routing constraints, etc. Note: can be empty

$\gamma$ objective criterion to be minimized

Routing constraint

In a job shop, each job $ is proccesed by a subset of the machines, in a specific sequence.
In a job shop, each machine has it's own routing constraint

Precedence constraint

Some job $i$ must be completed before some job $j$ can be processed. The precedence constraints of a valid set of jobs is represented by a DAG.

Non-delay/greedy schedule

no machine is kept idle while a task is waiting for processing (i.e. kept idle while a job is available to run on that idle machine)

Unforced idleness

A time interval when there exists an idle machine $M$ as well as a job $j$ that can run on $M$.
note: this is not referring to waiting for release dates

Non-delay property

No non-delay schedule has unforced idleness

What is the optimal approach for $1|| \sum C_j$? How is this proved?

SPT (shortest processing time first). Proven with an exchange argument, here it was Adjacent Pairwise Exchange.

Give the general format for exchange arguments in this course (largely for schedule optimality)

1. Establish an optimal adversary sequence that doesn’t follow your rule.

2. Establish a reference sequence that swaps 2 jobs in the adversary sequence

   1. Often we just use adjacent jobs, using API (Adjacent Pairwise Exchange)

3. Do some calculations on the sequence (adjusting for the due date changes, lateness, whatever) and show that the reference sequence is at least as good as or strictly better (depending on the problem) than the adversary. Contradiction.

Regular objective function $\gamma$

Monotonically increasing (non-decreasing) with respect to completion times

Describe the optimal approach for $1 || \sum w_j c_j$, and how to prove it?

Weighted shortest processing time (WSPT, or Smith’s rule), order jobs by decreasing ratios $\frac{w_j}{p_j}$ . Proven with API to derive contradiction.

Define the “value” of a chain in $1|\text{chains}| \sum w_j C_j$

sum up the weights, divide by the sum of the processing times

What doe the notation $[k]$ refer to

The set of numbers $\{ 1,2, \ldots ,k\}$

Define rho factor/$\rho-$factor in the context of job chains

Describe the simple algorithm used to solve $1|\text{chains}| \sum w_j C_j$

Whenever a machine is free

1. Pick the remaining chain with the highest $\rho-$factor

2. Process the jobs of that chain up to and including its determining job $\ell^*$

   1. the remaining tail becomes a new chain with its own newly computed $\rho-$factor

Define the “determining job” $\ell^*$ in the context of parallel chains

The index of the chain achieving the maximum $\rho-$factor

What is the optimal approach for $1 || L_{max}$ (max lateness), and how is it proven?

The EDD rule is optimal — order jobs by increasing due dates

Proven with exchange argument - apply API to "optimal" schedule S that violates EDD.

What is $1 | \text{prec} | h_{max}$? What is the optimal approach?

We have $n$ jobs with no precedence constraints, and non-decreasing functions of completion times$h_1, h_2, … h_n$. $h_{max} = \text{max} \{h_1(C_1),h_2(C_2), \ldots , h_n(C_n) \}$. Note that this is for a single machine, so the completion time of the last job is always $\sum p_j$

Optimal approach: Least Cost Last (LCL), where you go backwards from $\sum p_j$ to $0$ and schedule the job that is cheapest to place last at current time $t$ each time.

Explain the LCL approach for $1 | \text{prec} | h_{max}$

Least Cost Last (LCL) is a simply polytime DP algorithm, where you go backwards from $\sum p_j$ to $0$ and schedule the job that is cheapest to place last at current time $t$ each time.

Name the three main types of approx

1. $\alpha-$approx algos

2. PTAs

3. FPTAs

Explain $\alpha-$approx algorithms

Algorithm that gives solution $S$ such that $cost(S) \leq \alpha \cdot \text{OPT}$

Explain PTAs (polytime approximations)

For any \varepsilon > 0, we can find solution $S: \text{cost}(S) \leq (1+ \varepsilon) \cdot \text{OPT}$ with running time $poly(n)$

• could be growing exponentially or worse with respect to $1/\varepsilon$

Explain FPTAs (fully polytime approximations), and the 3 main things we need for it

For any \varepsilon > 0, we can find solution $S: \text{cost}(S) \leq (1+ \varepsilon) \cdot \text{OPT}$ with running time $poly(n, \frac{1}{\varepsilon})$

We need

1. Feasibility: $S’$ satisfies $size(S’) \leq b$

2. Approximation: $profit(S’) \geq (1- \varepsilon)\text{OPT}$ for any \varepsilon > 0

3. Polynomial running time in $poly(n, 1/ \varepsilon)$

What method is used for developing FPTAS for knapsack, and some other NP complete problems?

See the value that you intend to scale, and scale each value by a parameter $\rho=\varepsilon \cdot \text{max for that val} (1/n)$

• (divide by parameter and truncate it so the error is 1. bounded and 2. close to original (rounding error per item is at most scaling parameter $\rho$)

Note that FPTAS for knapsack runs in $O(n^{3}/\varepsilon)$

Weakly vs strongly NP hard

We can find FPTAS for weakly NP hard (where difficulty comes more from large numbers) but not strongly NP hard.

Describe Moore-Hodgson for $1|| \sum U_j$.

Want to minimize total number of late jobs. Will do so using DP.

Repeat

• scan EDD sequence $\sigma = (\sigma_{1},\sigma_{2} \dots \sigma_{\ell})$ left to right

• find smallest k such that job $\sigma_{k}$ is late (i.e. c_{\sigma_{k}} > d_{\sigma_{k}}, makesum up to that job is greater than due date of that job)

• if no late job found: stop

• else

  • among $\sigma_{1},\sigma_{2} \dots \sigma_{k}$, find index $m$ with $p_{\sigma_{m}}=max_{i\in[k]}p_{\sigma_{i}}$

    • so find job with max processing time

    • note: this has nothing to do with the late job, it's just in the sequence prefix k

    • intuition: removing longest processing time job frees the most time for the remaining jobs

  • reject $\sigma_{m}$ (remove it from $\sigma$)

Output: $\sigma,\zeta$, where $\zeta$ is any permutation off all rejected jobs.

Proven with the key lemma and induction.

What is the key lemma for Moore-Hodgson, and how do you prove it?

Let m be the job rejected in iteration $\# 1$.
Then there is an optimal schedule that rejects $m$.

Proven via an exchange argument.

What is the dominance lemma for total tardiness

Suppose jobs $j$ and $k$have $P_{j} \leq P_{k}$ and $d_{j} \leq d_{k}$
Then $\exists$ optimal sequence in which $j$ precedes $k$.

Proved with standard exchange argument.

What does the notation $[a]^\oplus$

$$max(0, \alpha)$$

What is the DP shifting lemma for the DP algorithm for

Assume $p_{j}$'s are distinct, and let $k$ be the job with max processing time.

There is an integer $\delta$ with $\delta\in \{ 0,1,\dots , n-k \}$ such that there is an optimal sequence $S^{*}$ such that job $k$ is preceded by all jobs $j$ with $j \leq k+\delta$, and job $k$ is followed by all jobs $j$ with j > k+\delta.

Describe the DP algorithm for Total Tardiness $1||\sum T_j$

$S \equiv$ length of sub-interval following job $k$
(DP tries all values of $\delta=0,1,2\dots ,n-k$)

Lawler showed that such a sub-interval exists.

$J(s,f,k)=$ set of jobs from a sub-interval where

• $s=$ start index of sub-interval

• $f=$ last index of sub-interval

• $k$ is job such that $p_{k} \geq p_{j} \; \forall j\in J(\cdot)$

• $k$ is excluded from $J(\cdot)$

$V(J(\cdot), t) \equiv$ optimal value (minimum tardiness) for subset $J(\cdot)$ with start time $t$

DP recurrence:

$$V(J(s,f,k), t)=\text{min}_{\delta=0,1,\dots,n-k}\;V(J(s, \ell+\delta, \ell), t) + [C_{\ell}(\delta)-d_{\ell}]^{\oplus} + V(J(\ell+\delta+1, f, \ell), C_{\ell}(\delta))$$

key idea: we split the interval into two based on the job with the max processing time

Where

• $$\ell = \text{job in }J(s,f,k) \text{ with max processing time}$$

• $C_{\ell}(\delta)= \text{ completion time of }\ell$ for sub-interval of length $=\delta$

• $[C_{\ell}(S)-d_{\ell}]^{\oplus}=$ Tardiness of job $\ell$

What is the FPTAS for Total Tardiness $1|| \sum T_j$

Scale processing times and due dates by scaling factor $K$, with $K= \frac{2 \varepsilon}{n(n+1)}$

• the reasoning for this choice can be seen in the error bounding calculations