检索结果-内蒙古大学图书馆

Network modeling issues for Grid application scheduling

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2005年第2期16卷 145-162页

作者： Casanova, H Univ Calif San Diego Dept Comp Sci & Engn San Diego Supercomp Ctr La Jolla CA 92093 USA

the dominant trend in scientific computing today is the establishment of platforms that span multiple institutions to support applications at unprecedented scales. On most distributed computing platforms a requirement to achieve high performance is the careful scheduling of distributed application components onto the available resources. While scheduling has been an active area of research for many decades most of the platform models traditionally used in scheduling research, and in particular network models, break down for platforms spanning wide-area networks. In this paper we examine network modeling issues for large-scale platforms from the perspective of scheduling. the main challenge we address is the development of models that are sophisticated enough to be more realistic than those traditionally used in the field, but simple enough that they are still amenable to analysis. In particular, we discuss issues of bandwidth sharing and topology modeling. Also, while these models can be used to define and reason about realistic scheduling problems, we show that they also provide a good basis for fast simulation, which is the typical method to evaluate scheduling algorithms, as demonstrated in our implementation of the S(IM)G(RID) simulation framework.

关键词： Grid computing network modeling simulation scheduling

来源：评论

学校读者我要写书评

暂无评论

A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks

A genetic algorithm for hybrid flow-shop scheduling with mul...

引用

6th workshop models and algorithms for planning and scheduling problems

作者： Oguz, C Ercan, M Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China Singapore Polytech Sch Elect & Elect Engn S-139651 Singapore Singapore

the hybrid flow-shop scheduling problem with multiprocessor tasks finds its applications in real-time machine-vision systems among others. Motivated by this application and the computational complexity of the problem, we propose a genetic algorithm in this paper. We first describe the implementation details, which include a new crossover operator. We then perform a preliminary test to set the best values of the control parameters, namely the population size, crossover rate and mutation rate. Next, given these values, we carry out an extensive computational experiment to evaluate the performance of four versions of the proposed genetic algorithm in terms of the percentage deviation of the solution from the lower bound value. the results of the experiments demonstrate that the genetic algorithm performs the best when the new crossover operator is used along with the insertion mutation. this genetic algorithm also outperforms the tabu search algorithm proposed in the literature for the same problem.

关键词： multiprocessor task scheduling hybrid flow-shop genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Steady-state scheduling on heterogeneous clusters

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2005年第2期16卷 163-194页

作者： Beaumont, O Legrand, A Marchal, L Robert, Y CNRS LaBRI UMR 5800 Bordeaux France ENS Lyon INRIA CNRS UMR 5668LIP Lyon France

this paper considers steady-state scheduling techniques for heterogeneous systems, such as clusters and grids. the use of steady-state scheduling is advocated to solve a variety of important problems, which would be too difficult to tackle with the objective of makespan minimization. Several examples are given, namely master-slave tasking, mixed task and data parallelism, and pipelined macro-communications (scatter, broadcast, multicast). For each example, both the advantages and the limitations of the approach are discussed.

关键词： PRODUCTION scheduling BROADCASTING industry COMMUNICATION COMMUNICATIONS industries OPERATIONS research MAthEMATICAL programming

来源：评论

学校读者我要写书评

暂无评论

Problem difficulty for tabu search in job-shop scheduling

引用

ARTIFICIAL INTELLIGENCE 2003年第2期143卷 189-217页

作者： Watson, JP Beck, JC Howe, AE Whitley, LD Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： problem difficulty job-shop scheduling local search tabu search

来源：评论

学校读者我要写书评

暂无评论

models and algorithms for a staff scheduling problem

引用

MAthEMATICAL PROGRAMMING 2003年第1-3期98卷 445-476页

作者： Caprara, A Monaci, M Toth, P Univ Bologna Dipartimento Elettr Informat & Sistemist I-40136 Bologna Italy

We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. the main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. the first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. the second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. the proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months.

关键词： staff scheduling integer linear programming column generation branch-and-bound maximum flow heuristic algorithms computational results

来源：评论

学校读者我要写书评

暂无评论

algorithms and models for railway optimization

引用

8th International workshop on algorithms and Data Structures (WADS 2003)

作者： Wagner, D Univ Karlsruhe Dept Comp Sci Karlsruhe Germany

ISBN: (纸本)3540405453

Mobility is increasing in a way that calls for systematic traffic planning in a broad context. In Europe the railways are requested to play a central role in this development. Future developments and improvements of European railways will have an impact on people's lives and therefore on society in general. the problems arising in this context are large and highly complex. Here are many interesting and challenging algorithmic problems waiting to be studied. Research topics include the network design, line planning, time table generation, crew scheduling, rolling stock rostering, shunting, time table information and delay management, In this talk we present models and algorithmic methods for several of these problems. We will discuss the interplay between algorithmic aspects and practical issues like availability and quality of data. the focus will be on two topics from network design and time table information respectively where we have ongoing cooperation with railway companies. As an example from network design, we will consider a scenario where the effects of introducing new train stops in the existing railway network is studied. For time table information whose algorithmic core problem is the computation of shortest paths we discuss new algorithmic issues arising from the huge size of the underlying data.

关键词： scheduling

来源：评论

学校读者我要写书评

暂无评论

6th International workshop on Approximation algorithms for Combinatorial Optimization problems, APPROX 2003 and 7th International workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003

引用

6th International workshop on Approximation algorithms for Combinatorial Optimization problems, APPROX 2003 and 7th International workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003

ISBN: (纸本)3540407707

the proceedings contain 33 papers. the special focus in this conference is on Approximation, Randomization, and Combinatoria Optimization. the topics include: Improved linear time approximation algorithms for weighted matchings;an improved decomposition theorem for graphs excluding a fixed minor;approximation algorithms for channel allocation problems in broadcast networks;an FPTAS for quickest multicommodity flows with inflow-dependent transit times;approximating market equilibria;approximating the degree-bounded minimum diameter spanning tree problem;on the hardness of approximate multivariate integration;a 2-approximation algorithm for the soft-capacitated facility location problem;approximating rooted connectivity augmentation problems;effective routing and scheduling in adversarial queueing networks;an improved algorithm for approximating the radii of point sets;computational analogues of entropy;on extracting private randomness over a public channel;high degree vertices and eigenvalues in the preferential attachment graph;the satisfiability threshold for randomly generated binary constraint satisfaction problems;continuous-time quantum walks on the symmetric group;a gambling game arising in the analysis of adaptive randomized rounding;tight bounds for testing bipartiteness in general graphs;discrete quantum walks hit exponentially faster;faster algorithms for max cut and max CSP, with polynomial expected time for sparse instances and a nearly linear size 4-min-wise independent permutation family by finite geometries.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Effective routing and scheduling in adversarial queueing networks

引用

作者： Sethuraman, Jay Teo, Chung-Piaw IEOR Department Columbia University New YorkNY United States Department of Decision Sciences National University of Singapore Singapore

来源：评论

学校读者我要写书评

暂无评论

Constraint Model-based planning and scheduling with Multiple Resources and Complex Collaboration Schema 6

Constraint Model-based Planning and Scheduling with Multiple...

引用

6th International Conference on Artificial Intelligence planning Systems, AIPS 2002

作者： Guettier, C. Allo, B. Legendre, V. Poncet, J.-C. Strady-Lécubin, N. Xerox Palo Alto Research Center 3333 Coyote Hill Road Palo AltoCA94304 United States AXLOG Ingénierie 19-21 rue du 8 Mai 1945 Arcueil94110 France

ISBN: (纸本)1577351428

In many domains, planning and scheduling problems have been considered separately. this historical decomposition leads to sub-optimal solving methods as task scheduling and planning share important sub-problems. In fact, on practical examples, there is no reason to separate coordination of activities and synchronization tasks. Furthermore, resource usage is not only relevant for task scheduling problems, but is also strongly affected by planning decisions in real-world problems. this paper proposes a Constraint Model-Based approach to concurrently tackle planning and scheduling problems. We show how constraint-based formulations can take advantage of flow models widely investigated in the operation research community. Our approach extends this model classification in order to derive both timing constraint and resource consumption for each transition of the plan. therefore, scheduling constraints involving precedences, exclusive disjunctions, and resource capacity limit can be stated over the set of timing and resource variables. On aeronautic and spatial examples, we demonstrate how this approach enables problem-dependent specialization and increases planning and scheduling efficiency. Lastly, by using real-world problem experimentations, we show how the approach supports local/global trade-offs while designing solving methods. © 2002, American Association for Artificial Intelligence (***). All rights reserved.

关键词： Economic and social effects

来源：评论

学校读者我要写书评

暂无评论

Proceedings - 6th International workshop on Discrete Event Systems, WODES 2002

Proceedings - 6th International Workshop on Discrete Event S...

引用

6th International workshop on Discrete Event Systems, WODES 2002

ISBN: (纸本)0769516831

the proceedings contain 56 papers. the topics discussed include: from discrete event to hybrid systems;decentralized supervisory control: a new architecture with a dynamic decision fusion rule;decentralized control of discrete event systems with bounded or unbounded delay communication;computation of supremal sub-languages of supervisory control using coalgebra;a formal mapping of static information models into dynamic models for process planning and control purposes;a discrete-event systems approach to communication induced checkpointing;an assume-guarantee reasoning for hierarchical coordination of discrete event systems;transformation of the cyclic scheduling problem of a large class of FMS into the search of an optimized initial marking of a linearizable weighted t-system;and transformation of the cyclic scheduling problem of a large class of FMS into the search of an optimized initial marking of a linearizable weighted T-system.

关键词：

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：