# Minimum size counter-example in a 2-machine scheduling problem proof

I'm confused about something in the main proof in this paper (sorry that it's behind a paywall, but I assume many people on here have access to such things through their university and my posting the paper somewhere accessible would be, you know, technically illegal). It's not that I think the authors made an error; I'm just brand new at this and there's a lot of stuff I don't understand.

The point in question is four pages into the paper (sorry), but I'll try to summarize it. First of all, this variation of the scheduling problem is $P2|r_j|C_{max}$, i.e. 2-machine scheduling with release dates and no preemption with the goal of minimizing the makespan. Also, you're allowed to delay the assignment of jobs as opposed to having to assign them immediately if a machine is available. (This allows the algorithm to let any additional jobs come in to better determine how to assign them.)

The paper's claim is that its algorithm is ($1 + \alpha$)-competitive, $\alpha$ = 0.38197. The value of $\alpha$ is also used by the algorithm itself, since it waits $\alpha p_n$ ($p_n$ = the processing time of the last job started) before assigning each job.

The proof is by contradiction, where it takes $\sigma$ as the minimum schedule that makes the algorithm take longer than $1 + \alpha$ ($1$ being the length of the optimal offline schedule).

Let $j$ be the last job released when one of the machines is idle and no jobs are available. (Any time when both machines are idle can basically be ignored). Let $k$ be the job running when $j$ is released. If there's never a time when a machine is idle while there are no jobs available, let $r_j = C_k = 0$. ($r$ stands for release time; $C$ stands for completion time.)

Let $p$ equal any processing the optimal offline algorithm would need to do on previously released jobs at time $r_j$ (which may be 0).

The paper states: "Since $\sigma$ is a minumum size counterexample, $C_k \le (1 + \alpha)(r_j + p)$."

This comes out of nowhere for me. Why isn't it conceivable that $C_k$ could be greater than $(1 + \alpha)(r_j + p)$? I get that the makespan of $\sigma$ is basically just over $(1 + \alpha)C_{max}(opt)$, but why would the completion time of any job, even a "special" one like $k$, fall under a similar restriction? What if, for instance, $C_k(\sigma)$ is way over $(1 + \alpha)(r_j + p)$, but nevertheless, for whatever reason, $\sigma$ really catches up after that point and still finishes at $(1 + \alpha)C_{max}(opt)$? I suppose that seems unlikely, but why isn't it possible?

I sense that I'm being a bit picky, but on the other hand, I also sense that there's something I'm fundamentally not understanding.

Sorry this is so long. And sorry for breaking whatever forum rule or guideline I've no doubt violated.

• The link is to John Noga and Steven S. Seiden, An optimal online algorithm for scheduling two machines with release times, TCS 268, 2001. – András Salamon Jan 8 '15 at 3:41
• Isn’t it just saying that if C_k > (1+α)(r_j+p), then the set of jobs released strictly before r_j becomes a smaller counterexample, contradicting the minimality of the size of σ? – Tsuyoshi Ito Jan 8 '15 at 13:48
• If I may ask a follow-up question, I have a lot of questions on this paper, and since it's still the winter break, I can't ask my professor. I assume it would annoy everyone here if I posted all my questions in separate posts. Are we allowed to post several related questions in one post? (Sorry for asking this question here, but I don't have enough reputation to post a question in meta and the FAQ doesn't address this.) – user124384 Jan 9 '15 at 8:03
• I do not know what other people think, but I personally do not think that it is acceptable to ask many questions on one paper, no matter whether they are posted as a single post or many posts. The users of this website are not your free tutors. – Tsuyoshi Ito Jan 9 '15 at 8:56
• Wow. If that's the case, why ask any questions? – user124384 Jan 9 '15 at 8:57