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

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

来源：评论

学校读者我要写书评

暂无评论

Using multicriteria analysis to develop environmental flow scenarios for rivers targeted for water resource management

引用

WATER SA 2003年第4期29卷 365-374页

作者： Brown, CA Joubert, A Univ Cape Town Dept Zool So Waters Ecol Res & Consulting CC ZA-7705 Mowbray South Africa Univ Cape Town Dept Stat Sci ZA-7701 Rondebosch South Africa

DRIFT is an interactive, holistic approach for advising on environmental flows for rivers, The DRIFT methodology, together with multicriteria analysis (MCA), can be used to provide flow scenarios and descriptive summaries of their consequences in terms of the condition of the river ecosystem, for examination and comparison by decision-makers. The essential features of DRIFT, the output of workshops where it is applied, and the development of the DRIFT database are described. Modules within the database include DRIFTSOLVER and DRIFTCATEGORY. DRIFTSOLVER contains an integer linear programming MCA method, which generates optimally distributed flow scenarios for different total annual volumes of water. DRIFT CATEGORY facilitates evaluation of these in terms of river condition. These two modules are explained in detail and illustrated with examples.

关键词： environmental flows interactive holistic approach DRIFT multicriteria analysis scenarios river condition integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Interactive R&D portfolio analysis with project interdependencies and time profiles of multiple objectives

引用

IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT 2003年第2期50卷 175-183页

作者： Stummer, C Heidenberger, K Univ Vienna Sch Business Econ & Comp Sci A-1210 Vienna Austria

This paper describes a three-phase approach to assist research and development managers in obtaining the most attractive project portfolio. The screening procedure of the first phase identifies project proposals that are worthy of further evaluation keeping the number of projects entering the subsequent phase within a manageable size. In the second phase, a multiobjective integer linear programming model determines the solution space of all efficient (i.e., Pareto-optimal) portfolios. It takes into account time profiles of the objectives, various project interdependencies, logical and strategic requirements, as well as resource and benefit constraints. The third phase, finally, aims to find a portfolio which fits the decision-maker's notions. Starting with an arbitrarily selected candidate he/she iteratively sets aspiration levels for objectives or modifies upper and lower bounds. Thus, the solution space is explored until a satisfying compromise between the figures both in benefit and resource categories is reached. Our approach is numerically tractable, and, as a key feature, requires no a priori assumptions about the decision-maker's preferences. Its application is illustrated by an example.

关键词： integer linear programming interactive decision support multiobjective decision-making portfolio analysis project interdependencies project selection research and development (R&D)

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of multirate time division multiplexed wavelength routed optical networks

引用

COMPUTER COMMUNICATIONS 2003年第14期26卷 1644-1650页

作者： Fenger, C Glenstrup, A Tech Univ Denmark Res Ctr COM DK-8000 Kongens Lyngby Denmark

We consider a wavelength routed all-optical mesh network, where the wavelengths are divided into individually routed timeslots to improve utilization and to allow for a higher degree of optical transparency. The multirate scheduling problem is defined mathematically by integer linear programming formulations. The equivalence of this problem to traditional wavelength routed optical networks is shown. An approximative analytical expression for the gain of using timeslots is derived and verified by simulation. We find that this type of network improves scalability and utilization of all-optical networks significantly when the typical size of a traffic demand corresponds to a couple of wavelengths or less. (C) 2003 Elsevier Science B.V. All rights reserved.

关键词： time slot wavelength routing all-optical integer linear programming

来源：评论

学校读者我要写书评

暂无评论

An integer multicommodity flow model applied to the rerostering of nurse schedules

引用

ANNALS OF OPERATIONS RESEARCH 2003年第1-4期119卷 285-301页

作者： Moz, M Pato, MV Univ Tecn Lisboa Inst Econ & Business Adm Dept Math P-1200781 Lisbon Portugal Univ Lisbon Fac Sci Ctr Operat Res P-1699 Lisbon Portugal

The problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities.

关键词： employee scheduling rerostering integer linear programming integer multicommodity flow problems

来源：评论

学校读者我要写书评

暂无评论

Solving integer programming by Evolutionary Soft Agent

引用

Wuhan University Journal of Natural Sciences 2003年第S1期8卷 283-286页

作者： Yin JianDepartment of Computer Science, Zhongshan University, Guangzhou 510275,Guangdong, ChinaState Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, Jiangsu, China Department of Computer Science Zhongshan University Guangzhou Guangdong China State Key Laboratory for Novel Software Technology Nanjing University Nanjing Jiangsu China

Many practical problems in commerce and industry involve finding the best way to allocate scarce resources a-mong competing activities. This paper focuses on the problem of integer programming, and describes an evolutionary soft a-gent model to solve it. In proposed model, agent is composed of three components: goal, environment and behavior. Experimental shows the model has the characters of parallel computing and goal driving.

关键词： agent integer linear programming duplication

来源：评论

学校读者我要写书评

暂无评论

Steiner tree construction based on congestion for the global routing problem 3

Steiner tree construction based on congestion for the global...

引用

3rd IEEE International Workshop on System-on-Chip for Real-Time Applications

作者： Behjat, L Vannelli, A Univ Calgary Dept Elect & Comp Engn Calgary AB Canada

ISBN: (纸本)076951944X

Global routing is an essential part of physical design, and has been traditionally formulated to minimize either an estimate of the total wirelength or the channel capacity of a circuit ignoring important issues such as congestion and number of bends. In this paper, a mathematical programming model that combines the wirelength minimization model and the channel capacity minimization model is presented. The combined model is also capable of incorporating different aspects of the global routing problem, such as via-count and congestion in two stages of the global routing problem: route construction and problem formulation. In addition, numerical enhancements have been proposed to increase the speed of the global routing formulation. Experiments on different benchmarks show that the new model builds a flexible and powerful technique that enhances the global routing solution compared to other mathematical programming techniques developed for global routing.

关键词： Channel capacity Circuits Design engineering integer linear programming Mathematical model Mathematical programming Minimization Physics computing Routing Very large scale integration

来源：评论

学校读者我要写书评

暂无评论

Energy-balanced task allocation for collaborative processing in networked embedded systems 03

Energy-balanced task allocation for collaborative processing...

引用

Association-for-Computing-Machinery SIGPLAN Conference on Languages Compilers and Tools for Embedded Systems (LCTES 03)

作者： Yu, Y Prasanna, VK Univ So Calif Dept EE Syst Los Angeles CA 90089 USA

ISBN: (纸本)9781581136470

In this paper, we study the problem of allocating a real-time application onto a set of homogeneous processing elements connected by a single-hop wireless network. A periodic application consisting of a set of communicating tasks is considered. Each element is equipped with discrete dynamic voltage scaling for exploring the energy-latency tradeoffs. The time and energy costs of both computation and communication activities are considered. The goal is to balance the energy dissipation of the elements during each period of the application with respect to the remaining energy of elements, such that the system lifetime is maximized. An integer linear programming (ILP) formulation is first developed, which can be solved to obtain the optimal solution. We then propose an efficient 3-phase heuristic. Experimental results show that for small scale problems, the performance of the heuristic achieves up to 85% of the system lifetime obtained by the ILP-based approach. For large scale problems, the performance of the heuristic shows an improvement of 120-250% in the system lifetime compared with the case where no voltage scaling is used. Further, we present two extensions of our approaches that consider multiple communication channels and techniques for exploring the energy-latency tradeoffs of the communication activities.

关键词： algorithms networked embedded systems energy-balanced task allocation integer linear programming

来源：评论

学校读者我要写书评

暂无评论

TESTLINE: An IEEE P1500 compatible test scheme for SoC test 5

TESTLINE: An IEEE P1500 compatible test scheme for SoC test

引用

5th International Conference on ASIC

作者： He, H Sun, YH Tsinghua Univ Inst Microelect Beijing 100084 Peoples R China

ISBN: (纸本)078037889X

An IEEE P1500 compatible test scheme. TESTLINE, for modular SoC testing is presented in this paper. The test scheme consists of wrappers, TAM and User Defined Controller (UDC). For a given SoC, with specified parameters of modules and their tests, TESTLINE can optimize the testing time for the whole SoC using integer linear programming (ILP). The ILP can efficiently determine the width of TAM and the assignment of modules to TAM. Experimental results for the 'ITC '02 SOC Test Benchmarks' show that TESTLINE is an effective and efficient test scheme for SoC testing.

关键词： integer programming linear programming system-on-chip IEEE standards integrated circuit testing IEEE P1500 compatible test SoC test system-on-chip test TESTLINE UDC user defined controller ILP integer linear programming TAM test access mechanism

来源：评论

学校读者我要写书评

暂无评论

Optimal code and data layout in embedded systems 16

Optimal code and data layout in embedded systems

引用

16th International Conference on VLSI Design/2nd International Conference on Embedded Systems Design

作者： Kumar, TSR Govindarajan, R Kumar, CPR Texas Instruments India Ltd Bangalore 560017 Karnataka India

ISBN: (纸本)0769518680

Efficient layout of code and data sections in various types/levels of memory in an embedded systems is very critical not only for achieving real-time performance, but also for reducing its cost and power consumption. In this paper we formulate the optimal code and data section layout problem as an integer linear programming (ILP) problem. The proposed formulation can handle: (i) on-chip and off-chip memory, (ii) multiple on-chip memory banks, (iii) single and dual ported on-chip RAMs, (iv) overlay of data sections, and (v) swapping of code and data (from/to external memory). Our experiments demonstrate that, for a moderately complex embedded system, the optimal results produced by our formulation took only a few minutes on a PC, and it matches, in terms of performance and on-chip memory size, with a hand-optimized code/data layout which took 1 man-month.

关键词： Application software Cost function Embedded system Energy consumption integer linear programming Memory architecture Random access memory Read-write memory Real time systems System-on-a-chip

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：