Abstract Scheduling is essentially a decision-making process that enables resource sharing among a number of activities by determining their execution order on the set of available resources. The emergence of distributed systems brought new challenges on scheduling in computer systems, including clusters, grids, and more recently clouds. On the other hand, the plethora of research makes it hard for both newcomers researchers to understand the relationship among different scheduling problems and strategies proposed in the literature, which hampers the identification of new and relevant research avenues. In this paper we introduce a classification of the scheduling problem in distributed systems by presenting a taxonomy that incorporates recent developments, especially those in cloud computing. We review the scheduling literature to corroborate the taxonomy and analyze the interest in different branches of the proposed taxonomy. Finally, we identify relevant future directions in scheduling for distributed systems.
@cite_75 present a taxonomy in the scheduling problem for workflows considering multiple criteria optimization in grid computing environments. The authors separate the multi-criteria scheduling taxonomy in @math , namely , and , each facet describing the problem from a different point of view. These facets are expanded to classify existing works in a smaller granularity, pointing out where current research can be expanded and the work in each facet.
@cite_75
1895859803
The workflow scheduling problem which is considered difficult on the Grid becomes even more challenging when multiple scheduling criteria are used for optimization. The existing approaches can address only certain variants of the multi-criteria workflow scheduling problem, usually considering up to two contradicting criteria being scheduled in some specific Grid environments. A comprehensive description of the problem can be an important step towards more general scheduling approaches. Based on the related work and on our own experience, we propose several novel taxonomies of the multi-criteria workflow scheduling problem, considering five facets which may have a major impact on the selection of an appropriate scheduling strategy: scheduling process, scheduling criteria, resource model, task model, and workflow model. We analyze different existing workflow scheduling approaches for the Grid, and classify them according to the proposed taxonomies, identifying the most common use cases and the areas which have not been sufficiently explored yet. To program in distributed computing environments such as grids and clouds, workflow is adopted as an attractive paradigm for its powerful ability in expressing a wide range of applications, including scientific computing, multi-tier Web, and big data processing applications. With the development of cloud technology and extensive deployment of cloud platform, the problem of workflow scheduling in cloud becomes an important research topic. The challenges of the problem lie in: NP-hard nature of task-resource mapping; diverse QoS requirements; on-demand resource provisioning; performance fluctuation and failure handling; hybrid resource scheduling; data storage and transmission optimization. Consequently, a number of studies, focusing on different aspects, emerged in the literature. In this paper, we firstly conduct taxonomy and comparative review on workflow scheduling algorithms. Then, we make a comprehensive survey of workflow scheduling in cloud environment in a problem---solution manner. Based on the analysis, we also highlight some research directions for future investigation. Workflow application can be executed in cloud computing environments in utility-based fashion. In our paper, we first give a survey of cloud workflow application and present the cloud-based workflow architecture for Smart City. Then a variety of workflow scheduling algorithms are reviewed. The purpose of this paper is to making taxonomy for workflow management and scheduling in cloud environment, and also applying this cloud-based workflow architecture to Smart City environments, further presenting several research challenges in this area. Over the last decade many techniques and tools for software clone detection have been proposed. In this paper, we provide a qualitative comparison and evaluation of the current state-of-the-art in clone detection techniques and tools, and organize the large amount of information into a coherent conceptual framework. We begin with background concepts, a generic clone detection process and an overall taxonomy of current techniques and tools. We then classify, compare and evaluate the techniques and tools in two different dimensions. First, we classify and compare approaches based on a number of facets, each of which has a set of (possibly overlapping) attributes. Second, we qualitatively evaluate the classified techniques and tools with respect to a taxonomy of editing scenarios designed to model the creation of Type-1, Type-2, Type-3 and Type-4 clones. Finally, we provide examples of how one might use the results of this study to choose the most appropriate clone detection tool or technique in the context of a particular set of goals and constraints. The primary contributions of this paper are: (1) a schema for classifying clone detection techniques and tools and a classification of current clone detectors based on this schema, and (2) a taxonomy of editing scenarios that produce different clone types and a qualitative evaluation of current clone detectors based on this taxonomy. Improving on the Voronoi cell based techniques of Micciancio and Voulgaris (SIAM J. Comp. 13), and Sommer, Feder and Shalvi (SIAM J. Disc. Math. 09), we give a Las Vegas @math expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the @math deterministic runtime of the Micciancio Voulgaris algorithm, henceforth MV, for CVPP (which also solves CVP) at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the @math path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest. We present a framework for the analysis and evaluation oftravel, or viewpoint motion control, techniques for use in immersive virtual environments (VEs). In previous work, we presented a taxonomy of travel techniques and a set of experiments mapping parts of the taxonomy to various performance metrics. Since these initial experiments, we have expanded the framework to allow evaluation of not only the effects of different travel techniques, but also the effects of many outside factors simultaneously. Combining this expanded framework with the measurement of multiple response variables epitomises the philosophy oftestbed evaluation. This experimental philosophy leads to a deeper understanding of the interaction and the technique(s) in question, as well as to broadly generalisable results. We also present an example experiment within this expanded framework, which evaluates the user's ability to gather information while travelling through a virtual environment. Results indicate that, of the variables tested, the complexity of the environment is by far the most important factor. Most software is accompanied by frequent changes, whereas the implementation of a single change can affect many different parts of the system. Approaches for Impact Analysis have been developed to assist developers with changing software. However, there is no solid framework for classifying and comparing such approaches, and it is therefore hard to find a suitable technique with minimal effort. The contribution of this paper is a taxonomy for Impact Analysis, based on a literature review conducted on related studies, to overcome this limitation. The presented classification criteria are more detailed and precise than those proposed in previous work, and possible candidates for all criteria are derived from studied literature. We classify several approaches according to our taxonomy to illustrate its applicability and the usefulness of our criteria. The research presented in this paper prepares the ground for a comprehensive survey of Software Change Impact Analysis. Cloud computing has emerged during the last decade to be widely adopted nowadays in several IT areas. It consists to propose market or not market-oriented resources as services that can be consumed in a ubiquitous, flexible and transparent way. In this paper, we deal with scheduling, one of the major cloud computing issue. According to the targeted cloud configuration, the addressed objectives and the accuracy of the view that one have of the cloud, we propose a taxonomy that identifies three levels of scheduling: service-level, task-level and Virtual Machine-level. We compare different cloud scheduling approaches from the literature and identify the common features and the differences between all the approaches according to each cloud scheduling level using different criteria. The reported results of the comparison show inter alia a weakness in the proposed schedulers, almost no Pareto multi-objective solving algorithms and very few realistic experiments facing the real cloud constraints. Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms has to be reconsidered by the influence of new execution supports (namely, clusters of workstations, grid computing and global computing) which are characterized by a larger number of heterogeneous processors, often organized by hierarchical sub-systems. Parallel Tasks model (tasks that require more than one processor for their execution) has been introduced about 15 years ago as a promising alternative for scheduling parallel applications, especially in the case of slow communication media. The basic idea is to consider the application at a rough level of granularity (larger tasks in order to decrease the relative weight of communications). As the main difficulty for scheduling in actual systems comes from handling efficiently the communications, this new view of the problem allows us to consider them implicitly, thus leading to more tractable problems. We kindly invite the reader to look at the chapter of Maciej Drozdowski (in this book) for a detailed presentation of various kinds of Parallel Tasks in a general context and the survey paper from Feitelsonsurvey for a discussion in the field of parallel processing. Even if the basic problem of scheduling Parallel Tasks remains NP-hard, some approximation algorithms can be designed. A lot of results have been derived recently for scheduling the different types of Parallel Tasks, namely, Rigid, Moldable or Malleable ones. We will distinguish Parallel Tasks inside the same application or between applications in a multi-user context. Various optimization criteria will be discussed. This chapter aims to present several approximation algorithms for scheduling moldable and malleable tasks with a special emphasis on new execution supports. This paper presents a methodology for classifying the literature of the Vehicle Routing Problem (VRP). VRP as a field of study and practice is defined quite broadly. It is considered to encompass all of the managerial, physical, geographical, and informational considerations as well as the theoretic disciplines impacting this ever emerging-field. Over its lifespan the VRP literature has become quite disjointed and disparate. Keeping track of its development has become difficult because its subject matter transcends several academic disciplines and professions that range from algorithm design to traffic management. Consequently, this paper defines VRP's domain in its entirety, accomplishes an all-encompassing taxonomy for the VRP literature, and delineates all of VRP's facets in a parsimonious and discriminating manner. Sample articles chosen for their disparity are classified to illustrate the descriptive power and parsimony of the taxonomy. Moreover, all previously published VRP taxonomies are shown to be relatively myopic; that is, they are subsumed by what is herein presented. Because the VRP literature encompasses esoteric and highly theoretical articles at one extremum and descriptions of actual applications at the other, the article sampling includes the entire range of the VRP literature. As online social networks expand their role beyond maintaining existing relationships, they may look to more faceted ratings to support the formation of new connections between their users. Our study focuses on one community employing faceted ratings, CouchSurfing.org, and combines data analysis of ratings, a large-scale survey, and in-depth interviews. In order to understand the ratings, we revisit the notions of friendship and trust and uncover an asymmetry: close friendship includes trust, but high levels of trust can be achieved without close friendship. To users, providing faceted ratings presents challenges, including differentiating and quantifying inherently subjective feelings such as friendship and trust, concern over a friend’s reaction to a rating, and knowledge of how ratings can affect others’ reputations. One consequence of these issues is the near absence of negative feedback, even though a small portion of actual experiences and privately held ratings are negative. We show how users take this into account when formulating and interpreting ratings, and discuss designs that could encourage more balanced feedback. Existing adaptive filtering systems learn user profiles based on users' relevance judgments on documents. In some cases, users have some prior knowledge about what features are important for a document to be relevant. For example, a Spanish speaker may only want news written in Spanish, and thus a relevant document should contain the feature "Language: Spanish"; a researcher working on HIV knows an article with the medical subject "Subject: AIDS" is very likely to be interesting to him her. Semi-structured documents with rich faceted metadata are increasingly prevalent over the Internet. Motivated by the commonly used faceted search interface in e-commerce, we study whether users' prior knowledge about faceted features could be exploited for filtering semi-structured documents. We envision two faceted feedback solicitation mechanisms, and propose a novel user profile learning algorithm that can incorporate user feedback on features. To evaluate the proposed work, we use two data sets from the TREC filtering track, and conduct a user study on Amazon Mechanical Turk. Our experimental results show that user feedback on faceted features is useful for filtering. The new user profile learning algorithm can effectively learn from user feedback on faceted features and performs better than several other methods adapted from the feature-based feedback techniques proposed for retrieval and text classification tasks in previous work. Recent advances in computational intelligent systems have focused on addressing complex problems related to the dynamicity of the environments. In increasing number of real world applications, data are presented as streams that may evolve over time and this is known by concept drift. Handling concept drift is becoming an attractive topic of research that concerns multidisciplinary domains such that machine learning, data mining, ubiquitous knowledge discovery, statistic decision theory, etc... Therefore, a rich body of the literature has been devoted to the study of methods and techniques for handling drifting data. However, this literature is fairly dispersed and it does not define guidelines for choosing an appropriate approach for a given application. Hence, the main objective of this survey is to present an ease understanding of the concept drift issues and related works, in order to help researchers from different disciplines to consider concept drift handling in their applications. This survey covers different facets of existing approaches, evokes discussion and helps readers to underline the sharp criteria that allow them to properly design their own approach. For this purpose, a new categorization of the existing state-of-the-art is presented with criticisms, future tendencies and not-yet-addressed challenges. Previous research has shown that faceted browsing is effective and enjoyable in searching and browsing large collections of data. In this work, we explore the efficacy of interactive visualization systems in supporting exploration and sensemaking within faceted datasets. To do this, we developed an interactive visualization system called FacetLens, which exposes trends and relationships within faceted datasets. FacetLens implements linear facets to enable users not only to identify trends but also to easily compare several trends simultaneously. Furthermore, it offers pivot operations to allow users to navigate the faceted dataset using relationships between items. We evaluate the utility of the system through a description of insights gained while experts used the system to explore the CHI publication repository as well as a database of funding grant data, and report a formative user study that identified usability issues. This paper extends traditional faceted search to support richer information discovery tasks over more complex data models. Our first extension adds exible, dynamic business intelligence aggregations to the faceted application, enabling users to gain insight into their data that is far richer than just knowing the quantities of documents belonging to each facet. We see this capability as a step toward bringing OLAP capabilities, traditionally supported by databases over relational data, to the domain of free-text queries over metadata-rich content. Our second extension shows how one can efficiently extend a faceted search engine to support correlated facets - a more complex information model in which the values associated with a document across multiple facets are not independent. We show that by reducing the problem to a recently solved tree-indexing scenario, data with correlated facets can be efficiently indexed and retrieved Scheduling theory has received a growing interest since its origins in the second half of the 20th century. Developed initially for the study of scheduling problems with a single objective, the theory has been recently extended to problems involving multiple criteria. However, this extension has still left a gap between the classical multi-criteria approaches and some real-life problems in which not all jobs contribute to the evaluation of each criterion. In this book, we close this gap by presenting and developing multi-agent scheduling models in which subsets of jobs sharing the same resources are evaluated by different criteria. Several scenarios are introduced, depending on the definition and the intersection structure of the job subsets. Complexity results, approximation schemes, heuristics and exact algorithms are discussed for single-machine and parallel-machine scheduling environments. Definitions and algorithms are illustrated with the help of examples and figures. Honeynet research has become more important as a way to overcome the limitations imposed by the use of individual honeypots. A honeynet can be defined as a network of honeypots following certain topology. Although there are at present many existing honeynet solutions, no taxonomies have been proposed in order to classify them. In this paper, we propose such taxonomy, identifying the main criteria used for its classification and applying the classification scheme to some of the existing honeynet solutions, in order to quickly get a clear outline of the honeynet architecture and gain insight of the honeynet technology. The analysis of the classification scheme of the taxonomy allows getting an overview of the advantages and disadvantages of each criterion value. We later use this analysis to explore the design space of honeynet solutions for the proposal of a future optimized honeynet solution. Faceted search is becoming a popular method to allow users to interactively search and navigate complex information spaces. A faceted search system presents users with key-value metadata that is used for query refinement. While popular in e-commerce and digital libraries, not much research has been conducted on which metadata to present to a user in order to improve the search experience. Nor are there repeatable benchmarks for evaluating a faceted search engine. This paper proposes the use of collaborative filtering and personalization to customize the search interface to each user's behavior. This paper also proposes a utility based framework to evaluate the faceted interface. In order to demonstrate these ideas and better understand personalized faceted search, several faceted search algorithms are proposed and evaluated using the novel evaluation methodology. In heterogeneous distributed environment, it is a great challenge to schedule multiple workflows submitted at different times. Particularly, scheduling of concurrent workflows with deadline and budget constraints makes the problem become more complex. Recent studies have proposed dynamic scheduling strategies for concurrent workflows which have limitations in inconsistent environments. Therefore, this paper presents a new dynamic scheduling algorithm for concurrent workflows. This algorithm proposes a uniform ranking that considers the time and costs for both workflows and workgroups to assign priorities for tasks. In the resource selection phase, it controls the resource selection range for each task based on an optimistic budget for the current task and selects resources for the current task according to a defined bi-factor. The experimental results show that our algorithm outperforms the existing algorithms in both consistent and inconsistent environments. The Semantic Web fosters novel applications targeting a more efficient and satisfying exploitation of the data available on the web, e.g. faceted browsing of linked open data. Large amounts and high diversity of knowledge in the Semantic Web pose the challenging question of appropriate relevance ranking for producing fine-grained and rich descriptions of the available data, e.g. to guide the user along most promising knowledge aspects. Existing methods for graph-based authority ranking lack support for fine-grained latent coherence between resources and predicates (i.e. support for link semantics in the linked data model). In this paper, we present TripleRank, a novel approach for faceted authority ranking in the context of RDF knowledge bases. TripleRank captures the additional latent semantics of Semantic Web data by means of statistical methods in order to produce richer descriptions of the available data. We model the Semantic Web by a 3-dimensional tensor that enables the seamless representation of arbitrary semantic links. For the analysis of that model, we apply the PARAFAC decomposition, which can be seen as a multi-modal counterpart to Web authority ranking with HITS. The result are groupings of resources and predicates that characterize their authority and navigational (hub) properties with respect to identified topics. We have applied TripleRank to multiple data sets from the linked open data community and gathered encouraging feedback in a user evaluation where TripleRank results have been exploited in a faceted browsing scenario.