时间相关的单机排序的最坏竞争比分析 (运筹学与控制论)

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题。工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工。本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比。进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法。     

时间相关的单机排序的最坏竞争比分析

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题.工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工.本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比.进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法.     

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。
     

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。     

Moore-Hodgson算法最优性的新证明

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一。著名的Moore-Hodgson算法可以在时间O(nlogn)内得到误工问题的最优解。虽然经过改进,然而Moore-Hodgson算法最优性的证明仍然非常复杂。本文给出Moore-Hodgson算法最优性的一个非常简洁的新的证明。由于误工问题在排序论里的重要性,本文给出的新的证明在理论上是有重要意义的,是可以为排序论的专著和教材所采纳的。此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有"一致性"关系的排序问题,或者工件的加工时间与工件的权有反向"一致性"关系的排序问题等,也可能有简洁的证明。     

部分工件必须不误工的误工排序问题

排序论中使误工工件的个数为最少的单台机器排序问题,称为误工问题,是排序论中最基本的问题之一.1973年,Sidney研究在工件的一个子集T中的工件必须不误工的条件下,使误工工件的个数为最少的误工排序问题1｜T｜∑Uj,并且给出该问题复杂性为O(n log n)的多项式算法--Sidney算法.本文把Sidney 算法改写成比较简洁的算法1,1)步骤1:设E 0=T,J－E 0=｛j1,j2,…,jm｝,j1＜j2＜…＜jm,m=n-｜T｜,令k=1:2)步骤2:若k=m+1,算法终止,(Em,J－Em)就是最优排序:若k＜m+1,转入步骤3:3)步骤3:设Fk=Ek-1∪{jk},计算Ek如下:如果Fk是不误工子集,令Ek=Ek-1∪{jk}:否则,如果Fk不是不误工子集,令Ek+Fk\{jr}.其中工件jr的加工时间为pr=max{pi｜ji∈Fk\T}.Ek中的工件是按EDD序排列.k=k+1,转入步骤2.并用数学归纳法证明算法1产生的排序是该误工问题的最优解.     

带有线性退化工件和退化维护时间的单机窗口排序

排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。     

两个多重目标排序问题的多项式时间算法 （运筹学与控制论）

多目标排序是排序论的一个重要分支,在解决经济、管理、工程、军事、社会等领域出现的复杂问题中起着越来越重要的作用。本文研究以误工个数∑Uj为第1目标,∑wjCj或者∑wjTj为第2目标的多重目标排序问题,分别给出了这两个问题在不误工工件集不改变下工件加工时间和权重满足反一致性条件(pi≤pjwi≥wj)时复杂性为O(nlogn)的多项式时间算法:对于排序问题1│(pi≤pj)(wi≥wj)│(∑wjCj/E),选取排序最后一个工件k满足条件:pk/wk=max{pi/wi│i∈M∪L};对于排序问题1│(pi≤pj)(wi≥wj)│(∑wjTj/E),选取排序最后一个工件k满足:1)若M为空集,pk/wk=max{pi/wi│i∈L};2)若M非空,任意选取k∈M。其中L是误工工件集,M是放在最后不误工的工件的集合。最后,证明了这两个算法可以得到相应问题的最优解。     

并行多机成组工件调度的启发式算法

N个成组工件将在M台并行一致的机器上加工,当一个工件接在不同组的工件之后时需要装设,而接在同组工件之后时不需要重新装设,目标函数是使总的通过时间最小·利用最优解的必要条件,将单个工件组成基本运行,在研究基本运行组合规则的基础上,提出了一个基于基本运行的并行多机成组工件调度的启发式算法·在中、小规模水平问题上,将启发式算法的结果与最优解的结果进行了比较·效果令人满意·实验证明该启发式算法能够有效地解决成组工件调度的实际问题,具有解决中大规模实际问题的潜力·     

具有通用机的多组工件的Q//C_(max)问题的近似算法

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题,人们通常寻求其近似算法。提出了一种改进的LPT算法,利用"最大相对加工时间"准则和"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,一台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤1+1/∑i∈Isi,其中I表示在最后完工的工件完工之前,在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对工件排序,在最差情况下要比最优排序多出1/∑i∈Isi的时间。     

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.     

具有共同松弛时间的恶化型工件排序问题研究

研究工件加工时间具有恶化效应的单机松弛工期排序问题.其中恶化效应指的是工件的实际加工时间是其开工时间的递增函数且所有工件的恶化率相同,工件的松弛工期等于其实际加工时间加上共同的松弛时间.目标是确定工件的一个排序和工件工期的共同松弛时间使得工件的提前时间、延迟时间和工期的共同松弛时间的线性加权和达到最小.用运筹学方法证明了该问题可以转化为两个向量的乘积问题,从而多项式时间可解,并给出了求解的最优算法.     

带有恶化和拒绝的工期指派的单机排序问题

讨论带有恶化和拒绝工件的工期指派的单机排序问题。工件的实际加工时间是其开始加工时间的线性增函数。如果工件被拒绝,则有一个惩罚费用,否则工件被加工。每个工件都要确定一个工期,文章讨论的工期指派分为CON(共同工期指派)和SLK(相同松弛工期指派)两种情况。对于CON工期指派问题,其目的是确定最优公共工期及工件的加工顺序,使工期、提前、延误和拒绝的总费用最小。将该问题归结为一系列指派问题,从而得到了一个复杂性为O(n4)的算法来求解此问题。对于SLK工期指派问题,目的是确定最优的松弛量及工件的加工顺序,使松弛、提前、延误和拒绝的总费用最小。将其归结为一系列指派问题,给出了求解此问题的多项式时间的最优算法。     

具有恶化效应、资源分配、速率修正和松弛工期的排序问题

研究带有松弛工期指派的单机排序问题,工件的实际加工时间同时受到恶化效应、凸资源分配与一次机器速率修正活动的影响。为确定工件的最优排序、速率修正活动的最优位置、最优的公共容许流和最优的资源分配量,使2个约束目标函数极小化。第1个目标函数是在满足资源总量有限的条件下,极小化总惩罚费用,即提前、延误、公共容许流和时间表长的加权和;第2个目标函数是在总惩罚有限的条件下,极小化资源消耗总费用。将上述问题分别转化为指派问题。当速率修正活动位于不同的位置时,选取使得目标函数最小的解为最优解。对2个问题分别给出多项式时间算法,算法的复杂度为O(n4),其中n为工件的数量。用数值算例分别验证2个算法,说明给出的求解算法比较有效。     

基于粒子群优化的多目标作业车间调度

为了利用粒子群优化算法解决作业车间调度问题,提出了将调度问题转化为连续优化问题的有效策略;设计了Pareto档案粒子群算法(PAPSO),该算法将档案维护和全局最好位置选取结合在一起,在档案维护过程中为每个粒子选取全局最好位置;给出了变异与PAPSO的结合新策略.将PAPSO和带变异的PAPSO应用于15个调度实例,以最小化总拖后时间和最大完成时间,与强度Pareto进化算法2等进行比较,结果验证了PAPSO在作业车间调度方面的良好性能.     

用GA算法解不同交货期窗口下的E/T调度问题

针对准时生产制下提前 /延迟 ( E/ T)费用的生产排序与调度问题 ,对不同交货期窗口下 E/ T指标的单机调度问题进行了分析 ,给出了在给定加工顺序条件下求解最优加工时间的动态规划算法。在此基础上 ,应用 GA( genetic al-gorithms)算法实现了求解。为提高算法优化性能 ,针对问题本身特性 ,分别从关键参数的选取 ;交叉操作的动态控制 ;变异操作的优化 3方面提出了相应改进策略。最后利用计算机仿真对算法性能进行研究 ,并得到一些经验性结论。仿真结果表明 ,该算法在优化性能和时间性能上均能满足工程上的要求。     

遥感卫星地面站资源调度的混合分解算法

针对传统算法逐渐难以满足地面站资源调度对精度和时效要求的问题, 提出一种混合分解算法. 该算法结合基于地面站资源使用冲突程度评价指标的启发式算法和Lagrange分解算法对问题进行求解, 以加快对最优解的搜索速度. 仿真测试结果表明, 该算法能在较短时间内得到遥感卫星地面站资源调度问题的高质量解.     

基于D-tree分解的欠约束与完备约束的几何约束求解

提出了解决欠约束、完备约束的几何约束问题的D-tree分解算法.首先,提出了一种适用范围更广的处理特殊约束策略,可以将这种特殊约束与普通约束统一化,采用转化策略将欠约束的几何约束问题转化为完备约束的几何约束问题.然后,根据几何约束图中结点的度的性质给出了D-tree分解算法,相比经典算法,D-tree分解算法拥有更低算法复杂度和相同的求解域.最后,根据D-tree分解算法结果的规律性,给出了一个为基于数值的求解方法导出求解序列的策略.D-tree分解算法通过导出的求解序列将提高几何约束求解中基于数值的求解方法的求解效率.     

一种无延迟的水文时间序列预测方法

为解决水文时间序列预测中,序列连续值间存在着高度的自相关性,而引起峰值点的预测时间落后于真实时间的问题,提出一种基于CSVMD-LSTM-ELM的无延迟预测方法。首先,将变分模态分解算法(variational mode decomposition,VMD)与布谷鸟搜索算法(cuckoo search algorithm,CS)相结合,其中,VMD用于削弱时间序列间的相关性,CS用于全局搜索VMD参数的最优解,并重点关注预测延迟的问题,为此,定义了一种新的适应度函数;其次,为分解得到的子序列建立了长短期记忆神经网络(long and short-term memory neural network,LSTM)和极限学习机(extreme learning machine,ELM)两种网络结构,分别讨论了单一网络和组合网络预测效果的优劣;最后,在秦淮河流域数据集上进行实验验证,与原有的LSTM和VMD-LSTM-ELM方法进行比较。结果表明,所提方法相较于其他方法,预测的峰值时间延迟更小,预测误差更低。可见,所提方法能够解决预测的延迟问题。