带不可用时间段限制的不允许等待柔性流水排序问题

来源 :兰州大学 | 被引量 : 0次 | 上传用户:bright_123456789
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文给出了极小化时间表长带这种称为机器不可用时间限制的不允许等待柔性流水车间排序问题的模型。作为研究求解该类问题算法的基础,本文首先指出,即使是最简单的仅有一个不可用时间段的柔性流水车间排序问题也是强NP-困难的。进一步,本文分析了该类问题的可逼近性。分析的结果表明,在柔性流水车间某个加工中心的所有机器上都附加不可用时间约束后,除非P=NP,几乎所有情况下都不存在具有有限最坏比的多项式时间算法(优化问题的这种性质在部分文献中称为APX-困难性)。鉴于该问题的这种APX-困难性,本文给出一个基于分支定界法的启发式算法。
其他文献
  图像边缘检测是图像处理与分析中基础内容之一。边缘检测作为机器视觉的一个早期阶段,有很长的研究历史,但至今为止还没有得到圆满解决。比较经典的Canny、Sobel等算子,一直
平均函数是平均数理论中的一个重要的研究课题,文[1][2][3]对平均函数进行了公理化处理,建立了平均族理论.本文是在[1][2][3]的基础上,进一步地探讨了高维多参数可数平均族的
本文首先在原来的F-展式法的基础上进行扩展,思想上利用Jacobi函数之间的关系,在解的形式中加入另一个Jacobi函数G,来求解非线性偏微分方程Hamiltonian振幅方程、(2+1)维的MKdV
本文首先考虑了非线性Schrodinger方程 -△u=V(x)u+f(u), u∈H1(RN) (1)的非平凡解的存在性. 利用上述问题的极限问题的一些结果,结合Lions的集中紧性原理,讨论了
随着科学技术的发展,越来越多的学者意识到了地理位置的空间差异对空间事物的影响。为揭示空间事物之间的空间关系而发展起来的空间统计分析,已成为当前研究的热门课题。空间
世博结束后,世博园区的环卫服务标准已成为中国环境服务业的经典样板。10米为半径的圆形范围内20分钟只能出现3个点状物、硬隔离带采取分流 After the Expo, the sanitation
本文对F-展开式法进行修改推广,解非线性偏微分方程,得出新解.首先对含有常数项c的F-展开式进行了讨论,在某些情况下,c可以取任意常数,获得了mKdV方程,KdV方程的一些新的解.
数学是小学教育中不可缺少的必修课,如何调动小学生学习数学的积极性呢?罗杰斯说过:“学习本身包括认识和情感两个方面。”实践表明:强烈的学习兴趣来自情感的动力。只有当学
  本文介绍了我们考虑Hénon方程{-△u=|x|αup-1,x∈Ω,u>0,x∈Ω,u=0,x∈()ΩΩ是RN中的单位球,α>0是一个常数,指数p是超线性且次临界的,即{2<p<2*=+∞,N=2,2<p<2*=2N/N-2,N>3.前人
  希尔伯特空间的框理论在信号、图象处理以及数据压缩和抽样理论研究等方面有着十分重要的作用。Gabor框作为一类重要的框,在光学、信号探测、噪音去除、量子理论领域有着