Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions

A variant of the High Multiplicity Multiprocessor Scheduling Problem with C job lengths is considered, in which jobs can be processed only by machines not greater than a given index. When C=2, polynomial algorithms are proposed, for the feasibility version of the problem and for maximizing the number of scheduled jobs.     

Integration of batching and scheduling for hot rolling production in the steel industry

This paper investigates the hot rolling production scheduling problem in the steel industry and proposes a new mixed integer programming model for this problem based on the monolithic modeling strategy that integrates batching and scheduling. Using this strategy, the new model can simultaneously schedule multiple turns and simultaneously determine the production timetable of these turns in a global optimal view. A long-term tabu search heuristic using frequency-based memory is developed to obtain near-optimal solutions for this problem. Three kinds of speed-up strategies are developed to accelerate the search procedure of the proposed tabu search. A practical scheduling system combining the proposed mathematical model and the tabu search heuristic has been developed and tested on instances collected from practical production data. The experimental results show that the proposed mathematical model and the tabu search heuristic outperform both the current manual scheduling method and the traditional serial method.     

Bandwidth allocation algorithms for weighted maximum rate constrained link sharing policy

This paper addresses the problem of bandwidth allocation under the weighted maximum rate constrained link sharing policy and proves a key theory in the condition of allocation termination. We propose several algorithms with various worst-case and average-case time complexities, and evaluate their computation elapse times.     

Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times

In this article we study thetabu search (TS) method in an application for solving an important class of scheduling problems. Tabu search is characterized by integrating artificial intelligence and optimization principles, with particular emphasis on exploiting flexible memory structures, to yield a highly effective solution procedure. We first discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. A prototype TS method is developed for this problem using the common approach of exchanging the position of two jobs to transform one schedule into another. A more powerful method is then developed that employs insert moves in combination with swap moves to search the solution space. This method and the best parameters found for it during the preliminary experimentation with the prototype procedure are used to obtain solutions to a more complex problem that considers setup times in addition to setup costs. In this case, our procedure succeeded in finding optimal solutions to all problems for which these solutions are known and a better solution to a larger problem for which optimizing procedures exceeded a specified time limit (branch and bound) or reached a memory overflow (branch and bound/dynamic programming) before normal termination. These experiments confirm not only the effectiveness but also the robustness of the TS method, in terms of the solution quality obtained with a common set of parameter choices for two related but different problems.     

Oracle 9i Data Guard技术在水调自动化系统中的应用与实施

水调自动化系统是电网运行的重要生产系统,该系统对数据库备份、数据完整性、实时性和并发访问能力等都提出了较高的要求,如何科学地应用商用数据库提供的高级功能构建稳定、可靠、高效的水调自动化系统,成为一个新课题.文中针对该问题,分析比较了多种常见的高可用数据库方案,最终选择应用Oracle Data Guard技术,构建高性能、高可用、低成本、易维护的水调自动化系统.     

一种面向车辆实时数据并行处理的任务调度算法

车辆实时监管正面临着不断增长的大规模车辆监测数据的实时处理需求,需要采用分布式的并行计算架构来提升大规模车辆监测数据处理的性能,支撑多样化的车辆监测数据处理任务,应对支撑环境的伸缩性需求。在这种架构下,对系统中不同计算节点间的车辆监测数据处理任务的调度提出了更高的要求。针对这一要求,并结合流式到达及历史积累的车辆监测数据的持续化处理需求以及大规模车辆监测数据实时处理中内存敏感的特征,提出一种基于路由表的并行任务调度算法。该算法基于车辆监测数据时空属性以及各计算节点的内存信息建立路由表,并以路由表的形式来进行任务的并行划分和分配调度,从而使得各计算节点达到负载均衡的状态。实验表明该算法能够使计算节点间的负载差异缩小到12%以内。此外,该算法在某市车辆监管实时系统中的实际应用也证明了其有效性。     

MIMO链路ad hoc网络传输调度算法

针对MIMO链路ad hoc网络中已有传输调度算法未充分利用MIMO空间复用能力的问题,提出了一种新的传输调度算法.该算法通过考虑MIMO的多流接收能力而有效地减小了调度帧长,通过合理安排节点分配顺序使得节点分配的数据流比较平均,同时,该算法通过允许节点发送多个数据流而高效利用了MIMO的空间复用能力.推导分析了传输调度算法的通过量和时延性能,结果表明,与已有算法相比,采用文中算法可以提高网络的通过量,减小网络的平均时延和最大时延.     

Achieving fair service with a hybrid scheduling scheme for CICQ switches

Providing performance guarantees for arriving traffic flows has become an important measure for today’s routing and switching systems. However, none of current scheduling algorithms built on CICQ (combined input and cross-point buffered) switches can provide flow level performance guarantees. Aiming at meeting this requirement, the feasibility of implementing flow level scheduling is discussed thoroughly. Then, based on the discussion, it comes up with a hybrid and stratified fair scheduling (HSFS) scheme, which is hierarchical and hybrid, for CICQ switches. With HSFS, each input port and output port can schedule variable length packets independently with a complexity of O(1). Theoretical analysis show that HSFS can provide delay bound, service rate and fair performance guarantees without speedup. Finally, we implement HSFS in SPES (switch performance evaluation system) to verify the analytical results.