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

1、零件加 工时间 最优的 动态规 划模型摘要零件加工最有时间问题是典型的动态规划问题。建立一个动态规划模型，按照这类问题的基本 思路，抓住等待时间这一关键要素，运用计算机模拟求解（我们用C写了一个程序（见附录），可 以模拟零件个数12以内的所有情况，得出最优时间和零件编号的顺序。程序己做成.em文件，与 论文的电子稿一起放在ftp上）。关键词：动态规划；机床零件；时间最优；1问题的重述例题3（工件排序问题）某修理车间因修理工作需要生产个不同的工件，每个工件都需要先在A机床，后在A机床上 进行加工。不妨用1,2,3,.,编号分别代表不同的工件，以.、表示工件，需在A, B机床上加 工的时间。如果该

2、车间只有一台A机床，一台B机床，且为、不受加工工件顺序的影响，问如 何安排零件在A , B机床上的加工顺序，才能使机床加工总时间（从A机床开始加工，至两机床均 将工件加工完为止）最短？2约定符号和名词解释4 = max气-妃,0：为第#阶段选择的零件需要的等待时间。S：为零件通过机床的顺序编号的集合；力：为顺序集合S中第小个元素，即为第k阶段选择的零件的编号。3问题的分析对于零件加工求解时间最优的问题，是典型的动态规划问题。根据题目，首先将问题划分个 阶段，每个阶段选择一个零件，将零件的编号计入数组公，通过计算等待时间的最小值，来确定选 择的零件顺序。根据题目可知，零件一定要先经过A机床，才能

3、通过B机床，那么人机床应该是不停工作的; 而A机床前一个零件的加工时间长短，直接影响矿机床目前零件能否立刻加工，若A机床前一个零 件加工时间过长，B就必须停下来等待，才而产生现等待时间。本问题正是要抓住等待时间这一变 化量，列出递推公式，用计算机模拟求得结果。4模型的假设根据题目，提出以下儿个假设：（1）假设加工零件在同一条流水生产线上，即零件通过A机床的顺序与通过B机床的顺序一 致。5问题模型的建立5. 1问题的进一步分析既然是典型的动态规划问题，就可以用通用的解题思想和步骤进行求解，即将多阶段决策过程 最优化问题划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数。根据题目，共有个零件

4、，那么就将整个过程分为个阶段，每次阶段选择一个零件，把每次 选择的零件编号存入一个数组中，用这个数组来记录零件通过机床的顺序；将等待时间作为状态变 量，而把零件加工的总时间作为指标函数。最终问题就是解最小的零件加工时间。5. 2模型的建立和求解首先，设每个零件的等待时间为4,不需要等待的零件7； “0”。根据题目，零件一定要先经 过A机床，才能通过B机床，那么A机床应该是不停工作的，而B机床会由于A机床前一个零件加 工时间过长而出现等待时间。如图所示列出等待时间的函数：第一个零件不需要等待，时间是7 = 0,从第二个零件起，等待时间：Tk = max官-虹,0,(A = 2,3,.)(5. 1

5、)根据上图，加工所有零件所需要的总时间是第一个零件的A机床时间、所有零件的B机床加工时间打、所有等待时间4三者之和，为：1=1* = %+文小，(5.2)1=1根据穷举法，通过C语言编程(程序见附录)，可解得最终数据。6模型的评价和推广零件加工时间最优问题，是最简单最常用的动态规划问题。本问题中的模型就是针对这类问题 建立的，模型的优点：能准确的计算住零件加工的顺序，和所需的时间。模型的缺点：模型的时间复杂度是!，当零件个数较多时(从超过9个开始)，模型运算所需 的时间飙升，对零件个数较大的情况，这个模型无能为力。参考文献张润琦，动态规划，1989： 10-18.秦学志，实用最优方法，第三版，

6、大连：大连理工大学出版社，2007.附录C语言编写的程序为：#iiiclude#iiicludeinclude #define cl (clock_t)l)计算时间函数define M 23int n.t=O,sM jeM;double aM.bM jm= 111111111 ,tn=0.0am=0.0:double max(double x,double y)】f(xy)return x;elsereturn y;double suml(iiit y)double all=0.0:mt 1=0;fbr(i=x;i=y;i+) all+=ai;retuni all;double suni2(m

7、t x.mt y)double all=0.0;mt 1=0;fbr(i=x;ibpO)wt+=apl-bp0;fbr(i=0;i=sum2(i-k-1 ,i 1)wt+=max(suml (i-kj)-suni2(i-k-1 j-1 ),0); k=l;break;elsek+;break;)fbr(i=0;itn)tm=tn;fbr(i=0;in;i+)rei=pi+l;void sort(int t)int i=0,op=0,j;tune(s);elsefor(i=0;in;i-H-)fiop=l；for(j=Ojtj+)if(s|j=i)(op=0；break;)if(op)(st=i

8、；t+;sort(t);t-S)void main()fmt i=0;/clock_t begin,flush;/ 计算时间函数/double ss; /计算时间函数/begiii=clock();/ 计算时间函数pnntf(”请输入工件个数(建议个数小于12否则需要耐心等待哟亲！)n”);scanf(”d”,&n);for(i=0;in;i-H-)fpnntf(”请输入A机器加工第:1工件的时间 W+1);fpnntf(”请输入B机器加工第:1工件的时间 W+1);for(i=0;in;i-H-)fs0=i；sort(l);/ finsh=clock();计算时间函数/ss=(fiiish-begiii)/cl;/ 计算时 Iuj 函数prin