【摘 要】
：
这篇论文主要研究单机加权分批运送排序问题(Scheduling with Weighted Batch Delivery,简记为SWBD),并把一些结果推广至平行机加权分批运送排序问题.在SWBD中,一组独立的工
论文部分内容阅读
这篇论文主要研究单机加权分批运送排序问题(Scheduling with Weighted Batch Delivery,简记为SWBD),并把一些结果推广至平行机加权分批运送排序问题.在SWBD中,一组独立的工件均在零时刻到达,每个工件有相应的加工时间和权重,且加工不允许中断,当所在批中最后一个工件完工后一起运走.问如何把这些工件安排在一台机器上加工,并适当地分批运送,使得总费用最小?这里,总费用包括两部分:一部分是运送费用,为分批数的非减函数,设为分批数的常数倍;另一部分是由于不及时运送而导致的附加费用,是工件运走时间总权和的非减函数,设为工件运走时间总权和.该文证明了SWBD是NP困难的,并用动态规划方法给出了一个算法,当分批数有固定上界时,即r≤U时,该算法为拟多项式的.并将该算法推广至平行机加权分批运送排序问题.我们给出一个复杂度为O(n<3>)的近似算法,数值检验说明该算法效果较好.我们引进了最优顺序的概念,并在此基础上证明了目标函数关于分批数的凸性.作为SWBD的一种可解情形,当最优顺序已知时,我们给出一个多项式时间算法.该文的最后给出一个优化模型,把SWBD与广义指派问题联系起来.
其他文献
《现代汉语词典》对“检查”一词的解释是:“为了发现问题而用心查看”。检查的目的是了解情况、发现问题、纠正偏差、督促完善,为决策提供依据。然而,一些领导和部门在检查
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
该文分别研究了单位球面S和复射影空间CP中的几类极小子流形的特征,全文共分三部分.第一部分介绍了子流形的一些基本概念和重要记号,并给出了该文的主要结论.第二部分在陈省
该文从网络安全的现状出发,探讨了目前网络安全的主要威胁和采用的相应措施,以及不 措施费用开销,同时归纳出针对解决这些安全威胁和节省费用开销的安全措施最常用技术—VPN
该文研究一个描述肿瘤生长的自由边界问题.这个自由边界问题是对Byrne和Chaplain相应肿瘤生长模型的一个改进和推广.我们先研究了在C=C=0的情况下该问题的解的存在性和解t→
该文主要对一般半群上的主同余及一些相关课题如稠密子集与析取子集(语言)进行研究.第一章给出了文中所需的一些预备知识.第二章主要研究稠密子集的一般理论,在给出了稠密子
空间聚类是空间数据挖掘中的一个重要研究领域,对于应用于大型空间数据库中的聚类算法一般有以下要求:最少的输入参数个数,能够发现任意形状的聚类,在大型数据库上效率好.从
几年的英语教学之路走来,我越发觉得对于相当大的一部分学生来说,学习英语最难不是难在语法上,而是认识记忆单词上.作为新形式下的英语教师,我们要重视学生在学习英语初始阶
该文主要讨论有关Teichmuller空间和调和映射理论的若干问题.论文共分四章,第一章是论文的引言.我们将综合介绍拟共形映射与Teichmuller空间理论,调和映射理论及它们的最新发
中国历史上曾经出现过的政府信息公开例外规则虽然与当今的政府信息公开规则有着不同的理念,但是仍与今天的制度一脉相承。梳理历史上的例外规则,便于了解当时社会精神文化层