流水作业调度.cpp

算法分析部分

/*
n个作业{1,2,...,n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是
先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai,bi,1<=i<=n。流水线
作业调度问题要求确定这n个作业的最优加工顺序，使得第一个作业在机器M1上开始加工，到最后一个作业在机器
M2上加工完成所需要的时间最少。
设全部作业的集合为N={1,2,...,n}。S属于N是N的作业子集。在一般情况下，机器M1开始加工S中作业
时，机器M2还在加工其它作业，要等时间t后才可以使用。将这种情况下完成S中作业所需要的最短时间记为
T(S,t)。流水作业调度问题的最优值是T(N,0)
*/
/*
最优子结构性质：
设u是所给n个流水作业的一个最优调度，它所需要的加工时间是a(u(1))+T'
其中T'是在机器M2的等待时间为b(u(1))时，安排作业u(2),...,u(n)所需要的时间。
记S = N - {u(1)},则有T' = T(S,b(u(1)))。
事实上由T的定义知道：T'>=T(S,b(u(1)))。若T'>T(S,b(u(1)))，设u'是作业
集S在机器M2的等待时间为b(u(1))情况下的一个最优秀调度，则u(1),u'(2),...,u'(n)
是N的一个调度，且该调度所需的时间为a(u(1))+T(S,b(u(1)))<a(u(1))+T'。这与u是N的
一个最优调度矛盾。故T'<=T(S,b(u(1)))。从而T' = T(S,b(u(1)))。这就证明了流水作业调度
问题具有最优子结构的性质。
*/
/*
递归计算最优值：
由流水作业调度问题的最优子结构性质可以知道：
T(N,0) = min{1<=i<=n}{ai + T(N-{i},bi)}
推广到一般形式下便有：
T(S,t) = min{i属于S}{ai+T(S-{i},bi+max{t-ai,0})}
其中max{t-ai,0}这一项是由于在机器M2上，作业i必须在max{t,ai}时间之后才能开工
因此在机器M1上完成作业i后，在机器上还需要
bi+max{t,ai}-ai = bi + max{t-ai,0}时间才能完成对作业i的加工
*/
/*
流水作业的Johnson法则：
设u是作业集S在机器M2的等待时间为t的任一最优调度。若在这个调度中，安排在最前面的两个作业分别是
i和j，即u(1) = i,u(2) = j。则动态递归式可得
T(S,t) = ai + T(S-{i},bi+max{t-ai,0}) = ai + aj + T(S-{i,j},tij)
其中tij = bj + max{ bi + max{t-ai,0} - aj,0}
		= bj + bi - aj + max{max{t-ai,0},0,aj-bi}
		= bj + bi - aj - ai + max{t,ai + aj - bi, ai }
如果作业i和j满足min{bi,aj}>=min{bj,ai}，则称作业i和j满足johnson不等式

如果作业不满足johnson不等式，则交换作业i和作业j的加工顺序后，作业i和作业j满足johnson不等式。
在作业集S当机器M2的等待时间为t时的调度u中，交换作业i和j的加工顺序得到S的另一个调度u',
它所需要的加工时间为
T'(S,t) = ai + aj + T(S-{i,j},tji)
其中，tji = bj + bi - aj - ai + max{t,ai+aj-bj,aj}。
当i和j满足johnson不等式的min{bi,aj}>=min{bj,ai}时
max{-bi,-aj}<=max{-bj,-ai}
从而
ai + aj + max{-bi,-aj} <= ai + aj + max{-bj, -ai}
max{ai+aj - bi,ai}<=max{ai+aj-bj,aj}


从而tij <= tji由此可见T(S,t)<=T'(S,t)
换句话说，如果i,j不满足johnson不等式的时候，T(S,t)>=T'(S,t),所以要交换
i和j使它们满足johnson不等式，且不增加加工的时间。由此可知，对于流水作业调度
问题，必然存在一个最优调度u，使得作业u(i)和u(i+1)满足johnson不等式
min{b(u(i)),a(u(i+1))}>=min{b(u(i+1)),a(u(i))} 1<=i<=n-1
则称这样的调度u为满足johnson法则的调度
可以进一步证明，调度u满足johnson法则当且仅当对于任意的i<j有：
min{b(u(i)),a(u(j))}>=min{b(u(j)),a(u(i))}.
至此我们将流水作业调度问题转化为求满足johnson法则的调度问题。
*/

/*
算法描述：
从上面的分析可知，流水作业调度问题一定存在满足johnson法则的最优调度
且容易由下的算法确定：
流水作业调度问题的Johnson算法：
（1）将N1={i|ai<bi},N2={i|ai>=bi};
（2）将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序
（3）N1中作业接N2中作业构成满足Johnson法则的最优调度：
算法具体实现如下：

*/

template<class Type>
int  Partion( Type *d, int left, int right )
{
	int i,j;
	Type temp;
	Type less = d[left];
	i = left;
	j = right;
	while( i < j )
	{
		while( d[++i] < less );
		while( d[--j] > less );
		
		if ( i < j )
		{
			temp = d[i];
			d[i] = d[j];
			d[j] = temp;
		}	
	}
	d[left] = d[j];
	d[j] = less;
	return j;
}

template<class Type>
bool SortWork( Type *d, int left,int right )
{
	if ( left < right )
	{
		int middle = Partion( d, left, right );
		SortWork( d, left, middle - 1 );
		SortWork( d, middle + 1, right );
	}
	return true;
}

class Jobtype
{
	public:
		bool operator<(const Jobtype &a) const
		{
			return (key < a.key);
		}

		bool operator>(const Jobtype &a) const
		{
			return key>a.key;
		}
		int key;
		int index;
		bool job;
};

int FlowShop( int n, int *a, int *b, int *c )
{
	Jobtype *d = new Jobtype[n];
	for( int i = 0; i < n; ++i )
	{
		d[i].key = a[i]>b[i]?b[i]:a[i];
		//记录M1，M2中最小的那个时间
		d[i].job = a[i] <= b[i];
		//如a[i]<=b[i]则为true
		d[i].index = i;
	}

	SortWork<Jobtype>(d,0,n);
	//根据d的key值从小到大进行排序，排序得到的结果是
	//依据a[i]的递增和依据b[i]的递增
	int j = 0;
	int k = n - 1;
	for( i = 0; i < n; ++i )
	{
		if ( d[i].job )
		{
			c[j++] = d[i].index;
		}
		else
		{
			c[k--] = d[i].index;
			//调整为依据b[i]的非递增
		}
	}
	j = a[c[0]];
	k = j + b[c[0]];
	for( i = 1; i < n; ++i )
	{
		j += a[c[i]];
		//j是计算在M1上处理作业的总时间
		//k是处理完第c[i]-1个作业所用的总时间
		
		k = j < k ? k + b[c[i]]:j + b[c[i]];
		//如果处理完第c[i]-1个作业所用的总时间大于处理完第c[i]个作业在M1上处理的时间
		//则总时间就是前这的时间加上b[c[i]],否则就是后者加上c[i]
		
	}
	delete d;
	return k;
}

int main()
{
	return 0;
}