文档介绍：零件加工时间最优的动态规划模型
摘要
零件加工最有时间问题是典型的动态规划问题。建立一个动态规划模型,按照这类问题的基本思路,抓住等待时间这一关键要素,运用计算机模拟求解(我们用C写了一个程序(见附录),可以模拟零件个数12以内的所有情况,得出最优时间和零件编号的顺序。程序已做成文件,与论文的电子稿一起放在ftp上)。
关键词:动态规划;机床零件;时间最优;
1问题的重述
例题3(工件排序问题)
某修理车间因修理工作需要生产个不同的工件,每个工件都需要先在机床,后在机床上进行加工。不妨用编号分别代表不同的工件,以、表示工件需在,机床上加工的时间。如果该车间只有一台机床,一台机床,且、不受加工工件顺序的影响,问如何安排零件在,机床上的加工顺序,才能使机床加工总时间(从机床开始加工,至两机床均将工件加工完为止)最短?
约定符号和名词解释
:为第阶段选择的零件需要的等待时间。
:为零件通过机床的顺序编号的集合;
:为顺序集合中第个元素,即为第阶段选择的零件的编号。
问题的分析
对于零件加工求解时间最优的问题,是典型的动态规划问题。根据题目,首先将问题划分个阶段,每个阶段选择一个零件,将零件的编号计入数组,通过计算等待时间的最小值,来确定选择的零件顺序。
根据题目可知,零件一定要先经过机床,才能通过机床,那么机床应该是不停工作的;而机床前一个零件的加工时间长短,直接影响机床目前零件能否立刻加工,若机床前一个零件加工时间过长,就必须停下来等待,才而产生现等待时间。本问题正是要抓住等待时间这一变化量,列出递推公式,用计算机模拟求得结果。
模型的假设
根据题目,提出以下几个假设:
(1)假设加工零件在同一条流水生产线上,即零件通过A机床的顺序与通过B机床的顺序一致。
问题模型的建立
既然是典型的动态规划问题,就可以用通用的解题思想和步骤进行求解,即将多阶段决策过程最优化问题划分阶段, 恰当地选取状态变量、决策变量及定义最优指标函数。
根据题目,共有个零件,那么就将整个过程分为个阶段,每次阶段选择一个零件,把每次选择的零件编号存入一个数组中,用这个数组来记录零件通过机床的顺序;将等待时间作为状态变量,而把零件加工的总时间作为指标函数。最终问题就是解最小的零件加工时间。
首先,设每个零件的等待时间为,不需要等待的零件“0”。根据题目,零件一定要先经过机床,才能通过机床,那么机床应该是不停工作的,而机床会由于机床前一个零件加工时间过长而出现等待时间。如图所示
列出等待时间的函数:
第一个零件不需要等待,时间是
,
从第二个零件起,等待时间:
()
根据上图,加工所有零件所需要的总时间是第一个零件的机床时间、所有零件的机床加工时间、所有等待时间三者之和,为:
, ()
根据穷举法,通过C语言编程(程序见附录),可解得最终数据。
模型的评价和推广
零件加工时间最优问题,是最简单最常用的动态规划问题。本问题中的模型就是针对这类问题建立的,
模型的优点:能准确的计算住零件加工的顺序,和所需的时间。
模型的缺点:模型的时间复杂度是,当零件个数较多时(从超过9个开始),模型运算所需的时间飙升,对零件个数较大的情况,这个模型无能为力。
参考文献
[1