323,097 research outputs found
Clustering methods for Mode S stations: Evaluation and perspectives
No full textGrouping of a set of Secondary Surveillance Radar (SSR) Mode S stations into functional entities called clusters has significant operational facets; it calls for a constrained optimization, an important significant constraint being the scarcity of Interrogation Identifier (II) codes. This clustering problem can be approached by two ways, i.e., integer programming methods and heuristic approaches. The definition of a general, usable decision support tool to build up and evaluate clustering strategies in any operational airspace, e.g. the one of a nation or, even more complicated, of a system such as the European one, is a very challenging task. This paper describes some steps toward this envisaged result proposing a mathematical formulation and a heuristic approach for the problem
A Simulation study on the impact of data replication policies in grid scheduling
No full textGrid computing is emerging as a new paradigm for solving large-scale problems and is becoming an established technology for providing transparent access to large-scale distributed computational resources. Resource allocation and application scheduling are two of the most important aspects of Grid computing. In general, a grid application also requires datasets that may not be available at the local computing site where the application has to be executed, and hence in this case the required data has to be fetched before running the application. Replication of data from primary repositories to other locations may improve the system performance, so as to reduce the frequency of remote data access. In this paper, we tackle with the local scheduling problem by means of a rectangle packing model combined with different policies for dataset replication, with the aim of maximizing the system efficiency of a local computing site. A simulation study is conducted to explore the impact these dataset policies on Grid scheduling by evaluating the performance of an on-line packing algorithm on different Grid scheduling scenarios
Location of differentiated waste collection centers with user cooperation: a bilevel optimization approach
No full textWe focus on the problem of locating differentiated waste collection centers: a municipal firm acts with the goal of locating and installing proper capacities to such facilities with the goal of defining a cooperative behaviour of the users of an urban area, possibly giving economic incentives to the latter in the case they decide to follow a predefined planning on waste recycling. The problem has a hierarchical structure and can be modeled as a bilevel program where the leader decision maker, i.e., the municipal firm, identifies which facilities should be opened along with their capacities minimizing the costs while the follower decision maker acts on behalf of the cooperating users in order to maximize the total utility deriving from delivering wastes to facilities. Besides the mathematical formulation of the problem, we propose a randomized-rounding based heuristic to cope with its solution. Experiments on synthetic instances and a comparison with a known algorithm in the literature are presented to assess the effectiveness of our proposal
A Fast metaheuristic for scheduling tasks with multiple modes
No full textWe consider the following multi-mode task scheduling problem. Given are a set of independent tasks, and a set of single unit dedicated renewable resources. At any time each resource can be used by a single task at most. Each task has to be executed without preemption in one out of its possible execution modes, where each mode identifies a subset of resources simultaneously required by the task for its execution. The aim of the problem is to find a mode assignment for each task, and a schedule of the tasks to be executed in the assigned modes, such that the total amount of resources requested by tasks in any time period does not exceed the resource availability, and the schedule length, i.e., the makespan, is minimized. From the complexity viewpoint this problem is NP-hard. Heuristic algorithms for scheduling tasks with multiple modes for the minimum schedule length criterion involve in general two distinct phases, task mode assignment and task scheduling. In this paper, we propose a novel two-phase approach metaheuristic based on strategic oscillation and on a randomized choice of the neighborhood of the local search to avoid being trapped in local optima. The proposed approach, that can be interpreted as a simplification of a previous work by the authors, is compared to two state-of-the-art algorithms
An Asymptotic worst case analysis of the effectiveness of the harmonic 3D-shelf algorithm for on-line 3D-strip packing
No full textIt is well known that shelf algorithms are used to pack items into strips. Harmonic shelf algorithms represent a particular subclass of these algorithms with which an asymptotic worst case analysis has been conducted on two-dimensional (2D) strip packing. In this paper, we consider the 3D-strip packing problem and analyse the effectiveness of the Harmonic 3D-shelf algorithm in terms of the ratio between the wasted volume inside the used portion of the strip and the total size of the latter, and we show that this algorithm is capable to pack items so that the asymptotic worst case value of this ratio comes arbitrarily close to 3/4. The results come from an extension of the 2D case
An Economic Model for Grid Scheduling
No full textGrid scheduling, that is, the allocation of distributed computational resources to user applications, is one of the most challenging and complex task in Grid computing. In this paper, we give a quantitative description of a tender/contract-net model. The performance of the proposed market-based approach is experimentally compared with a simple round-robin allocation protocol
A new approach for scheduling independent tasks with multiple modes
No full textHeuristic algorithms for scheduling tasks with multiple modes and minimizing the schedule length involve in general two distinct phases, task mode assignment and then task scheduling. We propose a novel approach where these two features are managed in an integrated mechanism with mode assignment embedded in scheduling. The problem is first reformulated as a special single-mode task scheduling problem, and then is modeled as a graph interval T -coloring. Finally, a tabu-like metaheuristic is proposed for this latter graph coloring problem, and the performance of our approach is compared to known multi-mode scheduling heuristics
Resource allocation in grid computing: an economic model
No full textGrid scheduling, that is, the allocation of distributed computational resources to user applications, is one of the most challenging and complex task in Grid computing. The problem of allocating resources in Grid scheduling requires the de£nition of a model that allows local and external schedulers to communicate in order to achieve an ef£cient management of the resources themselves. To this aim, some economic/market-based models have been introduced in the literature, where users, external schedulers, and local schedulers negotiate to optimize their objectives. In this paper, we propose a tender/contract-net model for Grid resource allocation, showing the interactions among the involved actors. The performance of the proposed market-based approach is experimentally compared with a round-robin allocation protocol
On the effectiveness of the harmonic shelf algorithm for on-line strip packing
No full textIn [J. Csirik, G.J.Woeginger, An on-line algorithm for multidimensional bin packing, Inform. Process. Lett. 63 (1997) 171–175] the authors study the asymptotic worst case ratio between the height of the strip needed to on-line pack a list of boxes by means of the Harmonic Shelf Algorithm and the height of the strip used by an optimal algorithm. In this note we analyze the effectiveness of the former algorithm in terms of the ratio between the unused area inside the strip and the total size of this strip, and we show that the Harmonic Shelf Algorithm is also capable of packing items so that the asymptotic worst case value of this ratio comes arbitrarily close to 1/2
An On-line algorithm for the rectangle packing problem with rejection
No full textIn this paper an on-line algorithmf or the Rectangle Packing Problemi s presented. The method is designed to be able to accept or reject incoming boxes to maximize efficiency. We provide a wide computational analysis showing the behavior of the proposed algorithmas well as a comparison with existing off-line heuristics
- …
