基于混合遗传算法车间调度优化论文+程序

车间作业调度问题（Job Shop Scheduling Problem）是一个著名的NP难题，具有很强的条件约束，当问题规模较大时很难找到全局最优解。因此作业车间调度是一类求解困难的组合优化问题。近几年各种智能计算方法逐渐被引入到作业调度问题中，如遗传算法、模拟退火算法、启发式算法等。如何有效的安排各零件的加工顺序将直接关系到生产效率,也是本文所要解决的问题之一。本文提出了实现车间调度的混合遗传算法的设计方案，把遗传算法与模拟退火算法相结合，充分发挥遗传算法良好的全局搜索能力和模拟退火算法有效避免陷入局部极小的特性，通过实验验证了基于混合算法的作业车间调度方法显著提高了搜索效率，GASA改进了收敛性能。

#include “stdlib.h“
#include “stdio.h“
#include “time.h“

#define PARA 1.1
#define CYNUM 10

//////////////////////结构体定义/////////////////////////////
typedef struct{
	char GZname[5];//工种的名称
	int GXnum;//工序数
	int GJnum;//工件数
}GZ;//工种

typedef struct{
	int time;//每个工序所用的时间
	int machine;//每个工序所用的机器
}GX;//工序

struct JCNode //定义机床任务队列的节点
{
	int tasknum;
	int lasttime;
	int *tasklist;
	struct JCNode *next;
}list*plist;


//////////////////////功能函数定义//////////////////////////

int getGXnum（GZ* gz）
{//返回某个工种的工序数
	return （gz->GXnum）;
}



int getGJnum（GZ* gz）
{//返回某个工种的工件数
	return （gz->GJnum）;
}


int location（int *pDadint posint *pMum）
{//寻找pDad里pos位上的基因在pMum的位置
	int ijk=0;
	int *p;
	i=*（pDad+pos）;
	for（j=0;j<=pos;j++）
		if （*（pDad+j）==i） 
			k++;
	p=pMum;
		
	while （k!=0）
		if（*（pMum++）==i）
			k--;
			
	return（pMum-p-1）;

}



void crossover（float crossoverrateint *pDadint *pMumint GXTnum）
{//杂交
	int xytijkmin;
	float iscross;
	int*p*q;
	//求杂交的位置
	x=rand（）%GXTnum;
	y=rand（）%GXTnum;
	
	if（x>y）
	{	
		t=x;
		x=y;
		y=t;
	}
	iscross=（float）（rand（）%100/100.0）;
	
	
	if （iscross	{
		q=（int*）malloc（sizeof（int）*（y-x+1））;
		p=q;
		for（i=x;i<=y;i++）
		{
			*（p++）=location（pDadipMum）;
			
		}
		
		//对杂交的位置进行排序
		for（i=0;i		{
			min=*（q+i）;
			k=i;
			for（j=i+1;j			{
				if（min>*（q+j））
				{
					min=*（q+j）;
					k=j;
				}
				
			}
			t=*（q+i）;
			*（q+i）=*（q+k）;
			*（q+k）=t;
		}
		//进行交换
		for（i=x;i<=y;i++）
		{t=*（pDad+i）;
		j=*（q++）;
		*（pDad+i）=*（pMum+j）;
		*（pMum+j）=t;
		}
		
	}
	
	
}



//求某个基因对应的工序的工时
int GetGenetime（int *pchromoint iGZ *pGZGX*pGXint GZnum）
{	
	int jk=0txsum;
	x=*（pchromo+i）;
	
	for（j=0;j	{//求得属于哪个工种
		x=x-（pGZ+j）->GJnum;
		if （x<=0）
		{
			break;
		}
		
	}
	t=0;

	x=*（pchromo+i）;
	for（k=0;k	{
		if （*（pchromo+k）==x）
			t++;
	}
	sum=0;
	for（k=0;k		sum=sum+（pGZ+k）->GXnum;
	
	return（（pGX+t+sum）->time）;
	
}



int getGZcode（int GJint GZnumGZ *pGZ）
{
	
	int j;
	
	for（j=0;j	{
		GJ=GJ-（pGZ+j）->GJnum;
		if （GJ<=0）
		{
			break;
		}
		
	}
	return j;
}



//求染色体上某个基因对应的机床号
int JCcode（int *pchromoint iGZ *pGZGX*pGXint GZnum）
{
	int jk=0txsum;
	x=*（pchromo+i）;
	
	for（j=0;j	{
		x=x-（pGZ+j）->GJnum;
		if （x<=0）
		{
			break;
		}
		
	}

    t=0;
	x=*（pchromo+i）;
	for（k=0;k	{
		if （*（pchromo+k）==x）
			t++;
	}
	sum=0;
	for（k=0;k		sum=sum+（pGZ+k）->GXnum;

	return（（pGX+t+sum）->machine）;
	
}




int AtJCnum（int iint *pchromoint GXTnumGZ *pGZGX *pGXint GZnum）
{//求某一机床号上的基因个数
	int jkt=0;
	
	for（j=0;j	{
		k=JCcode（pchromojpGZpGXGZnum）;
		if （k==i）t++;
	}
	return t;
}


void Mutation（float MutationRateint *pchromoint GXTnumGZ *pGZGX *pGXint GZnum）
{//变异
	float ismul;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     168960  2008-06-02 18:41  基于混合遗传算法车间调度优化\论文.doc

     文件      16737  2008-06-18 21:58  基于混合遗传算法车间调度优化\车间结稿\GA.c

     文件      19700  2008-06-18 21:57  基于混合遗传算法车间调度优化\车间结稿\GASA.c

     文件       9995  2008-06-18 21:58  基于混合遗传算法车间调度优化\车间结稿\车间结稿.rar

     文件       3740  2008-05-29 09:50  基于混合遗传算法车间调度优化\遗传算法退火算法\matlabTSP.m

     文件     183659  2008-05-29 10:01  基于混合遗传算法车间调度优化\遗传算法退火算法\一种基于遗传算法的车间调度算法求解.pdf

     文件     150746  2008-05-29 10:02  基于混合遗传算法车间调度优化\遗传算法退火算法\基于混合遗传算法的车间调度问题的研究.pdf

     文件     176371  2008-05-29 10:00  基于混合遗传算法车间调度优化\遗传算法退火算法\基于混合遗传算法的车间调度问题研究.pdf

     文件     137442  2008-05-29 09:56  基于混合遗传算法车间调度优化\遗传算法退火算法\基于遗传算法的车间作业调度.pdf

     文件      35560  2005-07-16 14:18  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\Data_discrete_analysis.m

     文件       2852  2005-07-18 13:52  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\main.m

     文件       3235  2005-07-18 15:09  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\main_88.asv

     文件       3320  2005-07-18 16:52  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\main_88.m

     文件        572  2005-07-10 21:21  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\Rand_Tong_yong.m

     文件         59  2005-07-13 09:52  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\wh_JC.m

     文件        269  2005-07-10 21:16  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\Wh_rand.m

     文件      35759  2005-07-16 15:18  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\wh_test.m

     文件     116538  2005-07-18 10:34  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\wh_test_44.m

     文件     233976  2005-07-16 14:21  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\wh_test_88.m

     文件         69  2005-07-13 09:55  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火法（Sb除Sw）\模拟退火法（Sb除Sw）\wh_ZHS.m

     文件        174  2006-11-24 16:52  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法\1.txt

     文件        304  2006-11-24 16:53  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法\2.txt

     文件       4716  2007-12-13 20:28  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法\main.cpp

     文件      31232  2008-06-01 07:22  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法.doc

     文件       5882  2008-05-28 21:12  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法.mht

     文件    6416546  2008-05-28 21:26  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法.pdf

     文件      61667  2008-05-29 09:51  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法_百度百科.mht

     文件     109332  2008-05-29 09:48  基于混合遗传算法车间调度优化\遗传算法退火算法\模拟退火算法源程序（转）_I.mht

     文件      18952  2008-05-31 12:09  基于混合遗传算法车间调度优化\遗传算法退火算法\研学论坛 - Re【原创】车间作业调度问题遗传算法通用Matlab程序（附图）.files\33725376.jpg

     文件        161  2008-05-31 11:41  基于混合遗传算法车间调度优化\遗传算法退火算法\研学论坛 - Re【原创】车间作业调度问题遗传算法通用Matlab程序（附图）.files\advu.gif

............此处省略209个文件信息