工件排序的均匀差值和检验标号算法

《工件排序的均匀差值和检验标号算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、工件排序的均匀差值和检验标号算法邓鑫，侯志白，张子阳（徐州空军学院，徐州221000）摘要：本文以目标规划基本理论为基础，借鉴整数规划中的0-1规划的特征，实现了工件摆放位置与工件重量，体积的联系，建立重量排序模型，以及重量与体积双重目标下的排序模型，运用lingo进行求解。但作者不局限于lingo求出的可行解，而是大胆创新，针对题目数据的特点，提出依据大小顺序每6个工件分段的思想，首先采用均匀差值算法找到了重量排序的满意解；其次，在满意解的基础上，运用检验标号，不仅满足了体积要求，而且直观明了，当

2、工件不满足要求时，能够具体找出需要更换的工件所处的位置以及重量和体积值的范围。填补了lingo只能求解不能反映临界状态，不能进行灵敏度分析的空白一.问题的重述某设备由24个工件组成，安装时需要按工艺要求重新排序。Ⅰ．设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g）。Ⅱ．工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3）；Ⅲ．

3、当工件确实不满足上述要求时，允许更换少量工件。问题1．按重量排序算法；问题2．按重量和体积排序算法；问题3．当工件不满足要求时，指出所更换工件及新工件的重量和体积值范围，并输出排序结果。二．问题的分析工件安装时，按工艺要求重新排序，排序要满足重量要求，如果各区域之间的重量差M越小，运行就越稳定，寿命就越长；还要符合体积要求,假如相邻工件的体积差Q越大，那么在安装时区分度就越大，结构简单，安装方便。综合考虑这两个指标时。同时处理两个目标比较困难，而且如果去求多个目标的最优解还会导致一些相互矛盾的结果，

4、，那么运用目标规划的理论，根据实际情况去确定模型，采用实际数据去求解，将重量要求设为高级目标，体积要求设为低级目标，借鉴分层序列法，在高级目标达到满意解的基础上，求低级目标的满意解。这种方法突出强调了高级目标的重要性，当高级目标要求较高时，造成满意解的数目较少，此时再去求低级目标的满意解，可能会导致无解。三．基本假设1.各个工件之间体积之差并非全部超过一定值Q；2.将圆盘划分为24个位置，每个工件对应圆盘上的一个位置，则相邻的4个位置划分为一个扇形区域；3.圆盘有一定的强度，不会因为重量过分集中于一

5、个区域导致轴等部件损坏，使得排序无法进行；4.圆盘上的工件排序以顺时针为标准进行排序。四．符号说明每个扇形区域的4个工件总重量与相邻的4个工件总重量之差不允许超过的一定值；相邻工件体积差不小于的一定值；　表示圆盘等分成的区域，；　表示第i个工件的重量；　表示第i个工件的体积；表示第i个位置工件的重量，J为该工件的序号；表示第i个位置工件的体积；表示；表示第i个位置的工件；表示第i个工件被安排在圆盘的第j个位置，0或1；满足相邻区域总重量和的差值不超过一定值M的满意解的集合；表示正偏差变量，；表示负的

6、偏差变量，；表示优先因子，规定远大于。五．模型的建立与求解5.1问题一重量排序算法5.1.1问题分析设备的24个工件均匀分布在等分成6个扇形区域的一个圆盘的边缘，所以可以将圆盘划分为24个位置，每个工件对应圆盘上的一个位置，就表示第i个工件被放在第j个位置，而相邻的4个位置就构成了一个扇形区域。那么以6个扇形区域为列，24个工件的重量为24行，组成了一个24*6的矩阵：因为在这个扇形区域中的4个工件的总重量与相邻区域中的4个工件的总重量不允许超过一定值M，所以问题Ⅰ的模型为：(1)运用Lingo软件

7、可以对模型1进行求解，得到的是一个可行解的集合R(M)，当M的取值越大时，集合R(M)中的可行解的数目就越多，相反则越少。5.1.2算法讨论1．问题用Lingo求解模型时，当一定值M较大时，虽然可行解较多，但许多可行解处于临界状态，以这样的解为基础无法实现相邻工件体积差不小于一定值Q的要求，而当一定值M较小时，求解模型所需要的时间很长，如果增加工件数目，模型将无法用Lingo求解。2．思路显然各区域中工件的总重量越接近一个平均值，相邻区域之间的总重量和的差就会越小，如果这个差小于一定值M，那么这样的

8、一个均匀分组构成的排序就成为一个可行解。3．算法实现STEP1将24个工件从小到大进行排序；STEP2以重量从轻到重的的顺序，每6个工件分一段，分成四段，每段中的工件的重量值在一个区间内，后一段的区间内的值大于前一段的区间内的值；STEP3将最后一段中的6个工件放入6个区域内，以第4个区域中的工件重量值为中位数，求出其它区域中的工件的重量值与中位数的差值；STEP4将前一段中的最轻的工件放入差值最大的区域中，将重量次轻的工件放入差值其次大的区域中。依此原则，将该段中6