There are no efficient algorithms for almost of all scheduling problems, especially when practical scheduling models are considered. Further there may be none for multiobjective scheduling problems. So we should take ...
详细信息
There are no efficient algorithms for almost of all scheduling problems, especially when practical scheduling models are considered. Further there may be none for multiobjective scheduling problems. So we should take efforts to develope efficient approximate algorithms for multi-objective scheduling problems. The main purpose of this paper is to survey approaches to some scheduling problems from the algorithmic view points till now and investigate some hopeful approximate approaches to multiobjective scheduling problems.
In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makes...
详细信息
In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in Jansen et al. [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints. Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.]: "Does there exist a polynomial time heuristic with worst-case guarantee better than 5/3 for the problem U2Chain?". The new approximation algorithm is also applied to the problem J2\pmtn\C-max. (C) 1998 Elsevier Science Ltd. All rights reserved.
Given a set N of n terminals in the first quadrant of the Euclidean plane E-2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertic...
详细信息
Given a set N of n terminals in the first quadrant of the Euclidean plane E-2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called rectilinear Steiner arborescence problem, which has been proved to be NP-complete recently (Shi and Su, 11th ACM-SIAM Symposium on Discrete algorithms (SODA), January 2000, to appear). In this paper, we present a polynomial time approximation scheme for this problem.
In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)\ . \C-max, where the numbers m(1) and m(2) of machines available in the two stages are part of the input. We demonstrate the...
详细信息
In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)\ . \C-max, where the numbers m(1) and m(2) of machines available in the two stages are part of the input. We demonstrate the existence of a polynomial time approximation scheme for this problem. This result solves the simplest case of an open problem that has been posed by Leslie Hall in a recent paper (Hall, 1995). hn extension of our algorithm yields an approximation scheme for the closely related two-stage multiprocessor job shop problem. (C) 2000 Elsevier Science B.V. All rights reserved.
We present a new polynomial time approximation scheme (PTAS) for tree alignment, which is an important variant of multiple sequence alignment. As in the existing PTASs in the literature, the basic approach of our algo...
详细信息
We present a new polynomial time approximation scheme (PTAS) for tree alignment, which is an important variant of multiple sequence alignment. As in the existing PTASs in the literature, the basic approach of our algorithm is to partition the given tree into overlapping components of a constant size and then apply local optimization on each such component. But the new algorithm uses a clever partitioning strategy and achieves a better efficiency for the same performance ratio. For example, to achieve approximation ratios 1.6 and 1.5, the best existing PTAS has to spend time O(kdn(5)) and O(kdn(9)), respectively, where n is the length of each leaf sequence and d, k are the depth and number of leaves of the tree, while the new PTAS only has to spend time O(kdn(4)) and O(kdn(5)). Moreover, the performance of the PTAS is more sensitive to the size of the components, which basically determines the running time, and we obtain an improved approximation ratio for each size. Some experiments of the algorithm on simulated and real data are also given.
This paper addresses the performance of list scheduling a cyclic set of N non-preemptive dependent generic tasks on m identical processors. The reduced precedence graph is assumed to be strongly connected but the numb...
详细信息
This paper addresses the performance of list scheduling a cyclic set of N non-preemptive dependent generic tasks on m identical processors. The reduced precedence graph is assumed to be strongly connected but the number of simultaneously active instances of a generic task is not restricted to be at most one. Some properties on arbitrary schedules are first given. Then, we restrict to regular schedules for which it is shown that the number of ready or active tasks at any instant is at least the minimum height H* of a directed circuit of the reduced precedence graph. The average cycle time of any regular list schedule is then shown to be at most (2 - (min{H*, m}/m)) times the absolute minimum average cycle time. This result, which is similar well-known (2 - (1/m)) Graham's bound applying for non-cyclic scheduling, shows to what extent regular list schedules take the: parallelism of the cyclic task system into account. (C) 2000 Elsevier Science B.V. All rights reserved.
The feedback vertex set problem for hypergraphs is considered and an efficient approximation algorithm is presented. It is shown that an approximation factor of k is guaranteed when the cardinality of every hyperedge ...
详细信息
The feedback vertex set problem for hypergraphs is considered and an efficient approximation algorithm is presented. It is shown that an approximation factor of k is guaranteed when the cardinality of every hyperedge is bounded by an integer k, generalizing the existing result for ordinary graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one pro...
详细信息
Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.
A typical approach to estimate an unknown quantity mu is to design an experiment that produces a random variable Z distributed in [0, 1] with E[Z] = mu, run this experiment independently a number of times, and use the...
详细信息
A typical approach to estimate an unknown quantity mu is to design an experiment that produces a random variable Z distributed in [0, 1] with E[Z] = mu, run this experiment independently a number of times, and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [ 0, 1]. We describe an approximation algorithm AA which, given and, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+epsilon of mu with probability at least 1-delta. We prove that the expected number of experiments run by AA (which depends on Z) is optimal to within a constant factor for every Z.
The World Wide Web provides access to vast amounts of information, but content providers are considering charging for the information and services they supply. Thus the consumer may face the problem of balancing the b...
详细信息
The World Wide Web provides access to vast amounts of information, but content providers are considering charging for the information and services they supply. Thus the consumer may face the problem of balancing the benefit of asking for information against the cost (in terms of both money and time) of acquiring it. We study information-gathering strategies that maximize the expected value to the consumer. In our model there is a single information request, which has a known benefit to the consumer. To satisfy the request, queries can be sent simultaneously or in sequence to any of a finite set of independent information sources. For each source we know the monetary cost of making the query, the amount of time it will take, and the probability that the source will be able to provide the requested information. A policy specifies which sources to contact at which times, and the expected value of the policy can be defined as some function of the likelihood that the policy will yield an answer, the expected benefit, and the monetary cost and time delay associated with executing the policy. The problem is to nd an expected-value-maximizing policy. We explore four variants of the objective function V: (i) V consists only of the benefit term subject to threshold constraints on both total cost and total elapsed time, (ii) V is linear in the expected total cost of the policy subject to the constraint that the total elapsed time never exceeds some deadline, (iii) V is linear in the expected total elapsed time subject to the constraint that the total cost never exceeds some threshold, and (iv) V is linear in the expected total monetary cost and the expected time delay of the policy. The problems of devising an optimal querying policy for all four variants and approximating an optimal querying policy for variants (iii) and (iv) are shown to be NP-hard. For (i), and with a mild simplifying assumption for (iii), we give a fully polynomial time approximation scheme. For (ii), we c
暂无评论