【摘 要】
：
排序(Scheduling)问题在运筹学和组合最优化中占有重要的地位.经典的平行机排序问题是NP-难的.它的一个实例是给定m台平行机,和n个工件,每个工件的加工时间事先给定.一次安排指的是把这n个工件放到m台机器上加工.每台机器上加工的所有工件的时间之和称为这台机器的负载,所有负载中的最大者称为一次安排的完工时间,它的目标是要求一个安排,使得完工时间尽可能地小.经典平行机排序问题的一个推广形式允许
论文部分内容阅读
排序(Scheduling)问题在运筹学和组合最优化中占有重要的地位.经典的平行机排序问题是NP-难的.它的一个实例是给定m台平行机,和n个工件,每个工件的加工时间事先给定.一次安排指的是把这n个工件放到m台机器上加工.每台机器上加工的所有工件的时间之和称为这台机器的负载,所有负载中的最大者称为一次安排的完工时间,它的目标是要求一个安排,使得完工时间尽可能地小.经典平行机排序问题的一个推广形式允许部分工件可以被拒绝掉,但拒绝了就会产生相应的惩罚费用.这个问题的一般形式是NP-难的.它的一个实例是给定m台平行机,和n个工件,每个工件的加工时间事先给定,如果拒绝该工件,则产生一个惩罚费用.它的目标是第一,把n个工件分成两个集合:接受加工的工件集合和拒绝加工的工件集合:第二,把接受加工的工件安排到m台机器上加工,使得完工时间加上拒绝加工的工件所产生的惩罚费用之和尽可能地小.本文探求这个NP-难问题在特殊条件下的算法设计和复杂性分析.我们讨论了每个工件的加工时间是2的幂次方且加工时间和惩罚费用之比满足简单的比例关系的情形,证明了在该情形下,问题是多项式时间可解的,并设计了多项式时间算法求解.我们的结论可自然地把每个工件的加工时间为2的幂次方推广到工件的加工时间满足整除关系,即任意两个工件的加工时间中,其中一个能整除另一个.我们也讨论了被接受工件的个数满足某些特殊条件的情形,在这些情形下,被接受工件的个数受到了某些限制,我们对此设计了近似算法求解该问题.
其他文献
对于离散事件系统,给定一个关于状态的秘密集合,若入侵者不能推断出系统的当前状态是否属于该秘密集合,那么认为系统具有不透明性。在以网络形式存在的信息物理系统中通常系统本身也会引入插入函数等方法来加强自身的不透明性,而这种加强不透明性的方式主要表现为对输出序列的再编码。再者,离散事件系统中也存在很多不可观测事件,这将导致入侵者可能不可以准确地推断出系统当前状态,站在入侵者立场,这样的问题显然需要及时解
随着互联网的迅速发展,情感分析已经成为自然语言处理的研究重点。语义提取和情感分类是解决这一问题的关键途径。面对不断变化的文本表达方式,现有算法的表现不令人满意。要想获得准确的情感分析结果,需要关注文本高层情感语义,需要提取文本多模态语义特征,需要提升情感分类的效果。论文重点研究了文本情感分析中的上述关键科学问题。论文主要工作和创新点如下:为了解决已有的语义提取算法提取结果不完善的问题,本文提出基于
随着深度学习和人工智能的不断发展,各行各业的相关应用也越来越多。目前,传统的监管工作逐步智能化,采用深度学习算法的巡检系统相继被开发出来,并能够对巡检人员和设备进行自动化监管。但是现有的系统往往存在以下不足。移动端由于自身运算和存储能力的限制,系统普遍运行在电脑端,电脑容易受到地点和使用场景的限制,使用起来不方便;OCR模型对巡检工作中仪表仪器图像进行文本检测时,容易将设备上的状态灯错误的检测成文
银联电子便民平台是一个缴纳水电煤等便民业务的在线平台,已于2009年上线。经过近5年运营,发现原有系统存在着用户体验不佳、代码冗余、可维护性不佳等问题,需要进行改造。本研究的主要工作是在充分分析用户需求及现有系统问题的基础上,对现有系统进行重构,增加新功能,以满足用户日益增加的应用需求。改造后的系统是一个基于J2EE的Web系统。该系统优化了原有系统的页面和缴费流程,增加了账单管理、每月一付、账单
青藏高原的形成、演化长期以来都是国际上地质学研究中的热点问题之一,青藏高原所在的地区在不同时期曾发生过一系列的构造运动,经历的地质事件也是多阶段的,包括特提斯阶段的三个阶段以及印度-亚欧大陆碰撞等,这些地质事件所带来的构造运动会使得强烈的岩浆活动出现在洋壳的俯冲以及印度与亚欧大陆碰撞的过程中。本文研究的地区处于班公错-怒江缝合带内,由于班怒带独特的构造格架使得其广泛分布有中生代的岩浆活动,这些岩浆
正态分布是统计分析中最常用的分布之一,通常假定响应变量具有对称性。但在经济金融、环境工程等实际领域中,响应变量不满足对称性的问题也很常见。为了研究这类问题,统计学者们提出了许多具有非对称性的统计模型,其中最典型的就是偏正态模型。传统的基于偏正态模型的回归分析大都只对均值参数建模。而在实际应用中存在大量的异方差数据,此时均值回归模型难以有效的拟合异方差数据,因此有必要继续对方差参数建模,即建立联合模
本论文研究了全新世中期(6000BP)以来三江源地区古生物群系类型的空间分布特点及分布演化模式。生物群系是生活在相似环境中的植物、动物等集群组成的集合,是描述生态环境的基本尺度,是地球生命的重要组成部分,其分布演变对生态学、地貌学、文明史的研究有重大意义。三江源地区位于青藏高原北部,是长江、黄河和澜沧江(即南亚湄公河)的源头,是我国的水源区、最大的自然保护区和第一个国家公园。研究三江源地区古生物群
商家希望通过促销吸引消费者,然而对于已经购买的顾客,降价促销可能带来不公平感,进而引发负面情绪和不利于商家的行为。探究有效降低已购顾客价格不公平感的促销方法,在信息发达的今天尤为重要。本研究从价格促销的不确定性出发,探讨确定促销与不确定促销对已购顾客价格不公平感影响的差异,并剖析其内在影响机制;在此基础上,探讨产品类型(物质性消费vs.体验性消费)对上述关系的调节作用;此外,还从消费者的个体特征(
随着风力发电系统使用规模的不断扩大,风电企业对风电设备的生产运营及设备管控提出了更高的要求,为了提高风力发电系统故障诊断的快捷性和可靠性,结合数据驱动技术和深度学习算法,对复杂的非线性故障诊断问题有了新的解决方法,在保障维保和技术人员人身安全、减少甚至避免不必要的经济损失中具有重要意义。深度学习本质上是通过输入信号进行处理和加工并作输出的一种机制,随着近年来大数据和云计算相关技术的发展,运用大幅度
在大数据时代,数据影响着人类社会的方方面面;不仅影响人的生活方式、工作方式,也影响着人的思维方式。人们的各种社会现象和社会行为都可以被“数据化”,这些现象及行为通过数据化后再依托数据技术被采集、存储、分析和利用,能够超越传统的信息获取和解读方式的局限,可以助力包括教育在内的众多领域精准地解读需求、把握动态、提供服务、预测发展。班级作为学校的基层组织、教学的基本单位,学生学习共同体,对学生个体社会化