具有优先约束的单机随机排序问题

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.     

在线约束单机排序问题的启发式算法

由于约束单机排序问题是经典装箱问题的一种推广并且同经典装箱问题有一些相同的特征。本文主要讨论了经典装箱问题的一些启发式算法在在线约束单机排序问题上的推广和最坏界估计。     

工件间具有串并有向图约束的单机随机排序问题

研究机器发生随机故障的单机排序问题,其中工件间的优先约束为串并有向图,目标函数为极小化加权完工时间和,证明了此问题多项式时间可解,并给出了多项式时间算法.     

有区间约束单机延误排序问题

研究一类推广的从准备时间ｒｉ到交工期ｄｉ的多重ｒ／ｄ区间排序问题——有区间约束单机延误排序问题。就该问题的一般情形而言证明了它是ＮＰ—困难的，对问题的特殊情形证明了它是多项式时间可解的。     

具有线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题.在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数.考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量.第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间.对两类问题讨论了最优排序的某些特征.基于对问题的分析,分别给出了求解最优资源分配的方法.结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立.     

资源有限的加权总完工时间单机排序问题

本讨论资源有限的加权总工时间单机排序问题，对现在仍为OPEN问题1｜pj=bj-ajuj，∑uj≤U｜∑wjCj给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况bj=b,wj=w,aj=a；bj=b,wj=w,uj=u；aj=a,wj=w,uj=u的最优算法。     

带有链优先序的分批排序问题

本文首次就带有优先序的分批排序问题进行了讨论，目标函数为最大完工时间．当优先序为链，一条链上的工件个数为饨，而其它链的工件个数为常数，分批的容量B大于等于链的条数，在这种情况下，问题为多项式可解的．文中并讨论了几种特殊情况的多项式算法．     

几类任务到达时间受资源约束的单机排序问题

本研究了任务到达时间受资源影响的，与时间表长有关的几个问题。对问题1|rj=bj-ajuj,∑j=1^nju≤U|Cmax的一种特殊情况给出了求任务的最优排序的算法，对问题1|rj=fj(uj),pj=p,Cmax≤C|∑j=1^nuj给出了最优算法；还给出了问题1|rj=fj(uj)|∑j=1^nujΛCmax的一个算法。     

一类资源约束排序问题

引入与研究 1| pj=fj( uj) ,∑uj U| ∑ ( wj Cj+ uj)型资源约束排序问题 .针对系统中加工顺序确定的情况 ,给出三个寻求最优资源分配的算法 ;就 fj=f和 fj=bj+ g,wj=w等情况研究系统的最优排序 .     

单机排序问题最优解的结构及其求法

本文研究了单机排序问题|r_i=0|∑|c_i-d_i|最优解的结构．提出了最优解的紧密规则，以及最优解的近似求法．     

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。     

关于机器随机故障完工时间方差最小化单机调度问题

讨论了机器随机故障时,工件完工时间方差的期望最小化单机调度问题,其中描述机器故障的计数过程为广义泊松过程.推导出了目标函数等价的确定形式,而后进一步给出了工件加工时间相同时问题的最优解.     

考虑任务优先约束的同类岸桥作业调度优化

分析了以箱组为任务对象QCSP与以整贝为任务对象QCSP的异同,指出前者更能均衡各岸桥作业负荷,并减少船舶装卸作业时间。考虑到岸桥具有作业效率差异的特点,将其视为同类平行机调度问题,同时结合任务优先约束、岸桥作业不可相互穿越与安全距离等特有约束,建立了更加符合实际的以箱组为任务对象的岸桥作业调度混合整数规划模型,其优化目标是最小化装卸作业的makespan。针对模型求解的复杂度,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的低界。实验算例表明所建立的模型能够反映岸桥作业调度过程中作业效率差异及任务优先约束现象,其算法能够在允许的运算时间内获得稳定的满意解,并且优化结果要全面优于以整贝为任务对象QCSP的调度方案。     

链式先后关系下的单机分批排序问题

在本文,我们证明链式先后关系下的单机分批排序问题是强NP困难的,解决了Albers和Brucker（1993）提出的待解决问题．关于此问题,Albers和Brucker（1993）也曾试图给出NP困难性证明,我们阐明了其证明中存在的缺陷．     

一类具有资源限制的调度问题

研究了具有线性退化及学习效应作用下的单台机器调度问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下求最大完工时间最小化问题给出了最优算法.     

带服务优先级车辆路径问题的扫描禁忌搜索算法

提出了一种带服务优先级车辆路径问题的模型(Vehicle Routing Problem with Precedence Constraints,VRPPC),和一种扫描—禁忌搜索算法(sweep-Taboo Search Algorithm,S-TSA).然后,运用S-TSA对郑煤物资供销有限公司的带有服务优先级的危险物资配送进行优化求解,并与扫描遗传算法(sweep-Genetic Algorithm,SGA),禁忌搜索算法(Taboo Search Algorithm,TSA),人工鱼群算法(Artificial Fish Algorithm,AFA)进行比较研究,研究结果显示:扫描禁忌搜索算法能在满足服务优先级的前提下,使配送费用最少.     

具有一般学习效应的单机排序问题

在具有学习效应的环境下,由于机器重复加工相同或相似的工件,因此以后加工的工件的加工时间变小.本文研究新的更一般的学习效应:Dejong学习效应.我们证明单机最大完工时间问题,总完工时间问题和两类多目标问题是多项式时间可解的.