考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证...考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过54+12k,其中k是算法中预先给定的迭代次数.已有的算法仅为32.展开更多
高精度气动优化是改善高超声速飞行器气动性能的必要途径。基于Navier-Stokes方程推导了连续伴随方程以及与气动力目标函数对应的边界条件和壁面灵敏度公式,考虑了层流输运系数变分对伴随方程的贡献,采用基于二阶熵修正Roe格式的伴随对...高精度气动优化是改善高超声速飞行器气动性能的必要途径。基于Navier-Stokes方程推导了连续伴随方程以及与气动力目标函数对应的边界条件和壁面灵敏度公式,考虑了层流输运系数变分对伴随方程的贡献,采用基于二阶熵修正Roe格式的伴随对流项离散形式,构造了适用于高超声速流动的连续伴随求解器;结合FFD(Free Form Deformation)参数化方法和SQP(Sequential Quadratic Programming)优化算法构建了高精度梯度优化框架;在高超声速来流条件下对二维翼型和Sanger飞行器机翼优化开展了验证和应用。结果显示,在高超声速流动条件下所采用的伴随对流项离散形式具有较好的鲁棒性和低耗散性;连续伴随求解器能够较好地给出气动力目标函数梯度;优化后Sanger机翼构型通过二次激波压缩实现了减阻增升,升阻比提高5.0%;验证了连续伴随优化作为高超声速飞行器高精度气动优化方法的可行性。展开更多
多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的...多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的尺寸可变装箱问题的定义。除了经典装箱问题中物品体积这一参数,还引入了物品类型、箱子类型等参数,建立了数学模型,将经典的FFD(First Fit Decreasing)算法进行了推广,提出了新的算法MFFD,并分析了相关的算法复杂性。最后对FF、FFD以及MFFD算法进行了模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,MFFD算法效果较好。展开更多
作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引...作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引入了物品类型和箱子脆度等参数,给出了相关的数学模型。在经典的FFD(First Fit Decreasing)算法的基础上进行了推广,提出了新的启发式算法NFFD,它对箱子的特性进行了预处理,再进行装箱。分析了该算法的复杂性。对NFD、FFD和NFFD算法进行了数值模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,NFFD算法的效果是最好的。展开更多
The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins ...The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins into which L can be packed, and let FFD(L)denote the number of bins used by FFD. Johnson showed that for every list L, FFD(L)≤11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker gave a much shorterand simpler proof for FFD(L)≤11/9OPT(L)+3. His proof required 22 pages. In this paper,we give a proof for FFD(L)≤11/9 OPT(L)+1. The proof is much simpler than the previousones.展开更多
THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the...THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing （FFD） algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.展开更多
文摘考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过54+12k,其中k是算法中预先给定的迭代次数.已有的算法仅为32.
文摘高精度气动优化是改善高超声速飞行器气动性能的必要途径。基于Navier-Stokes方程推导了连续伴随方程以及与气动力目标函数对应的边界条件和壁面灵敏度公式,考虑了层流输运系数变分对伴随方程的贡献,采用基于二阶熵修正Roe格式的伴随对流项离散形式,构造了适用于高超声速流动的连续伴随求解器;结合FFD(Free Form Deformation)参数化方法和SQP(Sequential Quadratic Programming)优化算法构建了高精度梯度优化框架;在高超声速来流条件下对二维翼型和Sanger飞行器机翼优化开展了验证和应用。结果显示,在高超声速流动条件下所采用的伴随对流项离散形式具有较好的鲁棒性和低耗散性;连续伴随求解器能够较好地给出气动力目标函数梯度;优化后Sanger机翼构型通过二次激波压缩实现了减阻增升,升阻比提高5.0%;验证了连续伴随优化作为高超声速飞行器高精度气动优化方法的可行性。
文摘多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的尺寸可变装箱问题的定义。除了经典装箱问题中物品体积这一参数,还引入了物品类型、箱子类型等参数,建立了数学模型,将经典的FFD(First Fit Decreasing)算法进行了推广,提出了新的算法MFFD,并分析了相关的算法复杂性。最后对FF、FFD以及MFFD算法进行了模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,MFFD算法效果较好。
文摘作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引入了物品类型和箱子脆度等参数,给出了相关的数学模型。在经典的FFD(First Fit Decreasing)算法的基础上进行了推广,提出了新的启发式算法NFFD,它对箱子的特性进行了预处理,再进行装箱。分析了该算法的复杂性。对NFD、FFD和NFFD算法进行了数值模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,NFFD算法的效果是最好的。
文摘The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins into which L can be packed, and let FFD(L)denote the number of bins used by FFD. Johnson showed that for every list L, FFD(L)≤11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker gave a much shorterand simpler proof for FFD(L)≤11/9OPT(L)+3. His proof required 22 pages. In this paper,we give a proof for FFD(L)≤11/9 OPT(L)+1. The proof is much simpler than the previousones.
文摘THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing （FFD） algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.
