工件安装与排序问题

《工件安装与排序问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、工件的安装与排序问题王晓楠，崔超，陈涛（中国矿业大学，徐州221008）摘要：本文首先深入分析了组合优化的特点，然后针对本题中设备对工件排血安装时的重量约束和体积约束的特点，就题目中提出几个问题分别设计了不同的算法，通过不同的算法的优劣的比较，不仅较好的解决了工件的排序安装问题，还得出了问题中算法设计的一些根据。在问题1中，我们引入了贪心策略和自适应方法对搜索算法进行改进，大大减小了搜索的规模得到了一种效率和性能都不错的搜索算法，另外还针对数据的特点给出了一种操作简便的简化算法，通过两种算法的比较得出了一些有用的算法设计结论。在问题1的算法设计过程中我们还适当的引

2、入了一些理论证明，使算法更加有说服力，最终通过MATLAB软件得出了令人满意的结果，有力的证明了算法的可行性。在问题2中将问题1的算法进行综合，然后分别从不同的出发点提出了两种算法，一种是适用性较强但不易实现的解析算法，另一种针对数据特点的较简便的针对性算法，并比较了两种算法各自的适应性，简便的求出了第二组数据的排序结果，并得出第一组数据无解的结论。问题3根据前面的结论，如果只考虑重量，分析了两种相临扇区总重量差最大的情况，通过数学分析得出工件调整幅度，如果还要考虑体积因素，通过对工件的贪心选择，不断修正工件重量和体积，筛选出满足条件的工件组合。我们在论文的最后还

3、给出了模型的评价和推广。一问题重述某设备由24个工件组成，安装时需要按工艺要求重新排序。Ⅰ．设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g）。Ⅱ．工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3）；Ⅲ．当工件确实不满足上述要求时，允许更换少量工件。问题1．按重量排序算法；问题2．按重量和体积排序算法；问题3．当工件不满足要求时，指出所更换工件及新工件的重量和体积值范围，并输出排序结果。请按

4、下面两组工件数据（重量单位：g，体积单位：），进行实时计算：序号重量体积序号重量体积1348101.51358.510323521022357.5103334710533551034349105.54351103.55347.51065355.510363471046357102733094734196832998834296.59329100.5934095.510327.598.51034497113299811342.595.112331.59912343.596.513348.5104.513357.5102.5143471051435510315346.

5、5107.515353.5103.516348104.516356.5103.517347.510417356103.518348104.518352.5104193339719342.59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.52434597二问题分析本题要求给出一种算法对24个工件按重量和体积的约束条件进行组合和排序，并安装到设备圆周的六个等分扇区上，每个扇区放置四个工件。相邻扇区的工件的重量之差不允许超过一定值，而相邻工件之间的体积差也要满

6、足不小于一定值的约束。表面上看似乎算法只要算法能给出一组排序满足要求即可，不需要进行最优化，但是通过深入分析可知，由于数据可能并不理想，满足要求的可行解的集合可能很大，但也可能很小甚至并不存在，因此要提高算法的适应性就必须对排序的结果进行目标优化，使结果尽可能满足要求，而不是简单的给出一组可行解，这样我们就可以通过最优或极优可行解来验证是否可以找到可行方案。因此问题可变为如下的优化问题：其中为一组排序方案，为所有可能排序的集合。由于每个位置上的工件只能从给定的24个工件中选，因此这是一种典型的组合优化问题。问题1只要求考虑重量约束下的排序，是单目标组合优化问题。我

7、们将目标函数定义为相邻扇区重量之差的最大值，寻找使该值最小的排序方案。目前对于组合优化问题的解决方案主要有两种策略，一是对搜索算法进行改进，以减少搜索的时间复杂度，如禁忌搜索算法；另一种是利用遗传算法、模拟退火算法等概率算法计算最优解。本问题所有可能的排序共有种，我们选择第一种方法，引入贪心策略通过搜索近似最优解以大降低搜索的复杂度，然后在保证算法结果不会恶化的前提下逐渐简化算法，提高算法的效率。问题2既要求满足重量约束又要求满足体积约束，是多目标优化问题，由于重量与体积之间相互并不一定有太大关联，因此若数据不理想而两者又要同时满足可能是非常困难的。我们的解决办法

8、从满足体积