A memetic approach to vehicle routing problem with dynamic requests

The paper presents an effective algorithm for solving Vehicle Routing Problem with Dynamic Requests based on memetic algorithms. The proposed method is applied to a widely-used set of 21 benchmark problems yielding 14 new best-know results when using the same numbers of fitness function evaluations as the comparative methods. Apart from encouraging numerical outcomes, the main contribution of the paper is investigation into the importance of the so-called starting delay parameter, whose appropriate selection has a crucial impact on the quality of results. Another key factor in accomplishing high quality results is attributed to the proposed effective mechanism of knowledge transfer between partial solutions developed in consecutive time slices. While particular problem encoding and memetic local optimization scheme were already presented in the literature, the novelty of this work lies in their innovative combination into one synergetic system as well as their application to a different problem than in the original works.     

A heuristic to solve the synchronized log-truck scheduling problem

We present a synchronized routing and scheduling problem that arises in the forest industry, as a variation of the log-truck scheduling problem. It combines routing and scheduling of trucks with specific constraints related to the Canadian forestry context. This problem includes aspects such as pick-up and delivery, multiple products, inventory stock, multiple supply points and multiple demand points. We developed a decomposition approach to solve the weekly problem in two phases. In the first phase we use a MIP solver to solve a tactical model that determines the destinations of full truckloads from forest areas to woodmills. In the second phase, we make use of two different methods to route and schedule the daily transportation of logs: the first one consists in using a constraint-based local search approach while the second one is a hybrid approach involving a constraint programming based model and a constraint-based local search model. These approaches have been implemented using COMET2.0. The method, was tested on two industrial cases from forest companies in Canada.     

Cyclic routing algorithms in graphs: Performance analysis and applications to robot scheduling

In this paper we revisit and extend the algorithm for the cyclic project scheduling problem which was originally proposed by Romanovskii (1967). While the algorithm has been derived for fixed numerical data, we show how it can be extended to handle the problems with interval data. We also propose a new algorithm for the cyclic scheduling problem with interval data that extends the parametric method developed by Megiddo (1979) and runs in strongly polynomial time.     

可扩展性卫星任务规划系统的设计与实现

针对现有卫星任务规划系统可扩展性差的特点,设计并实现了一种类似于HLA(High Level Architecture)框架的可扩展性卫星任务规划系统HES3(High-Extensible Satellite Scheduling System).为保证HES3的可扩展性,提出了基于专家系统和约束分离的卫星任务规划算法的两阶段规划处理机制.设计了基于类甘特图和GIS(Geo-graphic Information System)视图的规划结果可视化人机交互接口.最后,通过一个应用实例说明了HES3的运行过程.     

一种网格环境下的多级资源调度策略

网格计算是近年来得到快速发展的技术,其目标是把因特网整合成一种超大规模的巨大计算机系统,以实现各种资源的全面共享,阐述了网格调度的基本概念,分析了各种资源调度策略,并提出一种基于分布式调度算法的多级资源调度策略。通过对模拟仿真实验中三种技术指标的分析,表明了该算法的高效性。     

Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows: A Monte Carlo Ant Colony System Approach

Project scheduling under uncertainty is a challenging field of research that has attracted increasing attention. While most existing studies only consider the single-mode project scheduling problem under uncertainty, this paper aims to deal with a more realistic model called the stochastic multi-mode resource constrained project scheduling problem with discounted cash flows (S-MRCPSPDCF). In the model, activity durations and costs are given by random variables. The objective is to find an optimal baseline schedule so that the expected net present value (NPV) of cash flows is maximized. To solve the problem, an ant colony system (ACS) based approach is designed. The algorithm dispatches a group of ants to build baseline schedules iteratively using pheromones and an expected discounted cost (EDC) heuristic. Since it is impossible to evaluate the expected NPV directly due to the presence of random variables, the algorithm adopts the Monte Carlo (MC) simulation technique. As the ACS algorithm only uses the best-so-far solution to update pheromone values, it is found that a rough simulation with a small number of random scenarios is enough for evaluation. Thus the computational cost is reduced. Experimental results on 33 instances demonstrate the effectiveness of the proposed model and the ACS approach.     

Development of scheduling strategies in the TITAN operating system

Scheduling strategies are evolved to solve problems of selection in operating systems. Such strategies frequently undergo evolution in time as details of the specification are changed or, more frequently, as inadequacies in them are shown up by use in a heavily loaded system. This paper describes a number of scheduling strategies used in the TITAN system, and their development to meet changing circumstances or to overcome inadequacies.     

Compiler-assisted energy optimization for clustered VLIW processors

Clustered architecture processors are preferred for embedded systems because centralized register file architectures scale poorly in terms of clock rate, chip area, and power consumption. Although clustering helps by improving the clock speed, reducing the energy consumption of the logic, and making the design simpler, it introduces extra overheads by way of inter-cluster communication. This communication happens over long global wires having high load capacitance which leads to delay in execution and significantly high energy consumption. Inter-cluster communication also introduces many short idle cycles, thereby significantly increasing the overall leakage energy consumption in the functional units. The trend towards miniaturization of devices (and associated reduction in threshold voltage) makes energy consumption in interconnects and functional units even worse, and limits the usability of clustered architectures in smaller technologies. However, technological advancements now permit the design of interconnects and functional units with varying performance and power modes. In this paper, we propose scheduling algorithms that aggregate the scheduling slack of instructions and communication slack of data values to exploit the low-power modes of functional units and interconnects. Finally, we present a synergistic combination of these algorithms that simultaneously saves energy in functional units and interconnects to improves the usability of clustered architectures by achieving better overall energy–performance trade-offs. Even with conservative estimates of the contribution of the functional units and interconnects to the overall processor energy consumption, the proposed combined scheme obtains on average 8% and 10% improvement in overall energy–delay product with 3.5% and 2% performance degradation for a 2-clustered and a 4-clustered machine, respectively. We present a detailed experimental evaluation of the proposed schemes. Our test bed uses the Trimaran compiler infrastructure.     

Compiler-assisted power optimization for clustered VLIW architectures

Clustered VLIW architectures solve the scalability problem associated with flat VLIW architectures by partitioning the register file and connecting only a subset of the functional units to a register file. However, inter-cluster communication in clustered architectures leads to increased leakage in functional components and a high number of register accesses. In this paper, we propose compiler scheduling algorithms targeting two previously ignored power-hungry components in clustered VLIW architectures, viz., instruction decoder and register file.We consider a split decoder design and propose a new energy-aware instruction scheduling algorithm that provides 14.5% and 17.3% benefit in the decoder power consumption on an average over a purely hardware based scheme in the context of 2-clustered and 4-clustered VLIW machines. In the case of register files, we propose two new scheduling algorithms that exploit limited register snooping capability to reduce extra register file accesses. The proposed algorithms reduce register file power consumption on an average by 6.85% and 11.90% (10.39% and 17.78%), respectively, along with performance improvement of 4.81% and 5.34% (9.39% and 11.16%) over a traditional greedy algorithm for 2-clustered (4-clustered) VLIW machine.     

基于制丝生产单元的智能调度模型研究与应用

随着智能制造理念在烟草制造行业的普及,本文针对红河烟厂的实际生产情况进行研究,对烟草制丝生产流程中的关键生产单元——烟片预处理生产单元的调度排产进行研究,将其抽象成为求解流程型有限缓冲区的流水线调度问题,通过模拟退火算法优化的遗传算法求解最优解,最后通过模拟不同规模的订单调度过程,验证了经过调度后的结果比未经过调度的结果更优,从而体现了模型的实用性。     

Job scheduling in multiprogrammed computer systems

The job-scheduling function in a multiprogramming computer system plays a key role in the achievement of the performance goals for the system. It is possible and convenient to partition this scheduling function into a priority assignment function and resource assignment function. Implementation of a general purpose resource assignment module permits a large family of scheduling strategies to be implemented via different priority calculation schemes. The implications of this partitioning of the scheduling function are studied by use of a simulation model. A system embodying this approach to job scheduling is discussed as an application of the approach to other types of systems.     

复杂负载下数据缓冲区自适应调度方法仿真

传统数据缓冲区调度方法调度时间长、调度结果误差大且不能够完全应对复杂负载问题。因此提出了复杂负载下数据缓冲区自适应调度方法,通过构建模拟数据缓冲区来定义调整的方向,在缓冲数据中,利用操控行为和代替方法之间进行相互不变性推测,获取数据缓冲错失函数;通过引用能力制约条件,将时间分成一些零碎的小片段,利用数据缓冲错失,获取时间约束模型;引入时间约束模型,需要依据时间顺序对事件进行调顺序,结合根据模拟自适应算法所得到的数据,使用雷达资源约束条件能够精准快速地衡量各种数据波束所要求的指令,获取自适应调度模型,为某一个调度间隔选取出最完善的自适应调度方法。通过仿真结果表明:上述方法能够完全应对复杂负载情况的问题,且数据缓冲区自适应调度时间短、调度结果误差小。     

The use of metamodeling techniques for optimization under uncertainty

Metamodeling techniques have been widely used in engineering design to improve efficiency in the simulation and optimization of design systems that involve computationally expensive simulation programs. Many existing applications are restricted to deterministic optimization. Very few studies have been conducted on studying the accuracy of using metamodels for optimization under uncertainty. In this paper, using a two-bar structure system design as an example, various metamodeling techniques are tested for different formulations of optimization under uncertainty. Observations are made on the applicability and accuracy of these techniques, the impact of sample size, and the optimization performance when different formulations are used to incorporate uncertainty. Some important issues for applying metamodels to optimization under uncertainty are discussed.     

Comparison of a centralised and distributed approach for a generic scheduling system

PEGS (Production and Environmental Generic Scheduler) is a generic production scheduler that produces good schedules over a wide range of problems. It is centralised, using search strategies with the Shifting Bottleneck algorithm. We have also developed an alternative distributed approach using software agents. In some cases this reduces run times by a factor of 10 or more. In most cases, the agent-based program also produces good solutions for published benchmark data, and the short run times make our program useful for a large range of problems. Test results show that the agents can produce schedules comparable to the best found so far for some benchmark datasets and actually better schedules than PEGS on our own random datasets. The flexibility that agents can provide for today’s dynamic scheduling is also appealing. We suggest that in this sort of generic or commercial system, the agent-based approach is a good alternative.     

不确定环境下生产项目调度研究综述与展望*

调度优化是企业生产项目管理的重要内容,然而各种不确定因素的存在导致在确定性条件假设下得到的“最优”调度方案往往变得“次优”,甚至不可实施。本文综述了不确定环境下生产项目调度的研究现状,分析了生产项目调度过程中存在的各种不确定性,阐述了不确定因素的起因与分类、不确定因素的描述方法,详细探讨了不确定环境下生产项目调度方案的求解与优化方法,以及项目调度方案的评价指标,并指出了该领域面临的挑战和有待进一步研究的问题。     

Adaptive disk scheduling with workload-dependent anticipation intervals

Anticipatory scheduling (AS) of I/O requests has become a viable choice for block-device schedulers in open-source OS-kernels as prior work has established its superiority over traditional disk-scheduling policies. An AS-scheduler selectively stalls the block-device right after servicing a request in hope that a new request for a nearby sector will be soon posted. Clearly, this decision may introduce delays if the anticipated I/O does not arrive on time. In this paper, we build on the success of the AS and propose an approach that minimizes the overhead of unsuccessful anticipations. Our suggested approach termed workload-dependent anticipation scheduling (WAS), determines the length of every anticipation period in an on-line fashion in order to reduce penalties by taking into account the evolving spatio-temporal characteristics of running processes as well as properties of the underlying computing system. We harvest the spatio-temporal features of individual processes and employ a system-wide process classification scheme that is re-calibrated on the fly. The resulting classification enables the disk scheduler to make informed decisions and vary the anticipation interval accordingly, on a per-process basis. We have implemented and incorporated WAS into the current Linux kernel. Through experimentation with a wide range of diverse workloads, we demonstrate WAS benefits and establish reduction of penalties over other AS-scheduler implementations.     

中小型企业软件过程改进方法研究

软件质量很大程度上取决于生产和维护软件的过程的质量,这一结论已被广泛认可。我国自20世纪90年代开始关注软件过程改进,先后引入ISO9000、CMM/CMMI等过程模型。但这些模型主要源于大型组织的过程经验,在中小型企业中实施起来存在诸多困难。中小型企业如何实施软件过程改进这一问题在业界和学术界一直倍受关注。结合一个典型中小型企业的软件过程改进实践提出了一个持续的、迭代增量的软件过程改进方法,可满足中小型企业希望以较低成本达到良好改进效果的需求。     

Thread prioritization: A thread scheduling mechanism for multiple-context parallel processors

Multiple-context processors provide register resources that allow rapid context switching between several threads as a means of tolerating long communication and synchronization latencies. When scheduling threads on such a processor, we must first decide which threads should have their state loaded into the multiple contexts, and second, which loaded thread is to execute instructions at any given time. In this paper we show that both decisions are important, and that incorrect choices can lead to serious performance degradation. We propose thread prioritization as a means of guiding both levels of scheduling. Each thread has a priority that can change dynamically, and that the scheduler uses to allocate as many computation resources as possible to critical threads. We briefly describe its implementation, and we show simulation performance results for a number of simple benchmarks in which synchronization performance is critical.     

Speed scaling with a solar cell

We consider the setting of a device that obtains its energy from a battery and some regenerative source such as a solar cell. We consider the speed scaling problem of scheduling a collection of tasks with release times, deadlines, and sizes, so as to minimize the energy recharge rate of the regenerative source. This is the first theoretical investigation of speed scaling for devices with a regenerative energy source. We show that the problem can be expressed as a polynomial sized convex program. We show that, using the KKT conditions, one can obtain an efficient algorithm to verify the optimality of a schedule. We show that the energy optimal YDS schedule is 2-approximate with respect to the recharge rate. We show that the online algorithm BKP is O(1)$O\left(1\right)$-competitive with respect to recharge rate.     

一种求解多处理机调度问题的a-平坦化调度算法

在分析多处理机调度问题的基础上,提出了α-平坦的概念,并将其引入到多处理机调度问题中;基于此,提出了一种新的基于α-平坦的求解多处理机调度问题的算法。算法首先对作业集合做平坦化处理,然后再对处理后所得的新问题进行求解,最终获得原调度问题的一个近似解。实验结果表明,通过该算法可以求得较好的结果,相对于其它启发式算法,该算法具有较好的稳定性。