极小化加权总完工时间的分批排序问题

本文讨论了分批排序中极小化加权总完工时间的两个问题.就所有工件的加工时间都相等这一特殊情况,分别给出两个算法,并证明了算法的最优性.

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究 3台机器调整时间可分离的无等待 Flow Shop排序问题 ,目标函数为极小化折扣加权总完工时间。对某些特殊情况 ,给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待 Flow Shop排序问题的分派规则。

一类无界的不相容工件族分批排序加权总完工时间问题

考虑极小化加权总完工时间的一类无界的不相容工件族分批排序问题,给出了最优排序的性质和算法,并加以证明.对工件有k个到达时间的情形,给出了一个复杂性为O(2^(k-1)nlogn)的启发式算法.

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

讨论工件加工时间依赖于分配给它的一类资源,且加权总完工时间有限,目标函数为极小化资源总量的单机排序问题,对问题1,给出了一个有关最优解中最优资源使用的重要性质并利用该性质,对于bj=b,wj=w,aj=a这种特殊情况给出了最优算法.

加工时间相同的分族分批排序加权总完工时间问题

考虑极小化加权总完工时间的单机分族分批排序问题,给出了最优排序的性质和算法,并加以证明,对工件有k个到达时间的情形,给出了一个复杂性为的启发式算法。

折扣加权总完工时间问题的半在线排序算法

讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|r_j,p_(min)≤p_j≤p_(max)|∑w_j(1-e^(-βC_j)),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间p→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同p_(min)=p_(max)

具有周期维护的最小化加权总完工时间的平行机调度研究

针对具有周期维护的最小化加权总完工时间的平行机调度问题,首先证明了该调度问题是NP-难问题,并提出最优调度方案的4条性质。然后在WSPT规则的基础上结合工件在多机环境中的分配机制(JCT、MCT、BF)提出了WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法,其中ROPT算法为其他3个算法的最优输出。最后通过数值实验对4个算法进行性能分析,结果显示:WSPTJCT算法、WSPTBF算法以及ROPT算法的性能与最大加工时长pmax呈倒U型;工件个数n越大,WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能越好。

加权总完工时间有限的受资源约束排序问题

研究 1 | pj=fj( uj) ,∑jwj Cj≤C| ∑juj 型受资源约束排序问题。针对问题中加工顺序确定的情况给出两个寻求其最优资源分配的算法 ;就 fj=f和 fj=b- ajuj。

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。

无等待Flowshop带折扣加权排序问题的最优算法

讨论了目标函数为带折扣的加权总完工时间的无等待Flowshop排序问题,对其中三种特殊情况给出了最优算法.第一种问题是机器满足单调递增优势关系,第二种问题是机器满足单调递减优势关系,第三种是机器满足先递增、后递减的优势关系.

一类加工时间依赖资源的单机成组排序问题

研究了加工时间依赖资源的成组排序问题.在这类问题中,加工时间是资源的线性函数,工件被分成若干个组,同组内的工件需连续加工,不允许分开,各工件组有固定的安装时间,目标函数为极小化加权总完工时间.针对这类问题构造了一个有效的下降算法.

工件加工时间为非线性分段函数的单机排序问题

讨论工件加工时间是开工时间非线性分段函数的单机排序问题,目标函数为极小化最大完工时间,总完工时间和加权总完工时间.对于目标函数为极小化最大完工时间和总完工时间的问题,给出了求解最优排序的多项式算法,对于目标函数为加权总完工时间的问题,给出了工件间的一致关系.

基于加权总完工时间的两人合作排序博弈

现实活动中,往往存在一方无法独自完成一个项目中全部工件加工任务的情况,这就需要双方或者多方合作共同完成任务。假设每人有一台用于加工工件的机器,通过确定这批工件的一个恰当划分,把工件分配给两台机器,使得双方合作收益最大。本文研究当工件加工时间是其开工时间线性恶化函数,以最小的加权总完工时间作为加工成本,建立两人合作排序博弈模型。通过运用Matlab软件,分析不同的盈利能力和机会成本对最优解的影响,并与以总完工时间作为加工成本的模型进行比较,表明本文模型在盈利能力不强以及恶化因子小的情况下都可以求得最优解。

一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究

本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.

单步预测的单机调度算法及其仿真分析

调度问题中在线算法只能够利用已经到达的工件信息进行调度,但在实际生产中,往往有可能预知即将到达的未来工件信息,并且利用信息进行决策。针对经典单机加权完工时间调度问题,根据预测控制的思想,提出了一种单步预测调度的算法,并且分别在理论证明和仿真两方面进行了分析。对单步预测调度算法进行了性能分析,在理论上证明了预测调度算法的竞争比下界为2,对于一般的情况进行了大量的仿真比较,由于在调度中增加了未来信息,单步预测调度算法的调度结果优于在线调度算法。

带有资源冲突的Seru在线并行调度算法

随着大规模定制的市场需求日趋显著,赛如生产系统(Seru production system,SPS)应运而生,逐渐成为研究和应用领域的热点.本文针对带有资源冲突的Seru在线并行调度问题进行研究,即需要在有限的空间位置上安排随动态需求而构建的若干Seru,以总加权完工时间最小为目标,决策Seru的构建顺序及时间.先基于平均延迟最短加权处理时间(Average delayed shortest weighted processing time,AD-SWPT)算法,针对其竞争比不为常数的局限性,引入调节参数,得到竞争比为常数的无资源冲突的Seru在线并行调度算法.接下来,引入冲突处理机制,得到有资源冲突的Seru在线并行调度算法,αAD-I(α-average delayed shortest weighted processing time-improved)算法,特殊实例下可通过实例归约的方法证明其竞争比与无资源冲突的情况相同.最后,通过实验,验证了在波动的市场环境下算法对于特殊实例与一般实例的优越性.

基于流水线调度问题的模型与局部搜索算法

在基于流水线的调度问题中,所有工件按照相同的顺序访问机器,但部分或全部工件可以不必在某些机器上进行加工.标准flowshop问题是这种流水线调度问题的一个特例.研究了带序依赖和机器依赖加工准备时间的流水线调度问题,针对该问题建立了一个基于序列的0～1混合整数规划模型,目标函数是总加权完工时间最小,提出了相应的局部搜索算法,实验结果证明了算法的有效性和可应用性,所提出的局部搜索算法的求解思路对同类流水线调度问题具有指导意义。

具有学习效应的两个单机排序问题(英文)

研究工件具有学习效应的两个单机排序问题.工件的学习效应指的是工件的加工时间为所排位置的函数.对以下两个目标函数:加权总完工时间与最大延误,证明在某些特殊情况下加权最小加工时间优先(WSPT)规则和最早工期优先(EDD)规则可以分别给出最优算法.也给出了这两个规则在一般条件下的最坏情况界.

基于单机排序问题的降落飞机分组排序方法

为使单跑道降落飞机排序结果在实际操作时可行、简单,首先限制同一航路段上的飞机按照先来先服务的原则排序,在最终的排序中,其拓扑次序不变;其次提出了将飞机分组排序的思想,对同一航路段上刚好满足最小安全间隔的飞机做为一个飞机组参与排序。使用1|chains|∑wjcj做为排序模型,通过求解各飞机链的ρ因子可以快速得到排序结果。将本方法用于对双流国际机场和其它几个机场的实际航迹数据进行计算,得到的排序序列完全符合实际管制需要,具有很高的推广应用价值。