带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序.     

加工时间依赖工件位置的链约束单机排序问题

讨论了工件加工时间依赖工件位置的链约束单机排序问题．对于链可中断和不可中断两种情形．证明了目标函数为最大完工时间和总完工时间时该问题仍然多项式时间可解．     

带运输时间和一个不可用约束的两台平行机排序

考虑了两台平行机的排序问题,其中一台机器带有一个固定的不可用约束区间,任务的加工是不可中断的,而且每一个任务带有一个运输时间,目标函数是最小化最大运输完工时间.这个问题是强NP-难的.提出一个最坏情况比是8/5的多项式时间近似算法,并指出这个界是紧界.同时还用动态规划方法求解该问题.     

极小化两种目标函数的具有学习效应的单机排序问题

本文研究具有学习效应和遗忘效应的间歇批生产的单机排序问题,目标函数分别为极小化最大完工时间和总完工时间．考虑了批与批之间没有学习效应的传递、批与批之间有部分学习效应的传递、批与批之间有总的学习效应的传递三种情形．我们分别对所考虑的问题给出了多项式时间算法并且证明了算法的最优性．     

具有准备时间的模糊交货期的排序问题

本文分析了一类具有准备时间的模糊交货期的单机排序问题.将任务具有不同准备时间,任务加工允许中断,目标函数是最大延误的排序问题由经典交货期推广到模糊交货期,并给出了最大模糊延误修正值的定义,给出了一些性质。在此基础上给出了此类问题的算法。为了便于计算,用三角形模糊数表示模糊交货期,本文用模糊交货期的隶属函数来比较任务的完工时间和交货期,判断任务是否误工。     

带有可控性维护的单机调度问题研究

为在附加费用不大的条件下,通过最小化工件完成时间之和来减小work-in-process中的库存,尽可能使工件按期交付,在将工件调度与机器维护统一进行考虑的模型基础上,提出了带有预防性维护的单机调度问题,并对其进行了建模.将机器的维护周期适当放宽,以便在保证总的附加费用不超出预先给定的一个常数的前提下,实现工件的完成时间和的最小化.对工件加工允许中断的情况给出时间复杂度为O(n*ln(n));对工件加工不允许中断的情况给出一个启发式算法,其时间复杂度为O(n2).由该启发式算法很容易得到问题的可行解,从而为问题的进一步研究打下了基础.     

加工时间具有学习效应的链约束单机排序问题

研究了工件的加工时间具有学习效应的链约束单机排序问题,在链可中断和不可中断两种情况下,均给出了目标函数为极小化最大完工时间的多项式算法。     

带有固定区间的双代理排序问题

【目的】研究带有固定区间的双代理排序问题。【方法】第一个代理的工件加工过程可以中断，考虑两种机器类型：单台机器时考虑的目标函数为总权误工损失或总权提前损失；两台平行机时考虑的目标函数为总完工时间，同时必须在规定的固定区间加工第二个代理的工件，目标是在满足第二个代理目标的可行性前提下寻找一个使第一个代理的目标函数值更小的排序方案。【结果】设计了单台机器固定区间工件损失问题的排序算法，也为两台平行机总完工时间问题设计了相应算法。【结论】设计的算法可在多项式时间内得到解决，且证明了算法的最优性，并用数值实验说明了算法的可行性。     

带有退化效应和不可用区间的并行批排序问题

在制造业中,处理机由于长时间使用而发生故障或进行维护、保养等原因,产生一些不可用区间;并且工件的实际加工时间往往与它的开始加工时间有关。研究一种带有退化效应和不可用区间的无界单机并行批处理机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数。而并行批处理机中,同批工件同时开始加工,同时完工,且批一旦开始加工就不可中断;每批的加工时间等于这批工件中加工时间的最大者;同批中工件的完工时间都相同,为这批的完工时间。讨论的目标函数为最大完工时间问题。通过对最优解性质的分析,给出了求解此问题的多项式时间的最优算法。     

具有窗口交货期的单机E/T调度问题

工件完成时间与交货期差的绝对值加权和最小化单机调度是典型的E／T(Earliness／Tardiness)的调度模型，是NP-hard问题．然而，当工件权值与加工时间成正比时，LPT(Largest Processing Time)工件调度最优．本讨论了上述问题具有窗口交货期且工件权值与加工时间成正比的情形，结果表明LPT工件调度仍然最优．     

提前/拖延调度问题最优解的结构

讨论了带有４项惩罚指标的提前／拖延调度问题,目的是确定最优公共７交货期和确定最优排序,给出了最优公共交货期的确定方法,提出联合处罚因子的概念,并讨论了最优解的结构。     

一种基于时间片的抢占控制模型

针对实时系统中任务调度问题,提出了一种基于时间片的抢占控制模型.该模型以抢占次数上限为特征参数,在满足任务集可调度的前提下,由该特征参数计算出任务时间片并按片内不可抢占的限制条件优化任务抢占次数.采用遗传算法对该抢占控制模型进行了离线实现,同时使用惩罚函数来保证整个任务集的可调度性.通过仿真实验,验证了该模型的有效性.     

禁忌搜索算法解决钢铁企业生产合同计划优化问题

针对钢铁工业中的实际合同计划问题建立了数学规划模型.模型在考虑了机组产能、工序优先级和库存等实际约束下,最小化合同的提前拖期惩罚费用、机组的产能放空费用、机组的库存费用和合同的产线选择费用.针对合同计划的复杂约束、大规模和多目标等特征,提出了新的禁忌搜索算法以求得问题的近优解.为了提高搜索效率,在禁忌搜索算法中引入希望邻域和每代多次移动的策略.通过中小规模随机产生的数据进行实验,结果表明,提出的算法获得的结果优于标准优化软件ILOG-CP得到的结果.通过大规模实际数据的实验,验证了算法的有效性.     

带启动时间的多重休假Geomx/G/1排队

研究了批量到达多重休假带启动时间的Geom^x｜G｜1排队。给出了系统稳态队长和等待时间的母函数及其它们的随机分解结果，并分析系统的忙期、全假期和在线期。     

MPLS网络中支持Diffserv流量工程的抢占算法

通过对MPLS网络中支持Diffserv流量工程的抢占策略的分析,基于抢占策略包括LSP的数目、LSP的优先级和抢占带宽三个主要抢占准则的思想,提出了一种优化的启发式算法。该算法基于回溯法的原理求解NP完全问题。仿真结果表明,与其它算法相比,该算法表现出更高的求解准确度,求解时间复杂度相当,适合实际的大规模网络的应用。此外,本文也考虑了在抢占策略下的路由方法。     

RM算法中减少抢占开销的任务微调算法

在基于嵌入式实时操作系统的实时应用中,由于任务抢占导致的切换开销对于整个系统是不可忽略的.提出了一种减少抢占发生的RM任务微调算法,通过对固定优先级调度抢占行为可推迟时间的量化分析,推导出受低优先级任务阻塞而造成的受阻任务集,以及在任意抢占时刻,推迟高优先级实时任务执行避免抢占发生的判定条件.仿真实验表明该算法在保证可调度任务集中所有任务满足时限约束的前提下,延迟高优先级任务的执行,减少抢占发生次数,通过减少抢占开销提高RM算法在实际应用中的可调度利用率.     

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.     

带启动时间的单重休假GeomX/G/1离散时间排队

对批量到达单重休假带启动时间的Geom^x／G／1排队进行了研究。给出系统稳态队长和等待时间的母函数及其它们的随机分解结果，并分析了系统的忙期、全假期、闲期和在线期。     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。