作者：
Silva, CristóvãoKlement, NathalieCEMUC
Department of Mechanical Engineering University of Coimbra Rua Luís Reis Santos Coimbra 3030-788 Portugal LSIS CNR UMR 7296 (équipe INSM)
École Nationale Supérieur des Arts et Métiers. 8 boulevard Louis XIV – 59046 Lille Cedex France
In this paper a generic and modular decision support tool developed to solve different planning, assignment or scheduling problems is presented. The utilization of this tool is illustrated by solving a real world mult...
详细信息
Classical list scheduling is a very popular and efficient technique for scheduling jobs for parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost...
详细信息
Classical list scheduling is a very popular and efficient technique for scheduling jobs for parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units: each processor only has a local view of the work to execute. Thus, the scheduler is no longer greedy and standard performance guarantees are lost. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. We first present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load imbalance between the local lists. We obtain an equation giving the evolution of the potential by computing its expected decrease in one step of the schedule. Our main theorem shows how to solve such equations to bound the makespan. Then, we apply this method to several scheduling problems, namely, for unit independent tasks, for weighted independent tasks and for tasks with precedence constraints. More precisely, we prove that the time for scheduling a global workload W composed of independent unit tasks on m processors is equal to W/m plus an additional term proportional to log(2) W. We provide a lower bound which shows that this is optimal up to a constant. This result is extended to the case of weighted independent tasks. In the last setting, precedence task graphs, our analysis leads to an improvement on the bound of Arora et al. (Theory Comput. Syst. 34(2):115-144, 2001). We end with some experiments using a simulator. The distribution of the makespan is shown to fit existing probability laws. Moreover, the simulations give a better insight into the additive term whose value is shown to be around 3log(2) W confirming the precision of our analysis.
In the scheduling literature, the notion of machine non-availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays,...
详细信息
In the scheduling literature, the notion of machine non-availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator non-availability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling and other polynomial-time algorithms.
Maxima in R-d are found incrementally by maintaining a linked list and comparing new elements against the linked list. If the elements are independent and uniformly distributed in the unit square [0, 1](d), then, rega...
详细信息
Maxima in R-d are found incrementally by maintaining a linked list and comparing new elements against the linked list. If the elements are independent and uniformly distributed in the unit square [0, 1](d), then, regardless of how the list is manipulated by an adversary, the expected time is O(n log(d-2) n). This should be contrasted with the fact that the expected number of maxims grows as log(d-1) n, so no adversary can force an expected complexity of n log(d-1) n. Note that the expected complexity is O(n) for d = 2. Conversely, there are list-manipulating adversaries for which the given bound is attained. However, if we naively add maxima to the list without changing the order. then the expected number of element comparisons is n + o(n) for any d greater than or equal to 2. In the paper we also derive new tail bounds and moment inequalities for the number of maxima.
暂无评论