批处理作业调度问题.cpp

算法分析中

/*
给定的n个作业的集合J=(J1,J2,...,Jn)。
每一个作业Ji都有两项任务要分别在2台机器上完成
每一个作业必须先右机器1处理，然后再由机器2处理。
三个作业分别进行的，作业123连续在机器1上处理，没有重叠在里面的
算法设计：
对于批处理作业调度问题，由于是从n个作业的所有排列中找出有最小完成时间和的作业调度
所以批处理作业调度问题的解空间是一课排列树
*/
/*
给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。 
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。 
tji 机器1 机器2 
作业1 2 1 
作业2 3 1 
作业3 2 3 
这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。 
　　推导了许久，还是搞不清楚王晓东的例子。请高手解释一下最佳方案的18是如何得到的。 
 
 
问题点数：100 回复次数：3 显示所有回复显示星级回复显示楼主回复 修改 删除 举报 引用 回复   
 
我猜一下,以1,2,3为例: 
作业1在机器1上完成的时间为2,在机器2上完成的时间为3 
作业2在机器1上完成的时间为5,在机器2上完成的时间为6 
作业3在机器1上完成的时间为7,在机器2上完成的时间为10 
3+6+10=19，所以是19 
1，3，2 
作业1在机器1上完成的时间为2,在机器2上完成的时间为3 
作业3在机器1上完成的时间为4,在机器2上完成的时间为7 
作业2在机器1上完成的时间为7,在机器2上完成的时间为8 
3+7+8=18，所以时间和为18 
 
所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和 
…… 
 
ls猜得很准，是这个意思。不光要计算作业时间，连同等待时间也要考虑在内。 
这题同第3章的“流水作业调度”题干是一样的，当然所求的最优目标不同。 

*/
#include<iostream>
using namespace std;

class Flowshop
{
	friend Flow(int**,int,int[]);
private:
	void Backtrack(int i);
	int**M;
	//各作业所需的处理时间
	int *x;
	//当前作业调度
	int *bestx;
	//当前最优作业调度
	int *f2;
	//机器2完成处理时间
	int f1;
	//机器1完成的处理时间
	int f;
	//完成时间和
	int bestf;
	//当前最优值
	int n;
	//作业数
};

bool Swap(int &a,int &b )
{
	int temp;
	temp = a;
	a = b;
	b = temp;
	return true;
}
void Flowshop::Backtrack(int i)
{
	if ( i > n )
	//到叶结点，更新最优值
	{
		for( int j = 1; j <= n; ++j )
		{
			bestx[j] = x[j];
		}
		bestf = f;
	}
	else
	{
		for( int j = i; j <= n; ++j )
		{
			f1 += M[x[j]][1];
			//第j个作业在机器1上所需要的时间
			cout<<"f1 : "<<f1<<endl;
			f2[i] = ( (f2[i-1] > f1)?f2[i-1]:f1)+M[x[j]][2];
			//作业在机器2上的时间是等待时间加上要处理的时间
			cout<<"f2["<<i<<"] : "<<f2[i]<<endl;
			f += f2[i];
			//所有在机器2上完成的时间总和
			cout<<"f : "<<f<<endl;
			if ( f < bestf )
			{
				Swap(x[i],x[j]);
				//交换i,j就是为了调换顺序的
				Backtrack(i+1);
				Swap(x[i],x[j]);
			}
			f1 -= M[x[j]][1];
			f -= f2[i];
		}
	}
}

int Flow(int **M,int n,int bestx[])
{
	int nb = 32767;
	Flowshop X;
	X.x = new int[n+1];
	X.f2 = new int[n+1];
	X.M = M;
	X.n = n;
	X.bestx = bestx;
	X.bestf = nb;
	X.f1 = 0;
	X.f = 0;
	for ( int i = 0; i <= n; ++i )
	{
		X.f2[i] = 0;
		X.x[i] = i;
	}
	X.Backtrack(1);
	delete []X.x;
	delete []X.f2;
	cout<<"X.bestf = "<<X.bestf<<endl;
	return X.bestf;
}

int main()
{
	int **m;
	m = new int*[4];
	for( int i = 0; i < 4; ++i )
	{
		m[i] = new int[3];
	}
	m[1][1] = 2;
	m[2][1] = 3;
	m[3][1] = 2;
	m[1][2] = 1;
	m[2][2] = 1;
	m[3][2] = 3;
	int b[4];
	Flowshop a;
	Flow(m,3,b);
	return 0;
}