1999人阅读
算法（27）
问题描述：一个找出通过工厂装配线的最快方式的制造问题。共有两条装配线，每条有n个装配站，装配线i的第j个装配站完成工作需要的时间为a[i][j] 。在通过i装配线的第j个装配站后，产品可以直接进入i装配线的j+1个装配站，当中不需要损耗时间；产品也可以进入另外一条装配线的j+1个装配站，这个过程需要损耗t[i][j]时间。产品从初始站进入装配线分别需要损耗时间为e[0],e[1] ，产品从装配线进入终点站分别需要时间为x[0],x[1]。求一个产品从初始站到达终点站的最快路径。
分析：令f0[j]代表从初始站到在0号线上完成第j站操作所需的最少时间。令f1[j]代表从初始站到在1号线上完成第j站操作所需的最少时间。他们存在这样的递推关系。
#include &iostream&
#define MAXASSEMBLE 10000
* @brief Get the fast way in the assembly line schedule
* @param a[][MAXASSEMBLE]: a[i][j] means the time consumed in j'th assembly station of i'th AssemblyLine. The index of j is from 0 to n-1.
* @param t[][MAXASSEMBLE]: t[i][j] means the time consumed to move object from j'th station in i'th AssemblyLine to j+1'th station in the other AssemblyLine. The index of j is from 0 to n-2.
* @param e: e[i] means the time consumed to move object from start station to 0'th station in i'th AssemblyLine.
* @param x: x[i] means the time consumed to move object from n-1'th station in i'th AssemblyLine to end station.
* @param n: the station number in AssemblyLine.
* @param time: the least time consumed to move object from start station to end station.
* @param line[][MAXASSEMBLE]: line[i][j] means the pre-station's AssemblyLine number of station j+1 in AssemblyLine i.
* @param lastLine: the pre-station's AssemblyLine number of the end station.
void FastestWay(double a[][MAXASSEMBLE], double t[][MAXASSEMBLE], double* e, double* x, int n, double &time, int line[][MAXASSEMBLE], int &lastLine)
double lastWay0 = e[0] + a[0][0];
double lastWay1 = e[1] + a[1][0];
double Way0;
double Way1;
for (int i = 1; i & ++i)
//choose the way according last way
if (lastWay0 & lastWay1 + t[1][i - 1])
Way0 = lastWay0 + a[0][i];
line[0][i - 1] =
Way0 = lastWay1 + t[1][i - 1] + a[0][i];
line[0][i - 1] = 1;
if (lastWay1 & lastWay0 + t[0][i - 1])
Way1 = lastWay1 + a[1][i];
line[1][i - 1] = 1;
Way1 = lastWay0 + t[0][i - 1] + a[1][i];
line[1][i - 1] = 0;
lastWay0 = Way0;
lastWay1 = Way1;
//choose the last step
if (lastWay0 + x[0] & lastWay1 + x[1])
time = lastWay0 + x[0];
lastLine = 0;
time = lastWay1 + x[1];
lastLine = 1;
* @brief Print the path
* @param lastLine: the pre-station's AssemblyLine number of the end station
* @param line[][MAXASSEMBLE]: the path matrix
* @param n: the number of stations in one AssemblyLine
void PrintPath(int lastLine, int line[][MAXASSEMBLE], int n)
cout && n && &step: & && lastLine &&
while (--n & 0)
cout && n && &step: & && line[lastLine][n - 1] &&
lastLine = line[lastLine][n - 1];
int main()
double a[2][MAXASSEMBLE];
double t[2][MAXASSEMBLE];
int line[2][MAXASSEMBLE];
double e[2];
double x[2];
while (cin && n, n != 0)
for (int i = 0; i & ++i)
cin && a[0][i];
for (int i = 0; i & ++i)
cin && a[1][i];
for (int i = 0; i + 1 & ++i)
cin && t[0][i];
for (int i = 0; i + 1 & ++i)
cin && t[1][i];
cin && e[0] && e[1] && x[0] && x[1];
FastestWay(a, t, e, x, n, time, line, lastline);
cout && &Least time: & && time &&
PrintPath(lastline, line, n);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：162311次
积分：2253
积分：2253
排名：第13056名
原创：64篇
转载：14篇
评论：41条
(3)(1)(1)(6)(5)(1)(1)(1)(2)(1)(20)(29)(5)(2)动态规划-装配线调度
问题描述：
一个找出通过工厂装配线的最快方式的制造问题。共有两条装配线，每一条装配线上有n个装配站，编号为j = 0, 1, & , n & 1。装配线i(i = 0或1)，在装配站S[i][j]上所需的装配时间记为a[i][j]。一个汽车底盘进入工厂，然后进入装配线i的进入时间为e[i]，在通过一条线的第j个装配站后，这个底盘来到任一条线的第(j + 1)个装配站。如果留在相同的装配线上，则没有移动的开销；如果在装配站S[i][j]后，它移动到了另一条线上，则花费时间t[i][j]。在离开一条线的第n个装配站后，完成的汽车离开装配线i的离开时间为x[i] 。
状态转移方程：
代码实现：
//动态规划，工厂装配线&&
#include&iostream&&&
//e1,e2是两条装配生产线的输入耗费x1，x2是输出耗费，a1[i]是第一条生产线的第i个站耗时，t1，t2记录了两条生产线转换时耗时&&
//f1[i]为记录第一条生产线上第i个站生产耗时最少时间，L1[i]记录了第一条生产线上第i个站生产耗时最少时，前一站是那条生产线上的&&
//length为每条生产线上的站数&&
void FastWay(int e1,int e2,int *a1,int *a2,int x1,int x2,int *f1,int *f2,int *L1,int *L2,int &L,int *t1,int *t2,int length)&
&&& f1[1]=e1+a1[1];&
&&& f2[1]=e2+a2[1];&
&&& for(i=2;i&i++)&
&&&&&&& if(f1[i-1]+a1[i]&f2[i-1]+a1[i]+t2[i-1])&
&&&&&&& {&
&&&&&&&&&&& f1[i]=f1[i-1]+a1[i];&
&&&&&&&&&&& L1[i]=1;&
&&&&&&& }&
&&&&&&& else&
&&&&&&& {&
&&&&&&&&&&& f1[i]=f2[i-1]+a1[i]+t2[i-1];&
&&&&&&&&&&& L1[i]=2;&
&&&&&&& }&
&&&&&&& if(f2[i-1]+a2[i]&f1[i-1]+a2[i]+t1[i-1])&
&&&&&&& {&
&&&&&&&&&&& f2[i]=f2[i-1]+a2[i];&
&&&&&&&&&&& L2[i]=2;&
&&&&&&& }&
&&&&&&& else&
&&&&&&& {&
&&&&&&&&&&& f2[i]=f1[i-1]+a2[i]+t1[i-1];&
&&&&&&&&&&& L2[i]=1;&
&&&&&&& }&
&&& //利用f1[length]来存储所用最短时间&&
&&& if(f1[length-1]+x1&f2[length-1]+x2)&
&&&&&&& f1[length]=f1[length-1]+x1;&
&&&&&&& L=1;&
&&&&&&& f1[length]=f2[length-1]+x2;&
&&&&&&& L=2;&
//输出最短时间以及所需要的路线&&
void Printanswser(int *L1,int *L2,int L,int length,int *f1)&
&&& int i=L;&
&&& cout&&&the fast time is : &&&f1[length+1]&&&
&&& cout&&&the station : &&&length&&& is on line: &&&i&&&
&&& for(j=j&=2;j--)&
&&&&&&& if(i==1)&
&&&&&&& {&
&&&&&&&&&&& i=L1[j];&
&&&&&&& }&
&&&&&&& else&
&&&&&&& {&
&&&&&&&&&&& i=L2[j];&
&&&&&&& }&
&&&&&&& cout&&&the station : &&&j-1&&& is on line: &&&i&&&
int main()&
&&& int e1=2,e2=4,x1=3,x2=2;&
&&& int a1[8]={0,7,9,3,4,8,4};&
&&& int a2[8]={0,8,5,6,4,5,7};&
&&& int t1[6]={0,2,3,1,3,4};&
&&& int t2[6]={0,2,1,2,2,1};&
&&& int f1[8],f2[7],L1[7],L2[7],L;&
&&& FastWay(e1,e2,a1,a2,x1,x2,f1,f2,L1,L2,L,t1,t2,7);&
&&& Printanswser(L1,L2,L,6,f1);&
&&& return 0;&
//动态规划，工厂装配线
#include&iostream&
//e1,e2是两条装配生产线的输入耗费x1，x2是输出耗费，a1[i]是第一条生产线的第i个站耗时，t1，t2记录了两条生产线转换时耗时
//f1[i]为记录第一条生产线上第i个站生产耗时最少时间，L1[i]记录了第一条生产线上第i个站生产耗时最少时，前一站是那条生产线上的
//length为每条生产线上的站数
void FastWay(int e1,int e2,int *a1,int *a2,int x1,int x2,int *f1,int *f2,int *L1,int *L2,int &L,int *t1,int *t2,int length)
&f1[1]=e1+a1[1];
&f2[1]=e2+a2[1];
&for(i=2;i&i++)
&&if(f1[i-1]+a1[i]&f2[i-1]+a1[i]+t2[i-1])
&&&f1[i]=f1[i-1]+a1[i];
&&&L1[i]=1;
&&&f1[i]=f2[i-1]+a1[i]+t2[i-1];
&&&L1[i]=2;
&&if(f2[i-1]+a2[i]&f1[i-1]+a2[i]+t1[i-1])
&&&f2[i]=f2[i-1]+a2[i];
&&&L2[i]=2;
&&&f2[i]=f1[i-1]+a2[i]+t1[i-1];
&&&L2[i]=1;
&//利用f1[length]来存储所用最短时间
&if(f1[length-1]+x1&f2[length-1]+x2)
&&f1[length]=f1[length-1]+x1;
&&f1[length]=f2[length-1]+x2;
//输出最短时间以及所需要的路线
void Printanswser(int *L1,int *L2,int L,int length,int *f1)
&cout&&&the fast time is : &&&f1[length+1]&&
&cout&&&the station : &&&length&&& is on line: &&&i&&
&for(j=j&=2;j--)
&&if(i==1)
&&&i=L1[j];
&&&i=L2[j];
&&cout&&&the station : &&&j-1&&& is on line: &&&i&&
int main()
&int e1=2,e2=4,x1=3,x2=2;
&int a1[8]={0,7,9,3,4,8,4};
&int a2[8]={0,8,5,6,4,5,7};
&int t1[6]={0,2,3,1,3,4};
&int t2[6]={0,2,1,2,2,1};
&int f1[8],f2[7],L1[7],L2[7],L;
&FastWay(e1,e2,a1,a2,x1,x2,f1,f2,L1,L2,L,t1,t2,7);
&Printanswser(L1,L2,L,6,f1);
&return 0;
运行结果：
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'1852人阅读
算法（35）
问题描述：有二条流水线，每条流水线都有n个站，流水线1,2站j的处理功能相同，但处理时间可能不同，每个站都有一个处理时间，而且从一条流水线的站j-1到另一条流水线站j有一个消耗时间t1[j-1](从流水线1到2）或t2[j-1](从流水线2到1)，同一条流水线站j-1到站j的消耗时间忽略不计，物品上每一条流水线有个时间，下每一条流水线也有一个时间。
--------------------------目标：找出处理物品的最小时间（动态规划问题）---------------------
分析问题，比如一个底盘要到达S[1][j]，则有两种情况，第一种是从S[1][j-1]到S[1][j]，第二种是从S[2][j-1]到S[1][j]。找出这两者所花时间的最小，则就是S[1][j]所需时间的最小。
这就是有局部最优解求全局最优解。也就是说，一个问题的最优解包含了子问题的一个最优解。我们称这个性质为最优子结构。这是是否可以应用DP的标志之一。
找出这个递归关系，由步骤一可以得到这个递归关系：
因为递归的关系，一般总是可以转换为非递归的算法。
由已知量f1[1], f2[1]逐步推出未知量，推啊推，推啊推，最后就推到结果了~~~~
再由已知结果返回求路径。
这一节最给力的就是这个例子以及相应的图：
代码示例：
#include &stdio.h&
#include &string.h&
//N表示有几个站
const int N = 6;
//根据书上的伪代码写出程序
//void PrintStation( int l[][N + 1], int lResult, int n)
// int i = lR
// printf(&line %d , station %d\n&, i, n);
// for( int j = j &= 2; j--)
i = l[i][j];
printf(&line %d , station %d\n&, i, j - 1);
// 递归顺序输出结果,见习题15.1-1
void PrintStation( int l[][ N + 1], int lResult, int n)
if( n == 0 )
int i, j =
i = lResult, j = l[i][n];
PrintStation( l, j, n - 1 );
printf(&line %d , station %d\n&, i, n);
void FastestWay()
int e[3] = {0, 2, 4 };
int x[3] = {0, 3, 2 };
int t[3][N] = {{0, 0, 0, 0, 0, 0 },{0, 2, 3, 1, 3, 4}, { 0, 2, 1, 2, 2, 1}};
int a[3][ N + 1 ] = { {0, 0, 0,0, 0, 0, 0},{0, 7, 9, 3, 4, 8, 4}, {0, 8, 5, 6, 4, 5, 7}};
//存放结果
int f[3][ N + 1];
//辅助数组，用以产生最有解
int l[3][ N + 1];
memset( f, 0, sizeof( f[0][0] ) * ( 3*(N + 1) ) );
memset( l, 0, sizeof( f[0][0] ) * ( 3*(N + 1) ) );
f[1][1] = e[1] + a[1][1];
f[2][1] = e[2] + a[2][1];
for( j = 2; j &= N; j++ )
//给f[1][j]赋值
if( f[1][ j - 1] + a[1][j] &= f[2][ j - 1] + a[1][j] + /*运输代价*/ t[2][j - 1] )
f[1][ j - 1] + a[1][j];
l[1][j] = 1;
f[1][j] = f[2][ j - 1] + a[1][j] + /*运输代价*/ t[2][j - 1];
l[1][j] = 2;
//给f[2][j]赋值
if( f[2][ j - 1] + a[2][j] &= f[1][ j - 1] + a[2][j] + /*运输代价*/ t[1][j - 1] )
f[2][ j - 1] + a[2][j];
l[2][j] = 2;
f[2][j] = f[1][ j - 1] + a[2][j] + /*运输代价*/ t[1][j - 1];
l[2][j] = 1;
if( f[1][N] + x[1] &= f[2][N] + x[2] )
fResult = f[1][N] + x[1];
lResult = 1;
fResult = f[2][N] + x[2];
lResult = 2;
PrintStation( l, lResult, N);
printf(&总的代价：%d\n&, fResult);
int main()
FastestWay();
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：596689次
积分：6964
积分：6964
排名：第2439名
原创：135篇
转载：35篇
评论：109条
本博客乃学习笔记，没有纯粹无意义的转载。作者除了对自己负责，不对任何读者负责。欢迎指出文章错误，如果原意交朋友，可以通过Gmail联系我（），博客基本不再更新，欢迎访问我的独立博客
(5)(2)(1)(1)(14)(22)(11)(48)(30)(17)(22)(4)基于混流装配线调度问题的新颖蚁群算法--《计算机测量与控制》2013年10期
基于混流装配线调度问题的新颖蚁群算法
【摘要】：研究混流装配线调度问题,提出了一种用于求解该问题的新颖蚁群算法;该算法定义了适合求解该问题的信息素表示方法和更新公式,并结合解的质量定义了兴趣度;结合每代所产生的最优解构建知识库,并给出每个具体分配方案所占的次数比重;结合兴趣度和比重定义了经验概率因子;通过对具体实例进行求解,说明了算法的可行性;同时,针对同一实例,结果发现:如果迭代次数相同,则该算法求得的目标函数值小于Ant求得的目标函数值,且该算法求得的结果优于其他算法;可见,该算法解决问题的性能较优。
【作者单位】：
【关键词】：
【基金】：
【分类号】：TP18【正文快照】：
0引言混流装配线调度问题[1]指的是按照数量和品种均衡的要求,依据日均产量和型号比例的规定,在同一单位时间内在一条生产线上生产出多种不同型号的产品,从而满足市场的多样化需求。目前,已用来解决该问题的方法主要有:目标追随法、遗传算法、模拟退火算法、蚁群算法及粒子群
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
徐红梅;陈义保;刘加光;王燕涛;;[J];山东理工大学学报(自然科学版);2008年01期
侯思颖;;[J];西华大学学报(自然科学版);2010年06期
李楠;胡即明;;[J];中国水运(下半月);2008年05期
马骏;张健沛;杨静;程丽丽;;[J];北京邮电大学学报;2008年06期
刘晓东;冒勇军;;[J];计算机工程;2009年16期
彭沛夫;张桂芳;;[J];计算机工程与应用;2010年04期
蒋建国;夏娜;齐美彬;木春梅;;[J];电子学报;2005年12期
段海滨;马冠军;王道波;于秀芬;;[J];系统仿真学报;2007年05期
赵翔;黄厚宽;;[J];广西师范大学学报(自然科学版);2008年01期
康莉;谢维信;黄敬雄;;[J];电子学报;2008年03期
中国重要会议论文全文数据库
宁静;王桂棠;吴黎明;刘军;;[A];2007'仪表，自动化及先进集成技术大会论文集（一）[C];2007年
周龙;霍婷婷;;[A];第三届中国智能计算大会论文集[C];2009年
刘杰;闫清东;;[A];逻辑学及其应用研究——第四届全国逻辑系统、智能科学与信息科学学术会议论文集[C];2008年
宋春峰;侯媛彬;赵圣刚;;[A];第十四届全国煤矿自动化学术年会暨中国煤炭学会自动化专业委员会学术会议论文集[C];2004年
严彬;熊伟清;程美英;叶青;;[A];第二十七届中国控制会议论文集[C];2008年
师凯;蔡延光;邹谷山;王涛;;[A];04'中国企业自动化和信息化建设论坛暨中南六省区自动化学会学术年会专辑[C];2004年
张宁;徐晓静;;[A];第九届中国青年信息与管理学者大会论文集[C];2007年
何灿;邢建春;杨启亮;王荣浩;王书怀;;[A];中国自动化学会控制理论专业委员会D卷[C];2011年
王旭;张江;崔平远;;[A];2003年中国智能自动化会议论文集（下册）[C];2003年
张丹;华红艳;邵丽红;;[A];中国自动化学会中南六省（区）2010年第28届年会·论文集[C];2010年
中国博士学位论文全文数据库
程世娟;[D];西南交通大学;2009年
薛云;[D];中南大学;2008年
杨剑峰;[D];浙江大学;2007年
周爽;[D];哈尔滨工业大学;2010年
柏继云;[D];哈尔滨工业大学;2013年
叶强;[D];合肥工业大学;2008年
陈岩;[D];国防科学技术大学;2007年
吕勇;[D];浙江大学;2005年
李丽香;[D];北京邮电大学;2006年
李艳君;[D];浙江大学;2001年
中国硕士学位论文全文数据库
辛雅斐;[D];暨南大学;2008年
武交峰;[D];太原理工大学;2007年
康望星;[D];哈尔滨工程大学;2006年
陈建玲;[D];大庆石油学院;2007年
潘鹏竹;[D];沈阳工业大学;2010年
张建民;[D];新疆农业大学;2010年
陈冲;[D];哈尔滨工业大学;2010年
吕冬梅;[D];吉林大学;2005年
王爱军;[D];大庆石油学院;2005年
高彦明;[D];苏州大学;2005年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号您的位置： &
一种类微粒群算法及其在混流装配线调度问题中的应用}