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

零件加工时间最优的动态规划模型摘要零件加工最有时间问题是典型的动态规划问题。建立一个动态规划模型，按照这类问题的基本思路，抓住等待时间这一关键要素，运用计算机模拟求解（我们用C写了一个程序（见附录），可以模拟零件个数12以内的所有情况，得出最优时间和零件编号的顺序。程序已做成文件，与论文的电子稿一起放在ftp上）。关键词：动态规划；机床零件；时间最优；1问题的重述例题3(工件排序问题)某修理车间因修理工作需要生产个不同的工件，每个工件都需要先在机床，后在机床上进行加工。不妨用编号分别代表不同的工件，以、表示工件 需在，机床上加工的时间。如果该车间只有一台机床，一台 机床，且、不受加工工件顺序的影响，问如何安排零件在，机床上的加工顺序，才能使机床加工总时间（从机床开始加工，至两机床均将工件加工完为止）最短？2 约定符号和名词解释：为第阶段选择的零件需要的等待时间。：为零件通过机床的顺序编号的集合；：为顺序集合中第个元素，即为第阶段选择的零件的编号。3 问题的分析对于零件加工求解时间最优的问题，是典型的动态规划问题。根据题目，首先将问题划分个阶段,每个阶段选择一个零件，将零件的编号计入数组，通过计算等待时间的最小值，来确定选择的零件顺序。根据题目可知，零件一定要先经过机床，才能通过机床，那么机床应该是不停工作的；而机床前一个零件的加工时间长短，直接影响机床目前零件能否立刻加工，若机床前一个零件加工时间过长，就必须停下来等待，才而产生现等待时间。本问题正是要抓住等待时间这一变化量，列出递推公式，用计算机模拟求得结果。4 模型的假设根据题目，提出以下几个假设：（1）假设加工零件在同一条流水生产线上，即零件通过A机床的顺序与通过B机床的顺序一致。5 问题模型的建立5.1问题的进一步分析既然是典型的动态规划问题，就可以用通用的解题思想和步骤进行求解，即将多阶段决策过程最优化问题划分阶段, 恰当地选取状态变量、决策变量及定义最优指标函数。根据题目，共有个零件，那么就将整个过程分为个阶段，每次阶段选择一个零件，把每次选择的零件编号存入一个数组中，用这个数组来记录零件通过机床的顺序；将等待时间作为状态变量，而把零件加工的总时间作为指标函数。最终问题就是解最小的零件加工时间。5.2模型的建立和求解首先，设每个零件的等待时间为，不需要等待的零件 “0”。根据题目，零件一定要先经过机床，才能通过机床，那么机床应该是不停工作的，而机床会由于机床前一个零件加工时间过长而出现等待时间。如图所示列出等待时间的函数：第一个零件不需要等待，时间是，从第二个零件起，等待时间： （5.1）根据上图，加工所有零件所需要的总时间是第一个零件的机床时间、所有零件的机床加工时间、所有等待时间三者之和，为： ， （5.2）根据穷举法，通过C语言编程（程序见附录），可解得最终数据。6 模型的评价和推广零件加工时间最优问题，是最简单最常用的动态规划问题。本问题中的模型就是针对这类问题建立的，模型的优点：能准确的计算住零件加工的顺序，和所需的时间。模型的缺点：模型的时间复杂度是，当零件个数较多时（从超过9个开始），模型运算所需的时间飙升，对零件个数较大的情况，这个模型无能为力。参考文献1张润琦，动态规划，1989：10-18.2秦学志，实用最优方法，第三版，大连：大连理工大学出版社，2007.附录C语言编写的程序为：#include#include#include #define cl (clock_t)1)/计算时间函数#define M 23int n,t=0,sM,reM;double aM,bM,tm=111111111,tn=0.0,wt=0.0;double max(double x,double y)if(xy)return x;elsereturn y;double sum1(int x,int y)double all=0.0;int i=0;for(i=x;i=y;i+)all+=ai;return all;double sum2(int x,int y)double all=0.0;int i=0;for(i=x;ibp0)wt+=ap1-bp0;for(i=0;i1)if(sum1(i-k,i)=sum2(i-k-1,i-1)wt+=max(sum1(i-k,i)-sum2(i-k-1,i-1),0); k=1;break;elsek+;break;for(i=0;itn)tm=tn;for(i=0;in;i+)rei=pi+1;void sort(int t)int i=0,op=0,j;if(t=n)time(s);elsefor(i=0;in;i+)op=1;for(j=0;jt;j+)if(sj=i)op=0;break;if(op)st=i;t+;sort(t);t-;void main()int i=0;/clock_t begin,finsh;/计算时间函数/double ss; /计算时间函数/begin=clock();/计算时间函数printf(请输入工件个数 (建议个数小于12 否则需要耐心等待 哟 亲！) n); scanf(%d,&n);for(i=0;in;i+)printf(请输入A机器加工第%d工件的时间 n,i+1); scanf(%lf,&ai);for(i=0;in;i+)printf(请输入B机器加工第%d工件的时间 n,i+1); scanf(%lf,&bi); for(i=0;in;i+)s0=i;sort(1); / finsh=clock();/计算时间函数/ss=(finsh-begin)/cl;/计算时间函数pri