# Proving greedy algorithm is optimal for a scheduling problem

First, the problem discription:

For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of length $0$ such that in the end all the tasks are put in the queues and both queues has length $2n$. Let $cost$ be 0 at first. For each task $a_i$ that has value $1$, we add its index in the queue to the $cost$. The objective is to minimize the $cost$.

Example, the sequence of tasks is $10101010$, and we put the $1$th task in queue $1$, the $2$th task in queue $1$, the $3$th task in queue $2$, the $4$th task in queue $1$, the $5$th task in queue $2$, the $6$th task in queue $1$, $7$th task in queue $2$, the $8$th task in queue $2$, then queue $1$ will has task sequence $1000$ and queue $2$ will has task sequence $1110$, so the $cost$ is $(1)+(1+2+3)=7$.

Then we describe the greedy algorithm with parameter $0\le k\le 2n$：

It first puts the first $k$ tasks sequentially to the end of queue $1$. Then for $i=k+1,\dots$, if $a_i=1$ it puts the $i$th task into a queue with smaller length, else it puts the $i$th task into a queue with bigger length until one of the queues is full(it has length $2n$). Finally it puts the rest of tasks sequentially to the end of the non-full queue.

The question is proving the best greedy algorithm(over choices of $k$) gives the optimal cost for any $4n$ length sequence. I have many simulation results that support this statement and haven't found a proof yet.

• Does your simulation use random costs? If so, the greedy algorithm might be optimal for all your instances, but not for general instances. – Peter Shor Jun 15 '13 at 11:38
• @PeterShor: One of my simulation enumerates all sequences of length 20 (total number $2^{20}$) and it shows that greedy algorithm is optimal for these sequences. And you are right that for sequences with bigger length, it might not be optimal. But I guess it is. – caozhu Jun 15 '13 at 12:09
• That simulation is indeed convincing. – Peter Shor Jun 15 '13 at 12:26
• Is there a good example for why $k=0$ yields a suboptimal solution? – Suresh Venkat Jun 15 '13 at 17:03
• @SureshVenkat: For example, task sequence 101010101010 makes greedy algorithm with k=0 a sub optimal solution. At the end of the algorithm, the two queues will be $100000$ and $111110$, making the cost $(1)+(1+2+3+4+5)=16$. When $k=3$ or $k=4$, two queues will be $101000$ and $111010$, making the cost $(1+3)+(1+2+3+5)=15<16$. Thus $k=0$ is suboptimal in this case. – caozhu Jun 16 '13 at 2:41