【摘 要】
：
开发高效、精确的排序算法是组合优化中的一个重要课题.通过确定排序策略,可以在有限的资源和各种约束条件下,优化所选择的性能指标,从而提高潜在的经济效益.本文考虑的是带有起始时间和截止时间的在平行机环境中的排序问题,确定加工策略使得所需机器数最少,主要从算法和复杂性两方面研究了具有与序列相关的调整时间的区间排序问题.首先研究了固定工件排序问题,提出解决此问题的O(n2)列表排序算法并给出改进算法(O(
论文部分内容阅读
开发高效、精确的排序算法是组合优化中的一个重要课题.通过确定排序策略,可以在有限的资源和各种约束条件下,优化所选择的性能指标,从而提高潜在的经济效益.本文考虑的是带有起始时间和截止时间的在平行机环境中的排序问题,确定加工策略使得所需机器数最少,主要从算法和复杂性两方面研究了具有与序列相关的调整时间的区间排序问题.首先研究了固定工件排序问题,提出解决此问题的O(n~2)列表排序算法并给出改进算法(O(n log n)).结合实际生活中的人员调度问题,引入了与工件序列有关的调整时间的约束条件,分析并得到该问题与固定区间问题的联系,设计多项式时间的迭代算法解决有调整时间的工件排序问题.通过构造对应具有可传递边的工件网络把排序问题转化为网络优化问题,结合匹配,路径覆盖等知识论证算法正确性.最后,研究了调整时间不满足三角不等式约束下的排序问题,将排序问题转化到特定的图与网络中,结合解决匹配问题和网络流问题的多项式时间算法,提出了解决该问题的有效方法,进一步将最小流方法推广以解决多类别工件排序的推广问题.
其他文献
微宇宙作为一种人工控制的模拟生态系统,已广泛应用于农药生态风险评估,而多介质逸度模型也已逐渐成为研究农药环境行为和归趋的重要手段。本文通过构建室内水生微宇宙模拟和
随着中国经济步入“新常态”,我国建筑业的发展也面临新的挑战。一方面,建筑业的市场风险增多、发展速度逐渐放缓、竞争日趋激烈;另一方面,目前建筑业的项目也越来越紧俏,出现僧多粥少的严峻局面,各大建筑企业都出现了回款难与盈利难的问题,而中小民营建筑企业由于本身资金少,规模小,企业发展前景不明朗,加之知名度不高、地域性强等一系列原因致使中小民营建筑企业的人才,特别是技术人才不断的流失,严重地影响到了企业的
课程是落实教育目标的重要路径,学校教育的实践活动大部分都是围绕课程进行,课程改革作为教育改革的重要方面,最终是否达到预期效果,还是要依赖于相应的课堂教学是否发生了积极变化。思想政治课堂教学是落实课程改革目标的重要途径,教师作为思想政治课堂教学的主导者和直接执行者,他们能否将课程改革目标落实到具体的课堂教学,是有效实现思想政治课程改革目标的关键。鉴于思想政治课教师课程执行力的重要地位,首先,从思想政
近些年来,全球“黑天鹅”事件频频发生,地区热点问题跌宕彼伏,错综复杂的国际形势正使得各国面临着前所未有的高度不确定性。同时,伴随着世界多极化、经济全球化的深入发展,国家间的经济依存日益加强,关联方式不断增多。在此背景下,经济政策不确定性的跨国溢出成为世界各国学者共同关注的话题,关于该问题的深入研究对如何科学、有效地防范外部冲击具有重要的理论价值和现实意义。本文从理论与实证两方面来考察全球经济政策不
模型降阶是一类处理工程领域中高阶或复杂系统的有效近似方法,其目的在于寻找一个低阶系统来近似原始的复杂高阶系统,且使得该低阶系统能保持原始高阶系统的一些重要性质.在计算机辅助工程的相关过程中用低阶系统代替原始系统,可以降低系统的分析难度,减少运算量,提高仿真模拟效率.当前,模型降阶方法已被广泛应用于控制系统,通讯系统及电路系统等工程领域.本文首先研究了离散线性周期时变系统基于交叉Gram矩阵的奇异值
党的十九大报告提出必须树立和践行绿水青山就是金山银山理念。福建省南平市山清水秀、生态优越,以绿水青山享誉海内外。近年来南平市着力于打造“武夷山水”农产品区域公用品牌,培育一批本地拥有不错发展潜力的企业,让绿水青山中蕴含的经济效益更快转化为实体经济。如何更好发挥政府作用推进“武夷山水”农产品区域公用品牌建设成为亟待研究的问题。本文从政府作用的角度来研究“武夷山水”农产品区域公用品牌的建设,在地方政府
本文基于北京不同气象站地面观测总辐射、直接辐射、风速、风向、相对湿度、气压、气温以及本站或邻近环境监测站点的PM10、PM2.5浓度、AOD（Aerosol Optical Depth）实测数据分
随着我国的经济建设的高速发展,基础建设与资源开采的规模不断扩大,随之也面临着大量的工程地质问题。尤其是在各类矿山的开采过程中,往往会形成大规模、工程地质条件复杂的高边坡,这些高边坡由各种不同类型的结构面切割组合形成各种不稳定块体,往往也正是由组成高边坡的这类块体决定了矿山边坡的稳定性。块体是由结构面与完整岩石组合而成的复杂综合体。边坡内的各种块体的稳定性主要是其内部岩石以及组成块体的各类结构面强度
本论文通过理论计算研究了铝钠团簇的几何结构、稳定性和电子性质,首先采用遗传算法结合MOPAC程序对AlnNam（n=5,6;n+m≤10）团簇的能量最低结构进行全局搜索。使用密度泛函理论