-------------------------------------------------------------------------------
17-3 Scheduling variations

a.   Assume the input jobs have already been sorted into monotonically decreasing order by penalty.
Suppose A is the schedule which is calculated by the algorithm of this problem. p(A) is the sum of 
penalties in schedule A. Suppose B is one of the optimal answer. And for the first k (k=0,1,...,n) 
jobs, their positions in A are equal to the positions in B respectively. And the k+1th job's position 
is different in the two schedules.
If k equals to n, then B is the same as A. So A is the optimal answer. If k is less then n, I will 
prove that there exists an optimal schedule B' which has the first k+1 jobs' positions equal to the 
positions in A respectively.
Let C be a schedule which has the first k jobs' time slots as same as A, and other time slots are 
empty. Suppose the k+1th job is at the pth time slot in B.

I)   If there exists a time slot in C at or before k+1th jobs deadline dk+1 and it is the lastest slot 
which satisfy this condition, let it be the qth time slot. Then p is not equal to q. Assume the job in 
qth slots of B is t. Then we swap the two jobs in pth and qth slots in B, and get a new schedule B'.
1) If p<q, the k+1th job still execute before the deadline, and no penalty is changed. The job t moved 
forward and the penalty will not increase. So p(B')<=p(B).
2) If p>q, the k+1th job must be execute after deadline in B, and execute before deadline in B'. The 
increment of penalty is -p(k+1th job). When we move the job t from q to p, the increment of penalty is 
at most p(t). Since the jobs are sorted in monotonically decreasing order by penalty, p(t)<=p(k+1th 
job). So the sum of penalty will not increase. p(B')<=p(B).

II)   If there does not exist a time slot in C at or before k+1th jobs deadline dk+1. Let q be the 
latest of the as yet unfilled slot. Assume the job in qth slots of B is t. Then we swap the two jobs 
in pth and qth slots in B, and get a new schedule B'.
Since p<q, the k+1th job still execute after the deadline, and no penalty is changed. the job t moved 
forward and the penalty will not increase. So p(B')<=p(B).

>From I) and II), we get an optimal schedule B' which has the first k+1 jobs' positions equal to the 
positions in A respectively. And we can use inductive method to prove there exist an optimal schedule 
which has n jobs' positions equal to the positions in A respectively. That means A is the optimal 
solution.

b.   Implementation of the algorithm.
1 to n are n nodes. And assume p[i]=NULL at the initial.
We put the continuous slots which are occupied by jobs in one set. and use a field min[] to record the 
minimum slots in the set.

for i=1 to n do
	if p[deadline[i]]=NULL				//slot deadline[i] is empty
		slot[deadline[i]]<-job[i];		//put job[i] in slot deadline[i]
		Make-Set(deadline[i]);
		if p[deadline[i]-1]!=NULL		//union with neighbours
			union(deadline[i],deadline[i]-1);
		if p[deadline[i]+1]!=NULL
			union(deadline[i],deadline[i]+1);
	else
		q=min[Find-Set(deadline[i])];		
		if q!=1				//exist empty slots before the deadline[i]
			slot[q-1]<-job[i];	//put job[i] in the lastest such slot
			Make-Set[q-1];
			union(q-1, q);		//union with neighbours
			if p[q-2]!=NULL;
			union(q-2,q-1);
		else				//no empty slots before the deadline[i]
			if p[n]=NULL //put job[i] in the latest of the as yet unfilled slot
				q=n+1;
			else
				q=min[Find-Set(n)];
			slot[q-1]<-job[i];
			Make-Set(q-1);
			union(q-1, q);		//union with neighbours
			if p[q-2]!=NULL;
			union(q-2,q-1);
			
and since we add a min[] field in the structure, the make-set(), union() changed slightly:
Make-Set(x)
p[x]<-x;
rank[x]<-0;
min[x]<-x;	//only one element

Union(x,y)
Link(Find-Set(x), Find-Set(y))
Link(x,y)
small=min(min[x],min[y]);			//find the smallest in the two sets
if rank[x]>rank[y]
	then 	p[y]<-x;
		min[x]=small;			//put the smallest in min[] field
	else	p[x]<-y;
		min[y]=small;			//put the smallest in min[] field
		if rank[x]=rank[y]
			then rank[y]=rank[y]+1;
Running time analysis:
In the whole procedure, for each element we use Make-Set once, that is n operations. The Union() 
between i and i+1 (i=1,...,n-1) will be execute exactly once, that is n-1 operations. The Find-Set() 
will be execute at most 2n times. All of these are O(n) times.
So the worst-case running time is O(nlg*n), almost linear time.


-------------------------------------------------------------------------------

> Date: Mon, 13 Nov 2000 09:11:07 -0800
> From: Eli Gafni <eli@CS.UCLA.EDU>
> X-Accept-Language: en
> MIME-Version: 1.0
> To: yizhou@CS.UCLA.EDU
> Subject: I need hw3 prob 2 from you today...
> Content-Transfer-Encoding: 7bit
> 
> 
>