gantt.cpp

一个用于JSP神经网络的演示软件

#ifndef Gantt_CPP
#define Gantt_CPP

#include <iostream>
#include "Gantt.h"

GanttChart::GanttChart( int n, int m, int** machine, int** protime, double** data):res(false),loopfail(0)
{
	int i;
	this->n = n;
	this->m = m;

	matrix = new double*[n*m];
	for(i = 0; i < n*m; i++)
	{
		matrix[i] = new double[n*m+1];
	}
	if (data!=NULL)
	{
	    setMatrix(data);
	}

	this->machine = new int*[n];
	for (i = 0; i < n; i++)
	{
		(this->machine)[i] = new int[m];
	}
	if (machine != NULL)
	{
		setMachine(machine);
	}

	this->protime = new int*[n];
	for (i = 0; i < n; i++)
	{
		(this->protime)[i] = new int[m];
	}
	if (protime != NULL)
	{
		setProTime(protime);
	}

	proorder = new int*[n];
	for(i = 0; i < n; i++)
	{
		proorder[i] = new int[m];
	}	
	GetOrder();

	machorder = new int*[n];
	for (i = 0; i < n; i++)
	{
		machorder[i] = new int[m];
	}

	ganttPic = new GanttUnit*[m];
	for (i = 0; i < m; i++)
	{
		ganttPic[i] = new GanttUnit[n];
	}
	
	machstep = new int[m];
	for (i = 0; i < m; i++ )
	{
		machstep[i] = 0;
	}

	checked = new bool*[m];
	for (i = 0; i < m; i++)
	{
		checked[i] = new bool[n];
	}
}

/*
GanttChart::GanttChart(HNN* hnet)
{
	GanttChart(hnet->n, hnet->m, hnet->v, hnet->machine, hnet->protime);
}
*/

GanttChart::~GanttChart()
{
	int i;
	for (i = 0; i < n*m; i++)
	{
		delete []matrix[i];
	}
	delete []matrix;

	for (i = 0; i < n; i++)
	{
		delete []machine[i];
		delete []protime[i];
		delete []proorder[i];
		delete []machorder[i];
	}
	delete []machine;
	delete []protime;
	delete []proorder;
	delete []machorder;

	for (i = 0; i < m; i++)
	{
		delete []ganttPic[i];
	}
	delete []ganttPic;

	delete []machstep;
	
	for (i = 0; i < m; i++)
	{
		delete []checked[i];
	}
	delete []checked;

}

void GanttChart::setMatrix(double** data)
{
	for (int i = 0; i < n*m; i++)
	{
		for (int j = 0; j<n*m+1; j++)
		{
			matrix[i][j] = data[i][j];
		}
	}
}

void GanttChart::setMachine(int** machine)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			(this->machine)[i][j] = machine[i][j];
		}
	}
	
}


void GanttChart::setProTime(int** protime)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			(this->protime)[i][j] = protime[i][j];
		}
	}
}


bool GanttChart::constructGantt()
{
	int i,j;
	res = false;

	for (i = 0; i < m; i++ )
	{
		machstep[i] = 0;
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			machorder[i][j] = -1;	
		}
	}
		
	//递归由换位矩阵构造甘特图，
	//并自动修正可能出现的同一机器上前后任务的加工时间重叠
	//暂时忽略同一任务中前后工序的加工时间重叠情况
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (matrix[i*m+j][0] > 0.5)
			{
				if (machine[i][0] != j+1)	return false;
				
				int step = machstep[j];
				if (step > 0) 
				{
					int temp = step-1;
					while (temp>=0 && ganttPic[j][temp].start >= protime[i][proorder[i][j]]) temp--;
					for (int x = step-1; x > temp; x--)
					{
						ganttPic[j][x+1] = ganttPic[j][x];
						machorder[ganttPic[j][x+1].job-1][ganttPic[j][x+1].order-1]++;
					}
					
					step = temp+1;
					if (step > 0)
					{
						ganttPic[j][step].start = ganttPic[j][step-1].end;
						ganttPic[j][step].end = ganttPic[j][step-1].end +protime[i][proorder[i][j]];
					}
					else 
					{
						ganttPic[j][step].start = 0;
						ganttPic[j][step].end = protime[i][proorder[i][j]];
					}
				}
				else
				{	
					ganttPic[j][step].start = 0;
					ganttPic[j][step].end = protime[i][proorder[i][j]];
				}	
				
				ganttPic[j][step].job = i+1;
				ganttPic[j][step].order = proorder[i][j]+1;
				ganttPic[j][step].machine = j+1;
				machstep[j]++;
				machorder[i][proorder[i][j]] = step;

				findNextUnit(i*m+j, ganttPic[j][step].end);
			}
		}	
	}

	//检查是否所有工序都被分配了机器时间
	if (checkJobNum() == false)  return false;

	//检查在所生成的工序－机器双搜索图中是否有环
	if (dfscheck() == false)
	{
		if (checkJobTime() == false)	return false;		
	}
	else
	{
		//自动修正可能出现的同一任务中前后工序的加工时间重叠情况
		AdjustJobs();
	}

	res = true;
	return true;
}


void GanttChart::findNextUnit(int p, int startTime)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (matrix[i*m+j][p+1] > 0.5)
			{
				if (machorder[i][proorder[i][j]]!=-1) continue;
				int step = machstep[j];

			    if (step > 0 && ganttPic[j][step-1].end > startTime) 
				{
				   int temp = step-1;
				   while (temp>0 && ganttPic[j][temp].start >= startTime+protime[i][proorder[i][j]]) temp--;
				   for (int x = step-1; x > temp; x--)
				   {
						ganttPic[j][x+1] = ganttPic[j][x];
						machorder[ganttPic[j][x+1].job-1][ganttPic[j][x+1].order-1]++;
				   }
					
					step = temp+1;
					if (step > 0)
					{
						ganttPic[j][step].start = ganttPic[j][step-1].end;
						ganttPic[j][step].end = ganttPic[j][step-1].end +protime[i][proorder[i][j]];
					}
					else 
					{
						ganttPic[j][step].start = startTime;
						ganttPic[j][step].end = startTime+protime[i][proorder[i][j]];
					}
				}
				else
				{	
					ganttPic[j][step].start = startTime;
					ganttPic[j][step].end = startTime+protime[i][proorder[i][j]];
				}	

				ganttPic[j][step].job = i+1;
				ganttPic[j][step].order = proorder[i][j]+1;
				ganttPic[j][step].machine = j+1;
				machstep[j]++;
				machorder[i][proorder[i][j]] = step;
				
				findNextUnit(i*m+j, ganttPic[j][step].end);
			}
		}
	}
}

bool GanttChart::checkJobNum()
{
	//检查是否所有工序都被分配了机器时间
	for (int i = 0; i < m; i++)
	{
		if (machstep[i] < n)	
			return false;
	}

	return true;
}

bool GanttChart::checkJobTime()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m-1; j++)
		{
			int order = machorder[i][j];
			int mach = machine[i][j]-1;
			if (ganttPic[mach][order].end>ganttPic[mach][order+1].start)
				return false;
		}
	}
}

bool GanttChart::dfscheck()
{
	int i,j;

	//检查在所生成的工序－机器双搜索图中是否有环
	//(环会造成AdjustJobs搜索的死锁)
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			checked[i][j] = false;
		}
	}
	
	for (i = 0; i < m; i++)
	{
		if (ganttPic[i][0].order == 1)
		{
			if (checkLoops(i,0) ==  false) 
			{
				loopfail++;
				return false;
			}
		}
	}
}

bool GanttChart::checkLoops(int mach, int mastep)
{
	if (checked[mach][mastep] == true)	return false;	
	checked[mach][mastep] = true;

	if (mastep < n-1)
	{
		if (checkLoops(mach, mastep+1) == false) return false;
	}

	if (ganttPic[mach][mastep].order < m)
	{
		int job = ganttPic[mach][mastep].job-1;
		int order = ganttPic[mach][mastep].order-1;
		if (checkLoops(machine[job][order+1]-1, machorder[job][order+1]) == false)	return false;
	}

	checked[mach][mastep] = false;
	return true;
}


void GanttChart::AdjustJobs()
{
	int i, j, k;
	int num = n*m;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			checked[i][j] = false;
		}
	}
	
	while (1)
	{
		//按照甘特图中工序的排列顺序，依次遍历检查
		for (i = 0; i < m; i++)
		{
			//每个机器上的第一个任务
			if (checked[i][0] == false)
			{
				int job = ganttPic[i][0].job-1;
				int order = ganttPic[i][0].order-1;

				//若本工序为任务中的第一个工序，则起始时间一定为0
				if (order == 0) 
				{
					checked[i][0] = true;
					ganttPic[i][0].start = 0;
					ganttPic[i][0].end = protime[job][0];
					num --;
				}
				//否则必须考虑任务中的工序时间重叠问题
				else 
				{	
					int preorder = machorder[job][order-1];
					int premach = machine[job][order-1]-1;
					if (checked[premach][preorder] == true)
					{	
						checked[i][0] = true;
						ganttPic[i][0].start = ganttPic[premach][preorder].end;
						ganttPic[i][0].end = ganttPic[i][0].start + protime[job][order];
						num --;
					}
				}
				if (num == 0)	
				{
					return;
				}
			}

			//每个机器上的其它任务
			for (j = 1; j < n; j++)
			{
				if (checked[i][j] == true)	continue;

				int job = ganttPic[i][j].job-1;
				int order = ganttPic[i][j].order-1;
				if (checked[i][j-1] == false) continue;

				//若本工序为任务中的第一个工序，则只用考虑避免机器上时间重叠问题
				if (order == 0)
				{
					checked[i][j] = true;
					ganttPic[i][j].start = ganttPic[i][j-1].end;
					ganttPic[i][j].end = ganttPic[i][j].start + protime[job][order];
					num --;
				}
				//否则必须同时考虑机器和任务中的工序时间重叠问题
				else 
				{
					int preorder = machorder[job][order-1];
					int premach = machine[job][order-1]-1;
					if (checked[premach][preorder] == true)
					{
						checked[i][j] = true;
						ganttPic[i][j].start = ganttPic[i][j-1].end > ganttPic[premach][preorder].end ? ganttPic[i][j-1].end : ganttPic[premach][preorder].end;
						ganttPic[i][j].end = ganttPic[i][j].start + protime[job][order];
						num --;
					}
					
				}	
				if (num == 0)	
				{
					return;
				}
			}
		}
		
	}

}

void GanttChart::drawGantt(GanttHis* his, int s)
{
	if(res == 0)	return;

	int h = 50;//图距左端的距离
	int l = 40;//图距上端的距离
	int unit = 20;//一个时间单位在图中的长度
	int height = 20;//甘特图块的高度
	int span = 60;//两个机器分配图之间的距离
	int wl = 3;//文字与直线之间的距离
	int start = s*(span*m+l);
	LineHis templ;
	TextHis tempt;
	CPoint p;

	for (int i = 0; i < m; i++)
	{
		CString text;
		text.Format("M%d: ",i+1);
		p.x = 10;
		p.y = 25+i*span+start;
		tempt.pos = p;
		tempt.word = text;
		(his->texthis).push_back(tempt);

		int end = ganttPic[i][n-1].end;
		p.x = h;
		p.y = l+i*span+start;
		templ.start = p;
		p.x = h+end*unit;
		templ.end = p;
		(his->linehis).push_back(templ);

		for (int j = 0; j < n; j++)
		{
			text.Format("%d",ganttPic[i][j].start);
			p.x = h+unit*ganttPic[i][j].start-wl;
			p.y = l+i*span+wl+start;
			tempt.pos = p;
			tempt.word = text;
			(his->texthis).push_back(tempt);
			p.x = h+unit*ganttPic[i][j].start;
			p.y = l+i*span-height+start;
			templ.start = p;
			p.x = h+unit*ganttPic[i][j].start;
			p.y = l+i*span+start;
			templ.end = p;
			(his->linehis).push_back(templ);
 

			text.Format("%d%d%d",ganttPic[i][j].job,ganttPic[i][j].order,ganttPic[i][j].machine);
			p.x = h+unit*(ganttPic[i][j].start+ganttPic[i][j].end)/2-8;
			p.y = l+i*span-height-15+start;
			tempt.pos = p;
			tempt.word = text;
			(his->texthis).push_back(tempt);	 
			p.x = h+unit*ganttPic[i][j].start;
			p.y = l+i*span-height+start;
			templ.start = p;	 
			p.x = h+unit*ganttPic[i][j].end;
			p.y = l+i*span-height+start;
			templ.end = p;
			(his->linehis).push_back(templ);
			

			text.Format("%d",ganttPic[i][j].end);
			p.x = h+unit*ganttPic[i][j].end-wl;
			p.y = l+i*span+wl+start;
			tempt.pos = p;
			tempt.word = text;
			(his->texthis).push_back(tempt);	
			p.x = h+unit*ganttPic[i][j].end;
			p.y = l+i*span-height+start;
			templ.start = p;
			p.x = h+unit*ganttPic[i][j].end;
			p.y = l+i*span+start;
			templ.end = p;
			(his->linehis).push_back(templ);
		}
	}

}


void GanttChart::drawNeroOutputs(GanttHis* his)
{
	if(res == 0)	return;

	CString text;
	TextHis tempt;
	CPoint p;
	int left = 20;//起始点距左边距离
	int top = 10;//起始点距上方距离
	int unit = 30;//列之间距离
	int span = 30;//行之间距离

	for (int i = 0; i < n*m; i++)
	{
		for (int j = 0; j<n*m+1; j++)
		{
			text.Format("%d ",(int)matrix[i][j]);
			p.x = left+j*unit;
			p.y = top+i*span;
			tempt.pos = p;
			tempt.word = text;
			(his->texthis).push_back(tempt);
		}
	}

}

void GanttChart::GetOrder()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			proorder[i][machine[i][j]-1] = j;//j为工序数减1
		}
	}
}
	

/*
GanttUnit** GanttChart::getGuantt()
{
	
	int i, j;
	GanttUnit** g = new GanttUnit*[m];
	for (i = 0; i < m; i++)
	{
		g[i] = new GanttUnit[n];
	}

	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			g[i][j] = (this->ganttPic)[i][j];
		}
	}
	return g;
	
}
*/

int GanttChart::getMaxTime()
{
	if (res == false)  return HUGENUM;

	int maxTime = 0;
	for (int i = 0; i < m; i++)
	{
		if (ganttPic[i][n-1].end > maxTime)
		{
			maxTime = ganttPic[i][n-1].end;
		}
	}
	return maxTime;
}


bool GanttChart::isValid()
{
	return res;
}

#endif