多机调度问题.cpp

算法分析中

/*
设有 n 个独立的作业 { 1 , 2 , .. , n }，由 m 台相同的机器进行加工处理。
作业 i 所需的处理时间为 ti。现约定，任何作业可以在任何一台机器上加工处理，
但未完工前不允许中断处理。任何作业不能拆分成更小的作业。
多机调度问题要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内
由 m 台机器加工处理完成。

分析：
这个问题是一个NP完全问题，到目前为止还没有一个有效的解法。
对于这一类问题，用贪心选择策略有时可以设计出较好的近似算法。
采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。

按此策略，
当 n <= m 时，只要将机器 i 的[0,ti]时间区间分配给作业i即可。

当 n > m 时，首先将 n 个作业依其所需的处理时间从大到小排序。
 然后依此顺序将作业分配给空闲的处理机。

<<<< 简单一句话，让最空闲的机器做最繁重的任务 >>>>


*/

#define maxWork 100
#define maxMachine 100

class machineWork
{
public:
	machineWork(void);
	~machineWork(void);

	void SetMachine( int machine );
	void SetWorks( double times[] , int works );
	bool Arrange();
	void Sort( int timeId[] );
	void Print();
private:
	//double times[maxWork];
	double timesUnsorted[maxWork];
	//没经过排序的任务对应需要的时间数组
	int graph[maxMachine][maxWork];
	//机器和任务的对应数组
	double machinesTime[maxMachine];
	//机器的已经安排的时间进行排序

	int machines;
	//记录的是机器的总数
	int works;
	//记录的是任务的总数
};



machineWork::machineWork(void)
{
}

machineWork::~machineWork(void)
{
}

void machineWork::Sort( int timeId[] )
{
	for( int i = 0 ; i < works ; i++ )
	{
		timeId[i] = i;
	}
	for( int i = 0 ; i < works - 1 ; i++ )
		//使用选择排序方法
	{
		double min = timesUnsorted[ timeId[i] ];
		int p = i;
		for( int j = i + 1 ; j < works ; j++ )
		{
			if( this->timesUnsorted[ timeId[j] ] > min )
			{
				min = this->timesUnsorted[ timeId[j] ];
				p = j;
			}
		}
		int t = timeId[i];
		timeId[i] = timeId[p];
		timeId[p] = t;
	}
}


void machineWork::SetMachine( int machines )
{
 this->machines = machines;
}
//
//
void machineWork::SetWorks( double times[] , int works )
{
 this->works = works;
 for( int i = 0 ; i < works ; i++ )
  timesUnsorted[i] = times[i];
}
//
//
bool machineWork::Arrange()
{
	int timeId[maxWork];
	Sort( timeId );
	//某一工作安排后，对机器的工作时间进行排序
	//index[i]保存机器编号
	int index[maxMachine];
	//graph[i][0]表示机器i中已经安排了几项任务
	for( int i = 0 ; i < machines ; i++ )
	graph[i][0] = 0;
	//机器已经安排的工作时间
	for( int i = 0 ; i < works ; i++ )
		machinesTime[ i ] = 0.0;
	//index[0]所指向的 graph[ index[0] ][0] 的值是最小的
	for( int i = 0 ; i < machines ; i++ )
	index[i] = i;
	//给 i 号作业分配机器
	for( int i = 0 ; i < works ; i++ )
	{
	//把作业分配给 index[0] 所指向的机器
	graph[ index[0] ][0]++;
	graph[ index[0] ][ graph[index[0]][0] ] = timeId[i];
	machinesTime[ index[0] ] += timesUnsorted[ timeId[i] ];
	//对机器的已经安排的工作时间进行排序
	int j = 0;
	while(	j < machines - 1 
			&& machinesTime[ index[ j ] ] > machinesTime[ index[ j+1 ] ] )
	{
		int t = index[j];
		index[j] = index[j+1];
		index[j+1] = t;
		j++;
	}
	}
	return true;
}
//
//
void machineWork::Print()
{
 printf( "----------------------------------------\n" );
 for( int i = 0 ; i < works ; i++ )
  printf( "工作 %d 所需要的时间 %5.f\n" , i , timesUnsorted[i] );
 printf( "\n" );


 for( int i = 0 ; i < machines && i < works ; i++ )
 {
  printf( "机器 %d 工作总时间 %.f = " , i , machinesTime[i] );
  printf( "%.f " , timesUnsorted[ graph[i][1] ] );
  for( int j = 2 ; j <= graph[i][0] ; j++ )
   printf( "+ %.f " , timesUnsorted[ graph[i][j] ] );
  printf( "\n" );
 }
 printf( "\n" );


 for( int i = 0 ; i < machines ; i++ )
 {
  printf( "机器 %d 上的工作安排 " , i );
  for( int j = 1 ; j <= graph[i][0] ; j++ )
   printf( "%d " , graph[i][j] );
  printf( "\n" );
 }
 printf( "----------------------------------------\n" );
}


#include "stdafx.h"
#include "machineWork.h"
#include "conio.h"

int _tmain(int argc, _TCHAR* argv[])
{
 double t[maxWork] = { 2 , 14 , 4 , 16 , 6 , 5 , 3 };
 machineWork w;
 w.SetMachine( 10 );
 w.SetWorks( t , 7 );
 w.Arrange();

 w.Print();

 getch();
 return 0;
}