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

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

关于总加权提前损失的两个代理单机排序问题

[目的]研究与总加权提前损失有关的两个代理单机排序的问题.[方法]第1个代理工件的工期相同,目标函数是最小化总加权提前损失;第2个代理的目标函数是最大正则函数,它的特殊情形为最大完工时间.目标是寻找一个排序,使得在满足第2个代理目标可行的情况下,第1个代理目标函数值最小.[结果]利用背包问题证明了该问题是一般意义下NP...     

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

多目标排序是排序论的一个重要分支,在解决经济、管理、工程、军事、社会等领域出现的复杂问题中起着越来越重要的作用。本文研究以误工个数∑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是放在最后不误工的工件的集合。最后,证明了这两个算法可以得到相应问题的最优解。     

一类复合并行机排序问题的多项式时间算法

在经典排序论中，一般都作以下两条假设：每台机器在任一时刻至多加工一个零件，每个零件在任一时刻至多被一台机器加工。本文研究在并行加工中多台机器可同时加工一个零件的排序问题，且每个零件可在固定的一个机器的子集上加工。在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究这种问题的计算复杂性。     

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。
     

单机分批加工最大迟后问题的一个快速算法

本文考虑了下述单机分批加工问题，在时刻零同到达的ｎ个工件需分成若干批在同台机器上加工，同批中的工件相邻，任一工件的完工时间为所在批中全部工件完工时间的，机器每加工一批工件需一相同的调整时间，文中以工件的最大迟后为目标函数，对上述分别问题用动态规划技术给出了一多项式时间算法。     

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

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

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

具有传递时间变工时的单机排序问题

确定了具有传递时间变工时的单机排序问题是ＮＰ－完全的，且讨论了它的一些特殊情况。     

一类多机排序问题算法及其计算复杂性研究

在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。     

多共同工期分配调度问题算法研究

为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该问题可解。该问题是多项式可解的,并给出了具体求解算法。     

含运输时间的柔性作业车间调度问题研究

在工厂实际生产中,零件加工的运输时间占整个加工时间的比例是很大的,这个时间在生产调度时不可忽略。为了更合理的研究柔性作业车间调度问题,将运输时间考虑进调度模型之中,并在经典遗传算法的基础上进行改进,设计了一种新的启发式规则算法,嵌入在遗传算法中,用于该问题的求解。通过计算结果的比较,证明此调度模型更符合实际生产情况。改进后的算法能够得出解的效率更高。     

基于免疫算法的带软时间窗车辆调度问题

在对带软时间窗车辆调度问题(VSPSTW)简要叙述的基础上建立了VSPSTW数学模型。针对VSPSTW问题,构造一种免疫算法来求解VSPSTW,并提出了一种新的抗体编码、改进的亲和力计算方法,将求解结果与遗传算法比较。结果表明:该算法对于求解VSPSTW问题具有较好的性能和更好的鲁棒性。     

寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法。首先利用计算机几何凸壳与中轴的结构将集划分尤其中干个子点集,然后反复采用求子点集凸壳及划分科余子点集的方法,求得通过子点集的子路径,最后将各子路径连接成一条回路。中国货郎担问题存在多项时间算法求得最短回路。     

有时间窗配送车辆调度问题的禁忌搜索算法

在对有时间窗配送车辆调度问题进行描述的基础上,建立了该问题的基于直观描述的数学模型.通过设计一种新的解的表示方法构造了求解该问题的禁忌搜索算法,并以21个节点的运输网络为例进行了实验计算.计算结果表明,用作者设计的禁忌搜索算法求解有时间窗配送车辆调度问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定.     

目标函数为加权完成时间和的单机维护调度问题研究

讨论了带有可控性维护的单机调度问题,目标是实现工件加权完成时间和的最小化．此问题是强 NP难的,因此给出了三个启发式算法和一个分枝定界算法,并通过实验对这些算法进行评价．实验结果表明其中的两个启发式算法(WSPT算法和综合算法)能得到比较好的近似最优解,分枝定界算法对小规模(n≤10)的问题很容易得到最优解．     

多CPU控制系统时间片轮转调度的一种算法

设计了一个以ＳＴＤ总线为公用总线的９ＣＰＵ多机控制系统,给出了时间片转轮调的原理、硬件电路及软件设计。     

用AGLA算法求解一类以TFT为目标的模糊Flow Shop调度问题

针对一类加工时间不确定的以总流经时间(TFT)为目标的置换Flow Shop调度问题,应用模糊数学的方法表示加工时间的不确定性,提出了一种改进的智能算法——异步遗传局部搜索算法(AGLA)。该算法初始种群的一个解由构造型启发式算法产生,其他解随机产生;通过引入一个加强的变邻域搜索机制和一个简单的交叉算子,对种群执行异步进化操作(AE);算法最后加入重启机制防止陷入局部极小。仿真实验结果验证了AGLA解决模糊Flow Shop问题的有效性。