自由作业问题的一种启发式算法及最坏性能比分析

来源 :湖北民族学院学报：自然科学版 | 被引量 : 0次 | 上传用户：just_username

【摘要】

：

研究具有准备时间的自由作业问题,给出一种简单的启发式算法,证明在此启发式算法下,最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的.从而证明了对该问题的猜想:即在贪婪

【作者】

：

时凌

【机构】

：

湖北民族学院理学院

【出处】

：

湖北民族学院学报：自然科学版

【发表日期】

：

2002年4期

【关键词】

：

自由作业问题准备时间最坯性能比分析启发式算法 open-shop problem release times the worst-case analysi

【基金项目】

：

湖北省教育厅指导性项目

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

研究具有准备时间的自由作业问题,给出一种简单的启发式算法,证明在此启发式算法下,最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的.从而证明了对该问题的猜想:即在贪婪算法的情况下其最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的.特别当m=2时,具有准备时间的自由作业问题,利用该启发式算法得到的最坏性能比是3/2,其上界也是紧的.

其他文献

由“3^2＋4^2=5^2”衍生出的猜想

勾股三角形中最有代表性的是商高揭示的一组勾股数,由等式"32+42=52"产生联想,可衍生出"x2+y2=z2;3x+4y=5z ;ax+by=cz(其中a2+b2=c2)"等不定方程,考虑有无整数解产生一些猜想

期刊

勾股数猜想不定方程整数解初等数论勾股三角形常量变量pythagorean numbersconjectureinfinitive equatio

于田—和田绿洲沉积物的初步研究

<正> 根据对塔里木盆地南缘于田——和田绿洲沉积物调查,14C年代测定及粒度和化学元素等分析结果,本文认为:于田——和田绿洲沉积物主体主要是由3.32～6.64φ的风成沙尘物质即

期刊

于田-和田绿洲沉积物碳年代测定粒度成土作用

华南古大陆边缘湘北九溪下奥陶统碳酸盐等深岩丘

湘北桃源九溪碳酸盐等深岩丘发育于早奥陶世华南古大陆边缘湘北深水区。该区早奥世层系厚逾350m;其中极为发育的等深岩可分为灰泥等深岩、砂屑等深岩、粉屑等深岩、细砾屑等

期刊

等深岩碳酸盐岩早奥陶世岩丘

“Python程序设计”课程教学改革与实践

本文针对商科类本科院校针对零计算机程序设计基础学生的"Python程序设计"课程教学现状,分析了学情和教学中存在的问题,引入项目案例,提出以成果导向为指导、以能力培养为核

期刊

Python程序设计成果导向教学设计能力培养

广东系昌铅锌矿床中闪锌矿的谱的学特征与形成条件^＊

期刊

铅锌金属矿闪锌矿谱学铅锌矿

基于FPGA的LCD1602液晶显示屏系统控制设计

本研究基于FPGA实现驱动LCD1602液晶显示屏显示数字或者英文字符,设计中使用了Verilog硬件描述语言、Quartus II 6.0软件编程调试环境和DE2硬件环境,以完成对LCD1602液晶显示

期刊

Verilog语言LCD显示FPGA设计

商业银行“授信集中”风险形成机理的定量分析

该文从商业银行分支机构行为的角度对授信集中风险形成机理进行了研究,揭示其产生的内在原因,指出在商业银行分支机构面临规模指标考核及市场竞争的双重压力下,必然产生对大

期刊

商业银行授信风险

岩溶灾害对民用建筑和工业建筑影响的评价

<正> 欧洲部分覆盖着发育良好的硫酸盐和碳酸盐岩溶,主要赋存于沉积覆盖较薄的河谷之中。这种条件有利于岩溶崩塌的发育。岩溶崩塌是民用建筑和工业建筑的主要威胁。岩溶岩石

期刊

岩溶灾害民用建筑工业建筑溶洞概率法

“信号处理仿真实验”课程教学的改革与实践

“信号处理仿真实验”是一门综合性实验课程.本文介绍了该课程在教学改革与实践方面的一些特色,包括贯通式教学、开放式教学和案例式教学.尤其是“科研成果进课堂”这项工程

期刊

信号处理仿真案例式教学MATLABDSP

寓学于研教学模式在"网络空间安全"课程中的应用探索

在网络空间安全教学中,"网络空间安全"课程建设是本科生培养的重点,网络安全创新实践是学生科研之路的重要基石,两者相辅相成,缺一不可,均扮演着重要的角色。针对当前"网络空

期刊

寓学于研课程教学创新实践网络空间安全

自由作业问题的一种启发式算法及最坏性能比分析

与本文相关的学术论文