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

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

带有退化工件和机器维修区间的单机排序问题

考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的。     

有服务等级约束的同类机在线排序问题的可分算法

研究了一类有四个服务等级的可分排序问题,在一定条件下改进了下界,并且提出了一种最优算法。在该问题中,工件和机器都带有各自的服务等级约束,当且仅当工件的服务等级比机器的服务等级高或者相同时,该机器才被允许对该工件进行加工,并且每个工件都被允许在所有机器之间按照任意的比例分割后进行加工,同一个工件的各个部分被允许同时放在各台机器上进行加工,优化目标是找到最小时间表长。     

批处理机上有就绪和截止时间的等长度工件排序

一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表.就该问题,Baptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广Garey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法.算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策.     

带有退化、拒绝和不可用区间的恒速机排序

考虑带有退化工件、拒绝和不可用区间的2台恒速机排序问题,其中一台机器上带有一段固定的不可用区间.该问题以实际生产环境为背景来研究机器的工件调度问题.在此模型中,每个工件的实际加工时间与它的基本加工时间、退化率和开始加工时间有关,工件的实际加工时间是其开始加工时间的线性递增函数,工件可以被拒绝,被拒绝的工件需要支付惩罚成...     

产品中有多个工件时加权情况下的排序问题

本文考虑的是工件在单台机器上加工随后组装成产品的下述排序问题：ｎ个产品各由一特殊工件和ｍ个共同工件组成，这ｍ个共同工件分属ｍ个不同的共同工件类，所有的工件在同一台机器上加工，机器在加工一组第ｉ类共同工件前需时间ｓｉ〉０（ｉ＝１，２，．．．ｍ），一组共同工件中任一工件的完工时间为其所在组中的全部工件完工时的时间，产品的完工时间为其特殊工件和所有共同工件均完工时的时间，目标是适当排列工件加工序使ｎ个产     

可拆分平行机排序问题的一个启发式算法

为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标.在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工.与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题.借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配.通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策.     

具有禁用区间的平行机排序时间表长问题的全多项式近似方案

近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中。传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题。对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法。研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的。在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的。给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界。     

带单服务器的平行机排序问题的复杂性

研究带单服务器的两台平行机的排序问题的复杂性,每个工件在机器加工之前,必须由服务器先进行安装,在同一时刺每一个服务器只能安装一个工件,目标是使最大完工时间达到最小.在工件具有准备时间且所有加工时间等于1的条件下,证明该问题是强NP-困难的.     

退化工件2台机器异序车间作业排序问题

：文章讨论退化工件2台机器异序车间作业排序问题。在异序车间作业环境中,每个工件由一些工序组成,工序的个数未必与机器数相同。此外,每个工件有各自的工序加工顺序。工件可能多次在某些机器上加工,也可能根本不在某些机器上加工。假设工件的实际加工时间是其开始时间的比例函数,目标函数是极小化最大完工时间。首先证明了具有任意工序的问题是强意义下NP-难的;然后对每个工件最多只有2个工序的问题给出了多项式算法;最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的。     

无容量限制的批处理机时间表问题

研究无容量限制的批处理机时间表问题，在工件有到达时间和工期约束下，证明了当工件的到达时间和工期，或到达时间和加工时间一致单调时，该问题是多项式时间可解的；当加工时间和工期一致单调时，该问题是NP困难的。     

一种新的多处理器系统实时容错算法

实时多处理器容错算法是实时系统研究领域的一个重要课题.提出了一个动态处理非周期实时任务的容错算法.提出了对待实时任务的基、副版本采用不同的处理器分配策略.对于基版本,尽量提前任务的开始时间;对于副版本,尽量延迟任务的开始时间.通过实验模拟研究了算法的性能.实验表明,算法调度的成功率跟处理器个数、任务数以及任务计算时间有关.与采用单一处理器分配策略相比,具有较高的调度成功率.     

一种基于拓扑特征的数据流调度策略

 流式处理器针对数据并行的应用,提供多个简单的处理单元及它们之间的高带宽通道,通过高计算密度掩盖传输延迟,支持高速的数据传输和处理,与通用处理器相比,性能达到了数倍乃至数百倍的提升。在流式处理器的研究中,数据流的调度是个比较重要的问题。本文提出了一种基于拓扑特征的数据流调度策略,该策略包含平分策略和选择策略两种,其中平分策略用于体系结构中固有负载较少的情况,选择策略在固有负载较多时利用拓扑权重来辅助平分策略完成数据流任务的调度。建立了该策略的性能模型,在考虑节点间传输时间的情况下进行讨论,对数据流调度策略的选择提出建议。     

两个代理的单机排序问题的多项式时间算法

考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.     

带有退化效应和不可用区间的并行批排序问题

在制造业中,处理机由于长时间使用而发生故障或进行维护、保养等原因,产生一些不可用区间;并且工件的实际加工时间往往与它的开始加工时间有关。研究一种带有退化效应和不可用区间的无界单机并行批处理机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数。而并行批处理机中,同批工件同时开始加工,同时完工,且批一旦开始加工就不可中断;每批的加工时间等于这批工件中加工时间的最大者;同批中工件的完工时间都相同,为这批的完工时间。讨论的目标函数为最大完工时间问题。通过对最优解性质的分析,给出了求解此问题的多项式时间的最优算法。     

基于AADL的汽车防滑控制系统可调度性分析

针对设计阶段难以对汽车防滑控制系统进行可调度性分析的问题,利用AADL为该系统建模.根据实时系统中任务调度与线程、计算时间、处理器性能之间的关系,在任务数不变的情况下选取不同性能的处理器,通过OSATE对该系统模型进行分析.结果表明此方法可有效解决这一问题,该建模方法为系统的可调度性分析和优化设计提供了一条新的途径.     

An Efficient Real-Time Fault-Tolerant Scheduling Algorithm Based on Multiprocessor Systems

In the context of real-time fault-tolerant scheduling in multiprocessor systems, Primary-backup scheme plays an important role. A backup copy is always preferred to be executed as passive backup copy whenever possible because it can take the advantages of backup copy de-allocation technique and overloading technique to improve schedulability. In this paper, we propose a novel efficient fault-tolerant ratemonotonic best-fit algorithm efficient fault-tolerant rate-monotonic best-fit （ERMBF） based on multiprocessors systems to enhance the schedulability. Unlike existing scheduling algorithms that start scheduling tasks with only one processor. ERMBF pre-allocates a certain amount of processors before starting scheduling tasks, which enlarge the searching spaces for tasks. Besides, when a new processor is allocated, we reassign the task copies that have already been assigned to the existing processors in order to find a superior tasks assignment configuration. These two strategies are all aiming at making as many backup copies as possible to be executed as passive status. As a result, ERMBF can use fewer processors to schedule a set of tasks without losing real-time and fault-tolerant capabilities of the system. Simulation results reveal that ERMBF significantly improves the schedulability over existing, comparable algorithms in literature.     

多处理机实时分类调度算法研究

讨论了在多处理机实时系统中周期任务可调度性的充要条件和非周期任务的分布函数,并进行了任务调度模型设计。通过处理器利用率实现对实时任务的动态分类,并根据这些分类进行处理器分派。仿真结果表明,这种方法能有效提高实时任务的调度成功率;在处理器达到5个时,调度率可达98%以上,基本属于最优调度,平均负载达到最小且趋于平稳。     

Optimal algorithms for scheduling large scale application on heterogeneous systems

This paper studies optimal algorithms for scheduling largescale application on heterogeneous systems using Divisible Load Theory. A more realistic and general model, i.e., both processors and communication links may have different speeds and arbitrary startup costs, and communication is in nonblocking mode, is introduced. Under such environment, the following results are obtained: ①Mathematic model and closedform expressions both for the processing time and the fraction of load for each processor are derived;②the influence of startup costs on the optimal processing time is analyzed; ③for a given heterogeneous systems and a largescale computing problem, optimal algorithms are proposed.