We consider the classical problem of scheduling parallel unrelated machines. Each job is to be processed by exactly one machine. Processing job j on machine i requires time Pij. The goal is to find a schedule that min...
详细信息
ISBN:
(纸本)9781581139600
We consider the classical problem of scheduling parallel unrelated machines. Each job is to be processed by exactly one machine. Processing job j on machine i requires time Pij. The goal is to find a schedule that minimizes the p norm. Previous work showed a 2-approximation algorithm for the problem with respect to the ∞ norm. For any fixed p norm the previously known approximation algorithm has a performance of θ(p). We provide a 2-approximation algorithm for any fixed p norm (p > 1). This algorithm uses convex programming relaxation. We also give a √2-approximation algorithm for the 2 norm. This algorithm relies on convex quadratic programming relaxation. To the best of our knowledge, this is the first time that general convex programming techniques (apart from SDPs and CQPs) are used in the area of scheduling. We show for any given p norm a PTAS for any fixed number of machines. We also consider the multidimensional generalization of the problem in which the jobs are d-dimensional. Here the goal is to minimize the p norm of the generalized load vector, which is a matrix where the rows represent the machines and the columns represent the jobs dimension. For this problem we give a (d+l)-approximation algorithm for any fixed p norm (P > 1). Copyright 2005 ACM.
The automatic detection of unreachable coverage goals and generation of tests for "corner-case" scenarios is crucial to make testing and simulation based verification more effective. In this paper we address...
详细信息
Software systems are usually designed and documented with the aid of visual modeling notations. Visual modeling notations keep evolving over the years in tandem with visual modeling tools, and the tight binding in bet...
详细信息
ISBN:
(纸本)9781581139648
Software systems are usually designed and documented with the aid of visual modeling notations. Visual modeling notations keep evolving over the years in tandem with visual modeling tools, and the tight binding in between impedes the exchanging of modeling assets, which causes a spatial isolation of the models. Another problem with legacy software models is that they are isolated temporally in the early phases of the software engineering life cycle without reaching out to the later phases. This paper presents an approach for breaking both spatial and temporal isolation of software models by marshaling and unmarshaling models using the Entity-Relationship (ER) model, thus providing a promising way for evolving model-driven software development. Copyright 2005 ACM.
We give a Natural Deduction formulation of an adaptation of Gödel's functional (Dialectica) interpretation to the extraction of (more) efficient programs from (classical) proofs. We adapt Jørgensen's...
详细信息
Automated program transformation holds promise for a variety of software life cycle endeavors, particularly where the size of legacy systems makes code analysis, re-engineering, and evolution difficult and expensive. ...
详细信息
This paper presents the lessons learnt from a Visual *** curriculum from Microsoft. The said curriculum by the global name of "Code Rules" was recently localized and called "Coding Mel". A pilot wa...
详细信息
To become proficient programmers, novices must develop the skills of writing, reading, debugging, and testing code. We believe that learning to write short pieces of code correctly the first time helps strengthen all ...
详细信息
ISBN:
(纸本)1581139977
To become proficient programmers, novices must develop the skills of writing, reading, debugging, and testing code. We believe that learning to write short pieces of code correctly the first time helps strengthen all of these skills. In this paper, we describe a type of exercise, called IRONCODE, that helps develop the code-once skill. We describe the exercise, the programming environment, its implementation, and our experiences using IRONCODE in a second semester programming class. Copyright 2005 ACM.
作者：
Bibac, IonutNortel Networks
Parc d' Activités de Magny Châteaufort les Jeunes Bois Châteaufort 78928 Yvelines Cedex 9 France
The UMTS Bearer Independent Core Network program introduced the 3 rd Generation Partnership Program Release 4 BICN architecture into the legacy UMTS TDM-switched network. BICN is the application of call server archite...
详细信息
The UMTS Bearer Independent Core Network program introduced the 3 rd Generation Partnership Program Release 4 BICN architecture into the legacy UMTS TDM-switched network. BICN is the application of call server architecture for voice and circuit switched data, enabling the provisioning of traditional circuit-switched services using a packet-switched transport network. Today's business climate has made it essential for service providers to develop a comprehensive networking strategy that means introduction of R4-BICN networks. The R4-BICN solution to the evolution of the Core Network in UMTS will enable operators to significantly reduce the capital and operational costs of delivering both traditional voice services and new multimedia services. To build the optical backbone, which can support the third generation (3G) packetized infrastructure, the operators could choose a fibre connection, or they could retain the benefits of a wireless connectivity by using a FSO - Free Space Optical link, the only wireless technology available that is capable of achieving data rates up to 2.4 Gbit/s. FSO offers viable alternatives for both core transmission networks and for replacing microwaves links in NodeB - RNC access networks. The paper and presentation aim to demonstrate the manner in which FSO products and networks are employed into R4-BICN design solutions.
The availability of commodity multiprocessors offers significant opportunities for addressing the increasing computational requirements of optimization applications. To leverage these potential benefits, it is importa...
详细信息
Concerns for concurrent systems are not always easy to modularize within single units using traditional programming languages. The concept of aspect orientation can be applied to allow a modular implementation of thes...
详细信息
Concerns for concurrent systems are not always easy to modularize within single units using traditional programming languages. The concept of aspect orientation can be applied to allow a modular implementation of these concerns. Existing programming languages has been extended with new language features to support aspect-orientation. The most dominant of these language extensions are AspectJ for the Java programming language. However, Java is not ideal for all types of applications, or there exists legacy systems that need to be maintained. This paper presents AspectAda a new language extension to Ada95 and an AspectAda weaver tool built with the Ada Semantic Interface Specifciation (ASIS). The AspectAda language provides powerful language elements to facilitate aspect oriented programming in domains where Ada's capabilities are of high interest and the AspectAda weaver tool demonstrates the AspectAda language in action. Copyright 2005 ACM.
暂无评论