可扩展并行作业调度模拟器ParaSim设计与应用

针对作业调度研究的需求,设计和实现了一个可扩展的并行作业调度模拟器ParaSim。ParaSim采用与实际并行作业系统近似的工作流程,以资源占用矩阵来表示计算资源,使用事件驱动的模式进行模拟调度和运行,支持空间共享和时间共享等多种调度策略,并允许对各调度参数进行设置。ParaSim已投入实际使用,为并行机作业调度策略的定量分析、调整和优化提供了有力的支持。     

大规模并行计算机作业调度评价

大规模并行计算机的作业调度直接关系到其计算能力的发挥,因而相应的研究具有十分重要的意义。论文通过对国外现有作业调度评价体系的研究,建立了更能反映并行作业特点的作业调度策略评价体系,在此基础上设计并实现了一个作业模拟调度环境。模拟调度环境采用事件驱动的工作模式,支持FCFS、大作业优先、小作业优先、长作业优先、短作业优先、GANG等调度策略。模拟测试结果表明,GANG调度策略优于所有测试的空间共享调度策略;同时在空间共享调度策略中,短作业优先策略和大作业优先策略具有较好的性能。     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

并行对象调度策略

从并行系统的软件设计模式出发,结合面向对象的思想,阐述了在并行系统中以对象为中心进行任务调度的策略.给出了一种具体的算法并简要地分析了该算法的性能.     

数值天气预报后处理系统的作业级并行实现

对于具体问题采取何种并行方法,达到好的并行效果,是在并行化工作中需要考虑的.通过对数值天气预报模式T511后处理系统的特点分析,结合其运行的计算机环境特点,提出了一种"作业级的并行实现"方法,减少T511后处理系统所需的计算墙钟时间.该方法具有并行化工作量小、易于实现、并行效果好等特点.     

多机并行作业车间调度的混合粒子群算法

本文通过对多目标多机作业车间调度的研究提出了一个改进的结合启发式规则的粒子群算法,采用了依机器和工件排序的编码规则,两段式的表达形式,带启发式规则的调整,并结合聚类分析思想的保留策略,对此类问题提出了一个新的解决方法,并在文中通过一个仿真案例进行求解。     

负载调度策略的设计与实现

并行处理机系统中负载不平衡问题一直没有得到彻底地解决，国内外学者提出过多种解决办法，但都有不尽人意的地方。讨论了如何确定一个处理机的负载已达到阈值和如何选择任务要送到的结点等亟待解决的问题。一个处理机只要有任务在运行就不能算是空间，由空间的处理机申请任务可以决定任务要送到的结点，用这种方法调度并行处理机系统比其他方法有更高的效率。本方法在同构的计算机系统和异构的计算机系统中应用效果都很好。     

分布式计算机系统并行调度的探讨

分布式系统中的并行调度一直是一个十分活跃的课题.本文对系统的性能指标和调度技术予以介绍,最后总结了相关研究工作.     

工件工序可并行的作业车间调度模型与求解

针对传统作业车间调度模型没有考虑工件工序存在并行性的不足,提出一种以最小化完工时间为目标的工件工序可并行作业车间调度模型,且在模型中考虑了工序加工设备柔性;设计了基于遗传算法的调度算法,其中染色体编码采用分段编码方式,并提出一种适用于工件工序存在并行性的染色体解码方法.实验结果表明,文中算法能够有效地解决工件工序可并行的作业车间调度问题.     

柔性Job shop集成化计划调度模型及其求解算法

考虑不同加工工艺路径的成本因素，从集成化的角度研究了柔性Job shop计划和调度问题，针对问题的结构特点，建立了两层混合整数规划模型，提出门槛接受，遗传算法与启发式规则相结合的混合求解算法，综合考虑各层次决策问题进行求解，实例计算表明，该算法可迅速求得问题的近优解，表现出良好的求解性能。     

Algorithms for scheduling incompatible job families on single batching machine with limited capacity

Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively.     

ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times

To date, the topic of unrelated parallel machine scheduling problems with machine-dependent and job sequence-dependent setup times has received relatively little research attention. In this study, a hybrid artificial bee colony (HABC) algorithm is presented to solve this problem with the objective of minimizing the makespan. The performance of the proposed HABC algorithm was evaluated by comparing its solutions to state-of-the-art metaheuristic algorithms and a high performing artificial bee colony (ABC)-based algorithm. Extensive computational results indicate that the proposed HABC algorithm significantly outperforms these best-so-far algorithms. Since the problem addressed in this study is a core topic for numerous industrial applications, this article may help to reduce the gap between theoretical progress and industrial practice.     

基于DSP的并行软件系统的设计与实现

随着超大规模集成电路技术的发展,数字信号处理器的处理能力不断提高.介绍系统软件运行的硬件平台及功能,描述系统硬件的软件接口技术及其实现方法,设计并实现了一个基于VME总线技术.采用Link口互联的DSP 21160N并行软件系统,对系统性能进行测试与分析,结果表明,该并行软件系统能够满足设计要求.最后对系统的研究和实际工作做出总结.     

遗留系统并行架构的设计与实现

面向服务的体系架构(SOA)为遗留系统的再工程提供了解决方案,使得遗留系统可以支持分布式应用环境,但是由于技术的陈旧和架构的局限性,无法支持多线程、并行处理以及内存泄露等问题依旧在部分遗留系统中存在,极大地限制了它们的应用。为了解决这几个问题,通过深入分析研究Windows 通信基础(WCF)的通信机制,提出了一种并行架构,对WCF的基本架构进行了改造,即在默认的体系架构中添加一层服务控制器,用来在客户端和服务端之间传递消息和选择服务,很好地解决了这几个问题,并在某大型金融软件中得到了应用。     

三台机并行工件排序问题的改进的下界

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

Bicriteria scheduling problem for unrelated parallel machines with release dates

This research proposes a heuristic and a tabu search algorithm (TSA) to find non-dominated solutions to bicriteria unrelated parallel machine scheduling problems with release dates. The two objective functions considered in this problem are to minimize both makespan and total weighted tardiness. The computational results show that the proposed heuristic is computationally efficient and provides solutions of reasonable quality. The proposed TSA outperforms other algorithms in terms of the number of non-dominated solutions and the quality of its solutions.     

Data token heuristic scheduling of the Kalman algorithm onto a message-passing multiprocessor system

Scheduling the tasks of a parallel algorithm onto a network of processors to minimize the completion time of the task graph is an NP-hard problem, and heuristic methods are commonly used to solve this problem. Published works in this area, however, do not take advantage of the following aspects of the problem: (i) the availability of the full knowledge of the data that is being transferred during inter-task communication, and (ii) the availability of full duplex high-speed communication links in many multiprocessors (such as transputers). The scheduling approach presented in this paper, the data token heuristic (DTH) approach, exploits the above features, leading to a reduced schedule length. This is achieved by checking the pool of data tokens in the processors, and routing the required data token to the processor through the dynamic shortest path. The DTH approach is then used to find the best transputer network topology that gives the minimum schedule length for the parallel implementation of the Kalman algorithm. Quantitative results of scheduling the Kalman algorithm on a 4-transputer network with T-805 transputers are presented.