For practical reasons, most scheduling problems are an abstraction of the real problem being solved. For example, when you plan your day, you schedule the activities which are critical;that is you schedule the activit...
详细信息
ISBN:
(纸本)3540292381
For practical reasons, most scheduling problems are an abstraction of the real problem being solved. For example, when you plan your day, you schedule the activities which are critical;that is you schedule the activities which are essential to the success of your day. So you may plan what time to leave the house to get to work, when to have meetings, how you share your vehicle with your spouse and so on. On the other hand, you probably do not consider the activities that are easy to arrange like brushing your teeth, going to the shops, making photocopies and other such tasks that can usually be accomplished whenever you have the time available. Scheduling all of these activities at once is often too complicated. Instead, a simpler schedule is produced by considering only the critical activities. However, if a schedule goes wrong, it is often because an activity turned out to be critical but was not scheduled. We typically learn which activities are critical by experience and create an abstract scheduling problem which includes all known critical activities. Instead of scheduling the non-critical activities we estimate their effects in the abstract scheduling problem. We are interested in automating this abstraction process for scheduling problems. In our approach, given a set of activities A to be scheduled1, we choose a subset of activities, critical(A), and create a simplified scheduling model which approximates the other activities non-critical(A) instead of scheduling them. We then search this abstract model for a good, if not optimal solution. A solution is a partial order schedule for activities in critical(A). this abstract solution is then extended to a solution the entire problem by inserting the remaining activities non-critical(A) into the schedule. While the approach reduces complexity by solving the problem in two stages it does so at a price. there is a risk that the good abstract solution will not produce a good solution to the entire problem. We know
When solving constraint Satisfaction Problems (CSPs), it is desirable to find multiple solutions, or to find solutions that are robust, allowing us to modify the values of variables without breaking the solution. Furt...
ISBN:
(纸本)3540232419
When solving constraint Satisfaction Problems (CSPs), it is desirable to find multiple solutions, or to find solutions that are robust, allowing us to modify the values of variables without breaking the solution. Furthermore, we would like to be able to represent these multiple solutions in a compact manner. We present a method for improving the performance of, and solutions returned by, stochastic local search using maximal independent sets1 of the constraint graph. Given an independent set, this information can be used to significantly speed up the process of solving a CSP by reducing the search space. the CSP is partitioned into two sets of variables I and [`(I)]\bar{I}, where I is a maximal independent set of the constraint graph. In this way, search is concentrated only on the variables of [`(I)]\bar{I}, reducing the search space by a factor exponential in the size of I. Also this technique can provide multiple solutions in a compact form with no extra cost, since if we find a set of valid domain values for each variable in I, every element of the Cartesian product of these sets is a solution to the CSP. We focus on exploiting this information in local search. this technique is limited to low-density graphs, since dense graphs are less likely to contain a large independent set. the resulting solutions are robust with respect to the variables in the independent set. We compare the technique with WalkSAT, as defined for CSPs by [2], on low-density random CSP instances generated according to model B, with16 variables, domain size 8, tightness 0.3 and density 0.1. the average CPU run-time for WalkSAT was 96.5 seconds, while the average for WalkSAT_IS was 0.36 seconds. Also, while WalkSAT returns one solution, the average number of solutions returned by WalkSAT_IS per instance was 47,536,305 solutions this is a dramatic improvement in performance, as well as in the number of solutions returned. this technique falls in the category of algorithms exploiting backdoor
Most earlier works in the area of wireless mesh network assume a single interface being equipped in each node. In this paper, we consider the next-generation wireless mesh networks in which each node may be equipped w...
详细信息
Most earlier works in the area of wireless mesh network assume a single interface being equipped in each node. In this paper, we consider the next-generation wireless mesh networks in which each node may be equipped with multiple radio interfaces, each capable of running in one of several modes, one of several channels, and each capable of supporting multiple modulations. For example, from off-the-shelf components, one can easily construct a mesh node with multiple IEEE 802.11a/b/g radio interfaces. Our goal is to address the resource planning and packet forwarding issues in such an environment. the proposed methodology is based on linear programming with network flow principles and radio channel access/interference models. Given a network topology, traffic requirements, and gateway capacities, we show how to allocate network interface cards and their channels to fully utilize channel bandwidths. the results can be used by a wireless Internet service provider to plan their networks under a hardware constraint so as to maximize their profits. To the best of our knowledge, this is the first work addressing resource planning in a wireless mesh network. Our numerical results show significant improvement in terms of aggregate network throughput with moderate network-layer fairness.
In this work we propose novel algorithms for storing and evaluating sparse grid functions, operating on regular (not spatially adaptive), yet potentially dimensionally adaptive grid types. Besides regular sparse grids...
详细信息
Target cost control of construction projects is an important part of project management, and it plays a crucial role on the benefit of construction projects. In this paper, the issue about target cost control on the e...
详细信息
Target cost control of construction projects is an important part of project management, and it plays a crucial role on the benefit of construction projects. In this paper, the issue about target cost control on the early stage of construction projects has been explored further. Firstly, this paper elaborates on determination principles and measurement methods of target cost of construction projects. Secondly, through the establishment of target cost programming model of construction projects and the use of simplex method on the linear programming, the established target cost programming model has been solved and the satisfied value of target cost control of construction projects has been determined based on final solution of the model. Finally, the application of method has been verified in practice. the purpose on target cost control of construction project has been achieved qualitatively and quantitatively. the effective control about target cost of construction projects on the early stage has been ensured.
In this paper, we study a nursing home staff schedule optimization problem under resident demand uncertainty. We formulate a two-stage stochastic binary program accordingly, with objective to minimize the total labor ...
详细信息
ISBN:
(数字)9781728169040
ISBN:
(纸本)9781728169057
In this paper, we study a nursing home staff schedule optimization problem under resident demand uncertainty. We formulate a two-stage stochastic binary program accordingly, with objective to minimize the total labor cost (linearly related to work time) incurred by both regular registered nurses (RRNs) and part-time nurses (PTNs). As a significant constraint, we balance RRNs' total amount of work time with residents' total service need for every considered shift. Besides, we restrict feasible shift schedules based on common scheduling practice. We conduct a series of computational experiments to validate the proposed model. We discuss our optimal solutions under different compositions of residents in terms of their disabilities. In addition, we compare the total labor costs and an RRN scheduling flexibility index withthe given optimal solution under different combinations of RRNs and PTNs. Our analysis offers an operational approach to set the minimum number of nurses on flexible shift schedules to cover uncertain the service needs while maintaining a minimum labor cost.
暂无评论