lptc.cpp

来自「自己编写的任务机调度问题的近似算法（包括了穷举+近似的算法）」· C++ 代码 · 共 98 行

#include <iostream>
#include <algorithm>
#include <ctime>
const int N = 30;
int c = 3;
int m = 4;
int X[N];
int job[N] = {32,94,100,78,55,42,24,65,8,53};         // 各个任务的处理时间
int minTime = 10000;         //  记录穷举搜索的最优时间
int minMachine[N];   //  记录穷举搜索的最优调度的机器号码
using namespace std;

bool comp(const int& a,const int& b) // 逆序排序
{
	return a > b;
}

void traceback(int num)
{
	if(num == c){  // 找到一组解
		int maxProcessTime = 0;
		for(int j = 1; j <= m; j++){
			int temp = 0;
			for(int k = 0; k < c; k++){
				if(X[k] == j)
					temp += job[k];
			}
			if (temp > maxProcessTime )
				maxProcessTime = temp;
		}
		if (maxProcessTime < minTime){ // 更新，记录最优解
			minTime = maxProcessTime;
			printf("%d\n",minTime);
		
		for(int t = 0;  t < c; t++){
			minMachine[t] = X[t];
			printf("%d ",minMachine[t]);
		}
		printf("\n");
		}
		
	return;
	}
	for(int i = 1; i <= m; i++){
		X[num] = i;
		traceback(num+1);
	}
}



int main()
{
	int i,j;
	srand((unsigned)time(NULL)); 
	
	//for(i = 0; i < 10; i++)
	//	job[i] = rand()%100 + 1;
	//job = ;
	printf("调度前各个任务的处理时间\n");
	for(i = 0; i < 10; i++)   // 调度前各个任务的处理时间
		printf("%d\n",job[i]);
	printf("\n");
	printf("调度后的情况\n");
	sort(job,job+10,comp);      // 任务处理时间排序
	for(i = 0; i < 10; i++)   // 调度前各个任务的处理时间
		printf("%d ",job[i]);
	printf("\n");
	traceback(0);
	int time[N];           //  用来存储每台机器当前的任务量
	memset(time,0,sizeof(time));
	for(i = 0; i < c; i++)
		time[minMachine[i]] += job[i];

	// 处理剩余部分
	int min,k;
	for(i = c; i < 10; i++){
		min = time[1];
		k = 1;
		for(j = 2; j <= m; j++)
			if(time[j] < min){
				min = time[j];
				k = j;
			}
		minMachine[i] = k;
		time[k] += job[i];
	}
	int max = 0;
	printf("各个任务分配的机器\n");
	for(i = 0; i < 10; i++)
		printf("%d ",minMachine[i]);
	for(i = 1; i <= m; i++)
		if(time[i] > max)
			max = time[i];
	printf("处理的总时间:%d\n",max);
	traceback(0);
	return 0;
}