零件加工时间最优化的动态规划模型.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<stdio.h>
#include<stdlib.h>
#include <time.h>
#define cl ((clock_t)1)//计算时间函数
#define M 23
int n,t=0,s[M],re[M];
double a[M],b[M],tm=111111111,tn=0.0,wt=0.0;
double max(double x,double y)
{
if(x>y)
return x;
else
return y;
}
double sum1(int x,int y)
{
double all=0.0;
int i=0;
for(i=x;i<=y;i++)
all+=a[i];
return all;
}
double sum2(int x,int y)
{
double all=0.0;
int i=0;
for(i=x;i<=y;i++)
all+=b[i];
return all;
}
void time(int *p)
{
int j=0,k=1,i=0;
wt=0.0;
if(a[p[1]]>b[p[0]])
wt+=a[p[1]]-b[p[0]];
for(i=0;i<n;i++)
while(i>1)
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;
}
else
{
k++;
break;
}

for(i=0;i<n;i++)
wt+=b[p[i]];
wt+=a[p[0]];
tn=wt;
if (tm>tn)
{
tm=tn;
for(i=0;i<n;i++)
re[i]=p[i]+1;
}
}
void sort(int t)
{
int i=0,op=0,j;
if(t==n)
time(s);
else
{
for(i=0;i<n;i++)
{
op=1;
for(j=0;j<t;j++)
if(s[j]==i)
{
op=0;
break;
}
if(op)
{
s[t]=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;i<n;i++)
{
printf("请输入A机器加工第%d工件的时间 \n",i+1);
scanf("%lf",&a[i]);
}
for(i=0;i<n;i++)
{
printf("请输入B机器加工第%d工件的时间 \n",i+1);
scanf("%lf",&b[i]);
}
for(i=0;i<n;i++)
{
s[0]=i;
sort(1);
}
// finsh=clock();//计算时间函数
// ss=(finsh-begin)/cl;//计算时间函数
printf("最小时间为 %g\n",tm);
// printf("所耗时间为 %f ms\n",ss);//计算时间函数
printf("加工工件顺序为\n");
for(i=0;i<n;i++)
printf("（%d） %d号工件\n",i+1,re[i]);
system("pause");
}

5