工件有尺寸的单机批调度问题的在线算法

16160的在线算法,并给出了此问题的一个下界。     

三台平行同型机的一个半在线排序算法

本文研究三台平行同型机的一个半在线排序算法，我们假设工作的最大加工时间预先知道，我们将给出一个竞争比为（1＋√73)/6≈1.5907的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是√2.     

一种解决有限缓冲区流水车间调度问题的复合启发式算法

针对以最大完工时间为目标的有限缓冲区流水车间调度问题,提出了一种新的复合启发式算法.算法设计中首先使用PF-NEH算法进行解空间的搜索,并采用基于插入邻域和交换邻域的可变邻域搜索算法来增强局部搜索.仿真实验表明,该算法具有高效性和优越性.     

带准备时间的两台同类机半在线排序

针对机器速度和准备时间不同,探讨了带机器准备时间的两台同类机半在线排序问题,以达到优化工作效率的目的.目标为极小化最大机器完工时间,对于所有工件中最大工件的加工时间已知的这种半在线情形,给出了一个竞争比不少于(s+1)/(2s+1)的MIN半在线算法.     

实时需求下的带时间窗移动充电车在线调度算法

在双碳背景下,移动充电车作为新型充电设施,能够缓解电动车保有量迅速增长带来的充电压力。然而成本高、效益低等问题阻碍了移动充电车的进一步发展。本文针对移动充电车只有在用户发出充电请求时,才能获知充电需求信息的特点,且需求带有时间窗要求的情形,提出实时需求下的带时间窗移动充电车调度问题,以总时间成本最小为目标,采用在线理论与方法,建立优化模型并设计在线算法;给出了不同情形下的调度方案,计算方案的竞争比,并进行对比分析;最后通过数值算例验证了在线算法的可行性和有效性。研究结果表明,用户发出的实时充电需求数量越大、最大单位惩罚时间成本系数越小,在线算法的执行效果越好。本文的模型和在线调度算法可以有效解决实时需求下的带时间窗移动充电车调度优化问题,提高移动充电车的充电效率,平衡充电供需。     

两台带准备时间的同类机的半在线排序

研究了带机器准备时间的两台同类机的半在线排序问题,这里目标函数为极小化最大机器完工时间.对于所有工件总的加工时间已知的半在线情形,我们给出了一个竞争比为max{52 1,1 bb}的半在线算法,其中b为机器速度.并且算法对于对于机器加工速度b<2时的同型机情形是最好的.     

复合两信息的同类机半在线排序问题

研究了两台同类机的一个半在线排序问题，当预先知道所有工件的加工时间总和（sum）与最大工件的加工时间（max）及目标为极大化最小机器完工时间的情形时，证明了此问题的竞争比为（3s＋2）／（2s＋2）的半在线算法．     

预先知道工件最大加工时间的带机器费用的排序

对大多数排序问题来说，机器集往往是事先给定的，而且在算法进行过程中，机器集是不变的。Imreh和Noga第一次提出了在排序中考虑机器费用的模型。他们研究了所谓的List Model problem，并给出了竞争比为（1＋5的平方根）／2≈1．618的在线算法，同时证明了该模型的任意在线算法的竞争比至少是4／3。本文研究List Model problem的一个半在线情形，我们假设工件的最大加工时间预先知道，我们将给出一个竞争比为19／12≈1．583的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是4／3。这表明部分信息有利于设计更好的算法。     

关于占线广播调度问题的一个下界

通过研究带有时限的占线广播调度问题及其贪婪算法竞争比为5、确定性算法的竞争比下界为2.59,来剖析所有请求均为紧时限的特殊情形,并运用最坏情形分析法分析得出,在任意一个连续中断的序列中最大中断比具有逐渐减小的变化特征,进而证明了在所有可能的两类连续中断序列中都不可能存在竞争比小于4的确定性算法.由此得出,当请求均为紧时限时,竞争比下界为4.由于紧时限是任意时限的一个特例,从而得出请求为任意时限时的竞争比下界至少为4的结论.     

基于双层模型的水利工程应急物资调度优化

为了提升水利工程事故应急物资调配的效率,构建综合考虑应急配送中心的应急物流能力和以总时间满意度最大为目标的应急物资调度双层模型,对应急物资调度过程进行优化。首先,根据改进的应急物流能力指标体系,对应急配送中心的应急物流能力做出评价并确定上层物资分配的权重;然后将降半哥西分布引入时间满意度函数可以综合考虑各事故点的受灾程度不同,提升物资分配的时效性与公平性。最后,根据实际水利工程事故设计算例,通过双层模型与传统模型的结果对比分析,验证该模型的有效性。结果表明：双层模型能够综合考虑实际的应急配送中心应急物流能力和各个受灾点不同的物资需求时间敏感度,得出总时间满意度最大且更为符合实际情况的应急物资调度方案。     

带机器准备时间的两台机器半在线排序

研究了两台机器的两个半在线排序问题.当机器为有准备时间的同类机时,总加工时间已知;当机器为有准备时间同型机时,最大加工时间已知.对这两个问题,给出了各自的半在线算法,证明了他们的竞争比分别至少为b 1/2b 1和2/3,其中b,为机器速度,b1=1,1＜b2=b.     

两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题

研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法—层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.     

有模机配合约束的平行机台调度方法

所描述的问题为在平行机台上具有单一模具约束的调度问题,以实现最小化拖期和为目标·描述了该问题的数学模型,并提出了如下的启发式算法,依据模具成组构成工作表,在对工作指派时根据一定条件允许改变工作的指派顺序,最后运用启发式算法ＮＢＲ(ＮｅｔＢｅｎｅｆｉｔｏｆＲｅｌｏｃａｔｉｏｎ)对调度方案进行局部调整以减少拖期和·通过一个应用实例,测试了该算法的有效性·     

两台机在线均衡调度算法的改进

研究两台平行同型机的在线均衡调度问题，利用两个不同的部分信息分别设计出两个算法，这两个算法比可能有的最好的在线算法在性能上都要好。同时还证明，就这两个部分信息来说，给出的算法是可能有的最好的算法。     

具有维修时间的两台平行机在线排序

在排序问题中,机器可能出现故障或其他原因而需要维修,因此,在加工工件时把维修时间考虑进去是很必要的.对机器维修时间完全重合、可中断的两台平行机排序问题,本文考虑它的在线情形.通过分析不同情形,给出其任意在线算法竞争比的下界为2,并给出一个最好可能的在线算法.     

有界平行批处理机的在线排序问题

主要研究的是在线运输排序问题,即研究m台有界平行批处理机上考虑工件运输的在线排序问题.工件按时间在线到达,即一个工件只有在被释放之后才能知道它的一切信息.这些工件首先要在平行批处理机上分批加工,然后加工完成的工件再被一个运输车辆运送给某个顾客.当车辆的容量是充分大的时候,给出一个最好可能的在线算法,其竞争比为(5(1/2)+1)/2;当车辆的容量有限时,给出一个竞争比为(5(1/2)+3)/2的在线算法.     

具有预约到达时间的平行机在线排序问题研究

以现代服务业预定系统中的实际问题为背景,研究了一类具有预约到达时间和最迟完工时间的在线排序问题;论证了两台机器时该问题的在线算法竞争比下界为2;在传统在线排序算法的基础上提出了针对该问题的在线贪婪算法,并分析了该算法的竞争比.