CAMPS: a constraint-based architecturefor multiagent planning and scheduling

A new integrated architecture for distributed planning and scheduling is proposed that exploits constraints for problem decomposition and coordination. The goal is to develop an efficient method to solve densely constrained planning/scheduling problems in a distributed manner without sacrificing solution quality. A prototype system (CAMPS) was implemented, in which a set of intelligent agents try to coordinate their actions for satisfying planning/scheduling results by handling several intra- and inter-agent constraints. The repair-based methodology for distributed planning/scheduling is described, together with the constraint-based mechanism of dynamic coalition formation among agents.     

How Lean transformation affects scheduling

The Lean paradigm transforms a production company from utilisation-centric planning into a system in which other operating conditions such as short flow times, local control, reduction in variation, and first-in-first-out control are weighted as well. This paper studies how the scheduling of production changes when the above four conditions are implemented. Their effects are studied by constructing an optimisation model for the scheduling of a flow shop. The optimisation model is based on the following ideas. First, when the flow time is emphasised, the objective of the scheduling changes from utilisation to a short flow time. Second, if local control is used, it means that the optimisation is performed locally, i.e. individually at each station, and it concerns the makespan at the station. Third, if the variation is reduced, the processing times and arrival times have less variation and, fourth, the scheduling can force the flow times to have less variation by using first-in-first-out (FIFO) sequencing. The experimental results achieved using the model describe how and in which order the operating conditions under study should be implemented in the scheduling. For example, if utilisation is important, local control and FIFO should not be used before variation is reduced.     

A constraint-based approach for the shift design personnel task scheduling problem with equity

This paper presents an industrial problem which arises in a company specialized in drug evaluation and pharmacology research. The aim is to build employee timetables covering the demand given by a set of fixed tasks. The optimality criterion concerns the equity of the workload sharing. A solution to this problem is the assignment of all tasks whose resulting working shifts respect tasks requirements as well as legal and organizational constraints. Scheduling problems usually consider a fixed set of shifts which have to be assigned to a given number of employees whereas in our problem shifts are not fixed and are deduced from the task assignment. In the following, we refer to this problem as the shift-design personnel task scheduling problem with an equity criterion (SDPTSP-E), in reference to the shift minimization personnel task scheduling problem (SMPTSP). Even if the SDPTSP-E is related to several problems, none of them allow to grasp its full complexity. Consequently, we propose a dedicated method based on constraint programming. Several branching and exploration strategies are proposed and tested.     

一种支持单组播集成调度的并行分组交换结构*

针对已有基于单芯片交换结构的单组播集成调度算法在高速链路环境下无法在一个时隙内完成一次调度的问题,提出了一种支持单组播集成调度的并行分组交换结构UMSPPS（Uni-and multicast supported parallel packet switch）。通过动态地调整单播平面数和组播平面数,UMSPPS可以支持任意比例的单组播混合业务。仿真结果表明,在各种比例的单组播业务情况下,UMSPPS的时延总是低于FILM和f SCIA,并且具有最优的总体吞吐率。     

支持区分服务的自适应队列调度算法

分析了在DiffServ模型下的WRR和DWRR调度算法,提出了一种基于WRR的改进的 调度算法AWRR(ADWRR),同时提出了AWRR调度算法的实现过程。该算法根据网络中各业务数 据的实际流量动态的调整其对应的权值。因此AWRR不仅能提供QoS保证,而且还能根据该节点的 实际负载状况,提供动态的带宽分配。     

Exploring gene causal interactions using an enhanced constraint-based method

DNA microarray provides a powerful basis for analysis of gene expression. Bayesian networks, which are based on directed acyclic graphs (DAGs) and can provide models of causal influence, have been investigated for gene regulatory networks. The difficulty with this technique is that learning the Bayesian network structure is an NP-hard problem, as the number of DAGs is superexponential in the number of genes, and an exhaustive search is intractable. In this paper, we propose an enhanced constraint-based approach for causal structure learning. We integrate with graphical Gaussian modeling and use its independence graph as an input of our constraint-based causal learning method. We also present graphical decomposition techniques to further improve the performance. Our enhanced method makes it feasible to explore causal interactions among genes interactively. We have tested our methodology using two microarray data sets. The results show that the technique is both effective and efficient in exploring causal structures from microarray data.     

Data locality and parallelism optimization using a constraint-based approach

Embedded applications are becoming increasingly complex and processing ever-increasing datasets. In the context of data-intensive embedded applications, there have been two complementary approaches to enhancing application behavior, namely, data locality optimizations and improving loop-level parallelism. Data locality needs to be enhanced to maximize the number of data accesses satisfied from the higher levels of the memory hierarchy. On the other hand, compiler-based code parallelization schemes require a fresh look for chip multiprocessors as interprocessor communication is much cheaper than off-chip memory accesses. Therefore, a compiler needs to minimize the number of off-chip memory accesses. This can be achieved by considering multiple loop nests simultaneously. Although compilers address these two problems, there is an inherent difficulty in optimizing both data locality and parallelism simultaneously. Therefore, an integrated approach that combines these two can generate much better results than each individual approach. Based on these observations, this paper proposes a constraint network (CN)-based formulation for data locality optimization and code parallelization. The paper also presents experimental evidence, demonstrating the success of the proposed approach, and compares our results with those obtained through previously proposed approaches. The experiments from our implementation indicate that the proposed approach is very effective in enhancing data locality and parallelization.     

Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis

This paper presents a heuristic algorithm for solving a job-shop scheduling problem with sequence dependent setup times and min/max separation constraints among the activities (SDST-JSSP/max). The algorithm relies on a core constraint-based search procedure, which generates consistent orderings of activities that require the same resource by incrementally imposing precedence constraints on a temporally feasible solution. Key to the effectiveness of the search procedure is a conflict sampling method biased toward selection of most critical conflicts and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This constraint-based search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically both on a set of previously studied job-shop scheduling benchmark problems with sequence dependent setup times and by introducing a new benchmark with setups and generalized precedence constraints.     

Upper-level scheduling supporting multimedia traffic in cellular data networks

Wireless data networks such as cdma2000 1x EV-DO and UMTS HSDPA use downlink scheduling that exploits channel fading to increase the system throughput. As future wireless networks will eventually support multimedia and data traffic together, we need a proper criterion for scheduling that can count various service requirements such as delay and packet loss. Although some previous approaches proposed opportunistic schedulers at the lower layer, it has not been investigated well whether they are able to meet explicit QoS defined at the upper layer. Hence, in this paper, we develop a hierarchical scheduling model that considers QoS provisioning and the time-varying channel feature separately. We focus on the upper-level QoS scheduling that supports various traffic classes in a unified manner. Supposing that a user gets some satisfaction or utility when served, we introduce a novel concept of opportunity cost, which is defined as the maximum utility loss among users incurred by serving a particular user at the current turn. We obtain each user’s net profit by subtracting the opportunity cost from its expected utility, and then select a user with the maximum profit for service. Simulation results reveal that our scheme supports various QoS classes well that are represented by delay and packet loss under various traffic loadings.     

Enhanced bulk scheduling for supporting delay sensitive streaming applications

Providing end-to-end delay guarantees for delay sensitive applications is an important packet scheduling issue with routers. In this paper, to support end-to-end delay requirements, we propose a novel network scheduling scheme, called the bulk scheduling scheme (BSS), which is built on top of existing schedulers of intermediate nodes without modifying transmission protocols on either the sender or receiver sides. By inserting special control packets, which called TED (Traffic Specification with End-to-end Deadline) packets, into packet flows at the ingress router periodically, the BSS schedulers of the intermediate nodes can dynamically allocate the necessary bandwidth to each flow to enforce the end-to-end delay, according to the information in the TED packets. The introduction of TED packets incurs less overhead than the per-packet marking approaches. Three flow bandwidth estimation methods are presented, and their performance properties are analyzed. BSS also provides a dropping policy for discarding late packets and a feedback mechanism for discovering and resolving bottlenecks. The simulation results show that BSS performs efficiently as expected.     

On using priced timed automata to achieve optimal scheduling

In this paper, we describe an approach for solving the general class of energy-optimal task graph scheduling problems using priced timed automata. We provide an efficient zone-based algorithm for minimum-cost reachability. Furthermore, we show how the simple structure of the linear programs encountered during symbolic minimum-cost reachability analysis of priced timed automata can be exploited in order to substantially improve the performance of the current algorithm. The idea is rooted in duality of linear programs and we show that each encountered linear program can be reduced to the dual problem of an instance of the min-cost flow problem. Experimental results using Uppaal show a 70–80 percent performance gain. We provide priced timed automata models for the scheduling problems and provide experimental results illustrating the potential competitiveness of our approach compared to existing approaches such as mixed integer linear programming.This research was conducted in part at Aalborg University, where the author was supported by a CISS Faculty Fellowship.

---

     

Answering constraint-based mining queries on itemsets using previous materialized results

In recent years, researchers have begun to study inductive databases, a new generation of databases for leveraging decision support applications. In this context, the user interacts with the DBMS using advanced, constraint-based languages for data mining where constraints have been specifically introduced to increase the relevance of the results and, at the same time, to reduce its volume. In this paper we study the problem of mining frequent itemsets using an inductive database. We propose a technique for query answering which consists in rewriting the query in terms of union and intersection of the result sets of other queries, previously executed and materialized. Unfortunately, the exploitation of past queries is not always applicable. We then present sufficient conditions for the optimization to apply and show that these conditions are strictly connected with the presence of functional dependencies between the attributes involved in the queries. We show some experiments on an initial prototype of an optimizer which demonstrates that this approach to query answering is viable and in many practical cases it drastically reduces the query execution time.     

一种支持实时业务QoS的跨层分组调度方案*

提出了一种基于HSDPA系统的跨层分组调度方案,以支持实时业务QoS要求.在调度过程中,按照业务类型和实时要求将其排入分组队列,引入实时吞吐量和信道信息估算调度概率,实现实时业务质量和系统整体性能之间的平衡.仿真结果表明,该方案在数据吞吐量、传输时延等方面具有更好的性能.     

Exploration of networks using overview+detail with constraint-based cooperative layout

A standard approach to large network visualization is to provide an overview of the network and a detailed view of a small component of the graph centred around a focal node. The user explores the network by changing the focal node in the detailed view or by changing the level of detail of a node or cluster. For scalability, fast force-based layout algorithms are used for the overview and the detailed view. However, using the same layout algorithm in both views is problematic since layout for the detailed view has different requirements to that in the overview. Here we present a model in which constrained graph layout algorithms are used for layout in the detailed view. This means the detailed view has high-quality layout including sophisticated edge routing and is customisable by the user who can add placement constraints on the layout. Scalability is still ensured since the slower layout techniques are only applied to the small subgraph shown in the detailed view. The main technical innovations are techniques to ensure that the overview and detailed view remain synchronized, and modifying constrained graph layout algorithms to support smooth, stable layout. The key innovation supporting stability are new dynamic graph layout algorithms that preserve the topology or structure of the network when the user changes the focus node or the level of detail by in situ semantic zooming. We have built a prototype tool and demonstrate its use in two application domains, UML class diagrams and biological networks.      

On multiprocessor task scheduling using efficient state space search approaches

Obtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A^* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable.     

Energy-aware scheduling and simulation methodologies for parallel security processors with multiple voltage domains

Dynamic voltage scaling (DVS) and power gating (PG) have become mainstream technologies for low-power optimization in recent years. One issue that remains to be solved is integrating these techniques in correlated domains operating with multiple voltages. This article addresses the problem of power-aware task scheduling on a scalable cryptographic processor that is designed as a heterogeneous and distributed system-on-a-chip, with the aim of effectively integrating DVS, PG, and the scheduling of resources in multiple voltage domains (MVD) to achieve low energy consumption. Our approach uses an analytic model as the basis for estimating the performance and energy requirements between different domains and addressing the scheduling issues for correlated resources in systems. We also present the results of performance and energy simulations from transaction-level models of our security processors in a variety of system configurations. The prototype experiments show that our proposed methods yield significant energy reductions. The proposed techniques will be useful for implementing DVS and PG in domains with multiple correlated resources.     

On the modelling and optimization of preferences in constraint-based temporal reasoning

In this paper, we consider both the modelling and optimization of preferences in problems of constraint-based temporal reasoning. The Disjunctive Temporal Problems with Preferences (DTPP) – a formulation that combines the rich expressive power of the Disjunctive Temporal Problem with the introduction of metric preference functions – is studied, and transformed into a corresponding constraint system that we name the Valued DTP (VDTP). We show that for a broad family of optimization criteria, the VDTP can express the same solution space as the DTPP, under the assumption of arbitrary piecewise-constant preference functions. We then generalize the powerful search strategies from decision-based DTP literature to accomplish the efficient optimization of temporal preferences. In contrast to the previous state-of-the-art system (which addresses the optimization of temporal preferences using a SAT formulation), we instead employ a meta-CSP search space that has traditionally been used to solve DTPs without preferences. Our approach supports a variety of objective functions (such as utilitarian optimality or maximin optimality) and can accommodate any compliant valuation structure. We also demonstrate that key pruning techniques commonly used for temporal satisfiability (particularly, the removal of subsumed variables and semantic branching) are naturally suited to prevent the exploration of redundant search nodes during optimization that may otherwise be encountered when resolving a typical VDTP derived from a DTPP. Finally, we present empirical results showing that an implementation of our approach consistently outperforms prior algorithms by orders of magnitude.     

On commutativity based Edge Lean search

The problem of state space search is fundamental to many areas of computer science, such as, e.g., AI and formal methods. Often, the state space to be searched is huge, so optimizing the search is an important issue. In this paper, we consider the problem of visiting all states in the setting where transitions between states are generated by actions, and the (reachable) states are not known in advance. Some of the actions may commute, i.e., they result in the same state for every order in which they are taken. We show how to use commutativity to achieve full coverage of the states, while traversing a relatively small number of edges.     

基于排队网络的多优先级MapReduce作业调度算法

MapReduce是一个能够对大规模数据进行分布式处理的框架,目前被各个领域广泛应用。在提供MapReduce服务的集群中,如何保证不同优先级用户的截止时间限定是MapReduce作业调度问题的一个挑战。针对这一问题,提出了一个基于排队网络的多优先级作业调度算法（MPSA）。首先分析和归纳了基于MapReduce模型的算法,提出了三种常见模式,采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型,应用该网络模型可以求出不同优先级队列对资源的需求;随后使用AR(1)模型进行预测,使算法可以动态地适应不同的用户访问量;利用二分查找算法,分步计算出不同优先级在map阶段和reduce阶段分配的槽位数;最后实现了在MapReduce模型中应用的实时调度算法。实验结果表明,与传统的FIFO和公平调度算法相比,本文提出的算法在用户到达率和任务规模变化的情况下,可以更加有效地满足不同优先级用户的截止时间限定。     

支持多类业务的移动Ad Hoc网络拓扑透明MAC调度码

设计了一类用于支持多种业务类型的移动自组织网络拓扑透明媒质接入控制(MAC)调度码。这类调度码保证最低优先级用户在一帧中至少有一个时隙成功传输信息的前提下,码长最小。这种调度码设计方案不仅简单易行,而且发送时隙选择灵活。性能分析表明,基于这类调度码的无线网络能够支持多个业务类型的用户,并为各类用户提供有保证的服务质量。