一种双匹配动态调度算法

提出了适于异构环境独立任务调度的双匹配动态调度算法（BM算法）．BM算法将任务与处理机实现双匹配，使大部分任务在执行时间最短而且完成时间最早的处理机上执行．对于无法实现双匹配的任务，采用最早完成时间最小者优先的策略进行调度．BM算法可以同时满足负载均衡和高吞吐率两个目标．BM算法与通常用作评测基准的Min-min算法的比较结果表明，BM算法的运行时间远少于Min-min算法，其调度跨度比Min-min算法减少约9％．     

用带蚁群搜索的多种群遗传算法求解作业车间调度问题

结合遗传算法和蚁群算法的优点，提出一种带蚁群搜索的多种群遗传算法．多个种群各自遗传进化，用蚁群搜索得到的解替代各种群中的较劣个体，增加种群的多样性，提高种群的质量；根据各种群最优个体设定初始信息素，大大缩短信息素的累积过程，加快蚁群搜索的速度．利用算法对典型作业车间调度问题进行求解,仿真计算结果表明,该算法是有效的.     

Linux操作系统的实时化设计

提出了一种基于优先级的抢占调度外加相同优先级任务时间片轮转调度算法，以解决普通Linux中的优先级倒置和中断处理时不能处理外部硬件中断而导致响应时间过长的问题，使改造后的Linux可适应实时应用场合。     

公交车线路运营调度及评估系统的研究与实现

以公交车线路运营系统为背景，提出了各站上、下车人数分布的数学模型，并以此模型为基础，为公交车线路运营的调度问题，提供了一种较好的解决方法。对线路运营的一些重要指标进行了量化分析，建立了相关的数学模型。基于面向对象技术，开发了《公交车线路运营调度及评估系统》软件。软件和相关模型实现了对线路运营进行评估和优化公交车配置。     

求解非满载车辆调度问题的免疫遗传算法

非满载车辆调度问题是车辆调度问题中的一个基本问题,由于它是一个典型的NP难题,传统方法的求解结果往往不能令人满意.曾有研究将传统的遗传算法用于求解非满载车辆调度问题,但是由于遗传算法在遗传后期的波动现象,导致了迭代次数过大和准确率不高.该实验根据生物免疫系统的机理提出的免疫遗传算法,结合了遗传算法的进化操作和生物免疫中的浓度机制,通过抗体的期望繁殖率实现对抗体的促进和抑制,改善未成熟收敛.该算法是在传统遗传算法全局随机搜索的基础上,借鉴生物免疫机制中抗体的多样性保持策略,改善了传统遗传算法的群体多样性,通过与遗传算法的比较,结果表明,该算法不仅收敛,而且具有更好的全局和局部搜索能力和收敛速度.     

多模式智能教学系统教学规划与模式调度研究

具有多种教学模式的智能教学系统为适应不同学生的学习风格和学习要求，具有其它智能教学系统不可替代的优势，其关键问题之一是要解决教学规划和教学模式调度问题。提出了多模式智能教学系统的教学规划及教学模式调度的解决方案，以知识点关系图为基础提出了全局教学规划算法，根据对学生学习的评价和教学资源的相关特征为学生选择合适的教学模式并激活之。实验证明这种解决方案能取得令人满意的效果。     

A Decomposition and Coordination Scheduling Method for Flow-shop Problem Based on TOC

There are many flow shop problems of throughput (denoted by FSPT) with constraints of due date in real production planning and scheduling. In this paper, a decomposition and coordination algorithm is proposed based on the analysis of FSPT and under the support of TOC (theory of constraint). A flow shop is at first decomposed into two subsystems named PULL and PUSH by means of bottleneck. Then the subsystem is decomposed into single machine scheduling problems, so the original NP-HARD problem can be transferred into a serial of single machine optimization problems finally. This method reduces the computational complexity, and has been used in a real project successfully.     

Optimal control of parallel queues with impatient customers

We consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process with an arrival rate which is a non-increasing function of the number of customers in the system. Upon arrival, a customer must join a server’s queue according to a stationary state-dependent policy, where the state is taken to be the number of customers in servers’ queues. No jockeying among queues is allowed. Each arriving customer is limited to a generally distributed patience time after which it must depart the system and is considered lost. Two models of customer behavior are considered: deadlines until the beginning of service and deadlines until the end of service. We seek an optimal policy to assign an arriving customer to a server’s queue. We show that, when the distribution of customer impatience satisfies certain property, the policy of joining shortest queue (SQ) stochastically minimizes the number of lost customers during any finite interval in the long run. This property is shown to always hold for the case of deterministic customer impatience.     

Stability of size-based scheduling disciplines in resource-sharing networks

Size-based scheduling strategies such as Shortest Remaining Processing Time first (SRPT) and Least Attained Service first (LAS) provide popular mechanisms for improving the overall delay performance by favoring smaller service requests over larger ones. The performance gains from these disciplines have been thoroughly investigated for single-server systems, and have also been experimentally demonstrated in web servers for example. In the present paper we explore the fundamental stability properties of size-based scheduling strategies in multi-resource systems, such as bandwidth-sharing networks, where users require service from several shared resources simultaneously. In particular, we establish the exact stability conditions for the SRPT and LAS disciplines in various limiting regimes. The results indicate that size-based scheduling strategies may fail to use the available resources efficiently, and in fact cause instability effects, even at arbitrarily low traffic loads, and will therefore not yield optimal delay performance. The qualitative findings confirm the tendency for users with long routes and large service requirements to experience severe performance degradation.     

Optimizing Grid-Based Workflow Execution

Large-scale applications can be expressed as a set of tasks with data dependencies between them, also known as application workflows. Due to the scale and data processing requirements of these applications, they require Grid computing and storage resources. So far, the focus has been on developing easy to use interfaces for composing these workflows and finding an optimal mapping of tasks in the workflow to the Grid resources in order to minimize the completion time of the application. After this mapping is done, a workflow execution engine is required to run the workflow over the mapped resources. In this paper, we show that the performance of the workflow execution engine in executing the workflow can also be a critical factor in determining the workflow completion time. Using Condor as the workflow execution engine, we examine the various factors that affect the completion time of a fine granularity astronomy workflow. We show that changing the system parameters that influence these factors and restructuring the workflow can drastically reduce the completion time of this class of workflows. We also examine the effect on the optimizations developed for the astronomy application on a coarser granularity biology application. We were able to reduce the completion time of the Montage and the Tomography application workflows by 90% and 50%, respectively.