零件加工时间最优化动态规划模型.doc

***零件加工时间最优的动态规划模型蚅蝿摘要薀袇零件加工最有时间问题是典型的动态规划问题。建立一个动态规划模型,按照这类问题的基本思路,抓住等待时间这一关键要素,运用计算机模拟求解(我们用C写了一个程序(见附录),可以模拟零件个数12以内的所有情况,得出最优时间和零件编号的顺序。程序已做成文件,与论文的电子稿一起放在ftp上)。蒂关键词:动态规划;机床零件;时间最优;肂罿蚇蒄芀荿1问题的重述肄例题3(工件排序问题)薅某修理车间因修理工作需要生产个不同的工件,每个工件都需要先在机床,后在机床上进行加工。不妨用编号分别代表不同的工件,以、表示工件需在,机床上加工的时间。如果该车间只有一台机床,一台机床,且、不受加工工件顺序的影响,问如何安排零件在,机床上的加工顺序,才能使机床加工总时间(从机床开始加工,至两机床均将工件加工完为止)最短?薃螈袄莂蚁约定符号和名词解释芈:为第阶段选择的零件需要的等待时间。薅:为零件通过机床的顺序编号的集合;蒄:为顺序集合中第个元素,即为第阶段选择的零件的编号。蝿蚇莅蒅膂问题的分析肆对于零件加工求解时间最优的问题,是典型的动态规划问题。根据题目,首先将问题划分个阶段,每个阶段选择一个零件,将零件的编号计入数组,通过计算等待时间的最小值,来确定选择的零件顺序。肅根据题目可知,零件一定要先经过机床,才能通过机床,那么机床应该是不停工作的;而机床前一个零件的加工时间长短,直接影响机床目前零件能否立刻加工,若机床前一个零件加工时间过长,就必须停下来等待,才而产生现等待时间。本问题正是要抓住等待时间这一变化量,列出递推公式,用计算机模拟求得结果。芃芀模型的假设螀袆根据题目,提出以下几个假设:莄(1)假设加工零件在同一条流水生产线上,即零件通过A机床的顺序与通过B机床的顺序一致。,就可以用通用的解题思想和步骤进行求解,即将多阶段决策过程最优化问题划分阶段,恰当地选取状态变量、决策变量及定义最优指标函数。螈根据题目,共有个零件,那么就将整个过程分为个阶段,每次阶段选择一个零件,把每次选择的零件编号存入一个数组中,用这个数组来记录零件通过机床的顺序;将等待时间作为状态变量,而把零件加工的总时间作为指标函数。最终问题就是解最小的零件加工时间。,设每个零件的等待时间为,不需要等待的零件“0”。根据题目,零件一定要先经过机床,才能通过机床,那么机床应该是不停工作的,而机床会由于机床前一个零件加工时间过长而出现等待时间。如图所示芈芇蒄列出等待时间的函数:蒁第一个零件不需要等待,时间是蚇,羇从第二个零件起,等待时间:芁()薀根据上图,加工所有零件所需要的总时间是第一个零件的机床时间、所有零件的机床加工时间、所有等待时间三者之和,为:肆,()螇根据穷举法,通过C语言编程(程序见附录),可解得最终数据。芃羂模型的评价和推广螀膄零件加工时间最优问题,是最简单最常用的动态规划问题。本问题中的模型就是针对这类问题建立的,莄模型的优点:能准确的计算住零件加工的顺序,和所需的时间。肀模型的缺点:模型的时间复杂度是,当零件个数较多时(从超过9个开始),模型运算所需的时间飙升,对零件个数较大的情况,这个模型无能为力。腿羄参考文献膁[1]张润琦,《动态规划》,1989:10-[2]秦学志,《实用最优方法》,第三版,大连:大连理工大学出版社,:膃#include<>薁#include<>肈#include<>蒅#definecl((clock_t)1)//计算时间函数芄#defineM23虿intn,t=0,s[M],re[M];蒇doublea[M],b[M],tm=111111111,tn=,wt=;膅doublemax(doublex,doubley)肁{肂 if(x>y)羇 returnx;羆 else肃 returny;膀}薀doublesum1(intx,inty)蚆{膄 doubleall=;艿 inti=0;聿 for(i=x;i<=y;i++)莆 all+=a[i];羁 returnall;蚁}葿doublesum2(intx,inty)***{肃 doubleall=;蝿 inti=0;袈 for(i=x;i<=y;i++)袇 all+=b[i];肄 returnall;肂}莇voidtime(int*p)蚇{袂 intj=0,k=1,i=0;芀 wt=;螇 if(a[p[1]]>b[p[0]]) 肄 wt+=a[p[1]]-b[p[0]];羃 for(i=0;i<n;i++)莈 while(i>1)膆 if(s