程序源代码.cpp

生产线平衡问题的启发式算法求解

#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

const int Tc = 10;
const int max_units = 1000;

int unit_num;

struct unit
{
	int Te;
	int up;
	int down;
} units[max_units];

int relation[max_units][max_units];

int sort_index[max_units];

int cmp( const void*a,const void*b)
{
	int*p = (int*)a;
	int*q = (int*)b;
	return units[*q].Te - units[*p].Te;
}



int main( )
{
	int i;
	int t,f;
	int station;
	int sTe;
	int left;
	int j,k;
	int oldleft;
	char fname[30];
	char c;

	cout << "测试数据文件名:\n" ;
	cin >> fname;

	ifstream in;
	in.open(fname);

	in >> unit_num ;
	for( i = 1; i <= unit_num; i ++ )
		in >> units[i].Te; 
	while( 1 ){
		in >> f >> c >> t;
		if( t == -1 && f == -1 )
			break;
		relation[f][t] = 1;
		units[f].down ++;
		units[t].up ++;
	}

	for( i = 1; i <= unit_num; i ++ )
		sort_index[i] = i;
	qsort(sort_index+1,unit_num,sizeof(int),cmp);//求优先序


	station = 0;
	left = unit_num;
	while( left > 0 ){

		oldleft = left;
		station ++;
		sTe = 0;

		cout << "工作站 "<< station << " 负责的任务:" << endl;

		while( sTe <= Tc ){
			for( i = 1; i <= unit_num; i ++ ){
				j = sort_index[i];
				if( j > 0 && units[j].up == 0 && sTe + units[j].Te <= Tc)
					break;
			}

			if( i > unit_num )
				break;
			
			for( k = 1; k <= unit_num; k ++ ){
				if( units[j].down <= 0 )
					break;
				if( relation[j][k] == 1 ){
					units[j].down --;
					units[k].up --;
				}
			}
			left --;
			sTe += units[j].Te;
			sort_index[i] = -1;

			cout << "任务"<<j<<"    "<<"Te "<<units[j].Te<< endl;
		}

		if( left == oldleft){
			cout << "输入数据中优先度构成环，无解"<<endl;
			break;
		}
	}


	return 0;
}