Consideration was given to the classical NP-hard problem 1|rj|Lmax of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|rj|Lmax was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria Lmax and Cmax for complexity of O(n3logn) operations. 相似文献
This paper presents a synthesis technique for basically non-interacting, time-invariant, linear, minimum-phase, multi-variable feedback control systems with significant plant uncertainty. The technique permits precise design to specifications in the frequency domain, of the form ki1(ω)?|τii(jω)|?ki2(ω), |τij(jω)|?kij(ω), i/n=j, to be satisfied over the range of plant parameter uncertainty, where T = [ταβ] is the matrix of transfer functions of the closed-loop system, and the k's are a priori specified. The specifications are achieved with loop transmission elements of minimum ‘bandwidth’.A computerized iteration scheme is developed. At each iteration the problem is one of designing separate, single input-output systems with parameter uncertainty. An exact synthesis technique exists for this problem. Two detailed examples are given: one, a rotating d.c. to a.c. converter, in which parameter uncertainty is by a factor of 10 (1000%) and the second with parameter uncertainty factors up to 100. 相似文献
Let A = (aij) be an n × n complex matrix. Suppose that G(A), the undirected graph of A, has no isolated vertex. Let E be the set of edges of G(A). We prove that the smallest singular value of A, σn, satisfies: σn ≥ min σij | (i, j) ∈ E, where gij ≡ ai + aj − [(ai − aj)2 + (ri + ci)(rj + cj)]1/2/2 with ai ≡ |aii| and ri,ci are the ith deleted absolute row sum and column sum of A, respectively. The result simplifies and improves that of Johnson and Szulc: σn ≥ mini≠jσij. (See [1].) 相似文献
In this work, we present an agent-based approach to multi-criteria combinatorial optimization. It allows to flexibly combine elementary heuristics that may be optimal for corresponding single-criterion problems. We optimize an instance of the scheduling problem 1|dj|∑Cj,Lmax and show that the modular building block architecture of our optimization model and the distribution of acting entities enables the easy integration of problem specific expert knowledge. We present a universal mutation operator for combinatorial problem encodings that allows to construct certain solution strategies, such as advantageous sorting or known optimal sequencing procedures. In this way, it becomes possible to derive more complex heuristics from atomic local heuristics that are known to solve fractions of the complete problem. We show that we can approximate both single-criterion problems such as Pm|dj|∑Uj as well as more challenging multi-criteria scheduling problems, like Pm||Cmax,∑Cj and Pm|dj|Cmax,∑Cj,∑Uj. The latter problems are evaluated with extensive simulations comparing the standard multi-criteria evolutionary algorithm NSGA-2 and the new agent-based model. 相似文献
Quantitative feedback theory (QFT) has presented techniques for the design of multiple-input-multiple-output (MIMO) linear time invariant (LTI) systems with structured parameter uncertainty in the plant P for the satisfaction of specifications on the closed loop transfer function matrix T = [Tij]. In many practical applications the specifications are of the basically non-interacting (BNIA) type, i.e. aii(ω) < | Tii(jω) | < bii(ω), | Tij(jω) | < bij(ω), (i ≠ j) and bij(ω) < aii(ω) in a significant range of frequencies. In one QFT technique the design is based on expressing when the matrix of compensators G = diag(Gii(s)), Li = GiiQii, P?1 = [1/Qij], Dij a disturbance due to plant interaction between the different system channels. It is shown in this paper that when the specifications are BNIA and F = diag(Fii(s)), the effect of the disturbance acting on the main diagonal terms (i.e. Dii) can be neglected. This observation saves some computational burden because satisfaction of specifications on the Tiis becomes a single-input-single-output (SISO) design problem instead of the more elaborated multiple-input-single-output (MISO) design problem which had to be designed originally. A detailed 2-input-2-output design example is presented illustrating the simpler approach, stressing the importance of considering the correlation between specifications in the design procedure. 相似文献
Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D in an infinite line, we show a rendezvous algorithm with cost O(D|Lmin|2) when D is known and O((D+|Lmax|)3) if D is unknown, where |Lmin| and |Lmax| are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O(n|Lmin|), if the size n of the ring is known, and of cost O(n|Lmax|), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O(D|Lmin|) if the topology of the graph and the initial positions are known to agents. 相似文献
We study the problem of minimizing the average weighted completion time on a single machine under the additional constraint that the sum of completion times does not exceed a given bound B(1|∑Cj?B|∑wjCj) for which we propose a (2,1)-approximation algorithm. We also address the problem 1|∑cjCj?B|∑wjCj for which we present a (2,2)-approximation algorithm. After showing that the problem of minimizing two different sums of weighted completion times is intractable, we present an algorithm which computes a (2(1+?),1) (respectively (2(1+?),2))-approximate Pareto curve for the problem 1‖(∑Cj,∑wjCj) (respectively 1‖(∑cjCj,∑wjCj)). 相似文献
The classical problem of scheduling theory that is NP-hard in the strong sense 1|rj|Lmax is considered. New properties of optimal schedules are found. A polynomially resolved case of the problem is selected, when the release times (rj), the processing time (pj), and due dates of completion of processing (dj) of jobs satisfy the constraints d1 ≤ ... ≤ dn and d1 ? r1 ? p1 ≥ ... ≥ dn ? rn ? pn. An algorithm of run time O(n3logn) finds Pareto-optimal sets of schedules according to the criteria Lmax and Cmax that contains no more than n variants. 相似文献
Given a real number sequence A=(a1,a2,…,an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A(i,j)=(ai,ai+1,…,aj) that maximizes ∑i?k?jak subject to . In this paper, we give an O(n)-time algorithm for the case where the average upper bound is ineffective, i.e., U=∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω(nlogn) even if the average lower bound is ineffective, i.e., L=−∞. 相似文献
Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σn and a pattern string P∈Σm, for each i=1,2,…,n−m+1 define Lp(i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with Lp distance is to compute Lp(i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L1 matching (pattern matching with an L1 distance) we show a reduction of the string matching with mismatches problem to the L1 matching problem and we present an algorithm that approximates the L1 matching up to a factor of 1+ε, which has an
O(\frac1e2nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|)
run time. Then, the L2 matching problem (pattern matching with an L2 distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L∞ matching up to a factor of 1+ε with a run time of
O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|)
. We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog 4m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric. 相似文献
The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a setV={v1,v2, ...,vn} of distinct points in atwo-dimensional space. The pointvj is said to be arelative neighbour ofvi ifdp(vi,vj)≤max{dp(vj,vk),dp(vj,vk)} for allvk∈V, wheredp denotes the distance in theLp metric, 1≤p≤∞. After dividing the space around the pointvi into eight sectors (regions) of equal size, a closest point tovi in some region is called anoctant (region, orgeographic) neighbour ofvi. For anyLp metric, a relative neighbour ofvi is always an octant neighbour in some region atvi. This gives a direct method for computing all relative neighbours, i.e. for establishing therelative neighbourhood graph ofV. For every pointvi ofV, first search for the octant neighbours ofvi in each region, and then for each octant neighbourvj found check whether the pointvj is also a relative neighbour ofvi. In theLp metric, 1<p<∞, the total number of octant neighbours is shown to be θ(n) for any set ofn points; hence, even a straightforward implementation of the above method runs in θn2) time. In theL1 andL∞ metrics the method can be refined to a θ(n logn+m) algorithm, wherem is the number of relative neighbours in the output,n-1≤m≤n(n-1). TheL1 (L∞) algorithm is optimal within a constant factor. 相似文献
{In this paper we design and analyze a neural approximation algorithm for the Maximum Clique problem. This algorithm, having
as input an arbitrary undirected graph G = \langle V, E\rangle , constructs a finite sequence of Hopfield networks such that the attractor of the last network in the sequence represents
a maximal clique of G .
We prove that D(G) ⋅ |E\rm c| , where D(G) = max {i,j}\notin E\min{di, dj} , di is the degree of the vertex i of G , and |E\rm c| denotes the cardinality of the set of edges in the complement graph, is an upper bound to the number of the networks in
the sequence.
Some experiments made on the second DIMACS benchmark and on random graphs show that:
1. The quality of the solutions found by the algorithm is satisfactory.
2. The theoretical upper bound D(G) ⋅ |E\rm c| is quite pessimistic.
For random graphs we propose an empirical formula that gives a better estimate of the number of networks in the sequence.
Moreover, thanks to the simplicity of the algorithm, we are able to design a uniform family of circuits of small size (\approx 10n2log 2 n ) that implements it. The circuit, which solves the problems for graphs of at most 32 vertices, has then been programmed
on FPGAs (Field Programmable Gate Arrays). An analysis in terms of size and time complexity is given.
Received November 10, 1998; revised December 2000. 相似文献
An optimal piecewise linear continuous fit to a given set of n data points D = {(xi, yi) : 1 ≤ i ≤ n} in two dimensions consists of a continuous curve defined by k linear segments {L1, L2,…,Lk} which minimizes a weighted least squares error function with weight wi at (xi, yi), where k ≥ 1 is a given integer. A key difficulty here is the fact that the linear segment Lj, which approximates a subset of consecutive data points Dj ⊂ D in an optimal solution, is not necessarily an optimal fit in itself for the points Dj. We solve the problem for the special case k = 2 by showing that an optimal solution essentially consists of two least squares linear regression lines in which the weight wj of some data point (xj, yj) is split into the weights λwj and (1 − λ)wj, 0 ≤ λ ≤ 1, for computations of these lines. This gives an algorithm of worst-case complexity O(n) for finding an optimal solution for the case k = 2. 相似文献
In this paper we consider the well-known single machine scheduling problem with release dates and minimization of the total job completion time. For solving this problem, denoted by 1|rj|∑Cj, we provide a new metaheuristic which is an extension of the so-called filtered beam search proposed by Ow and Morton [30]. This metaheuristic, referred to as a Genetic Recovering Beam Search (GRBS), takes advantages of a Genetic Local Search (GLS) algorithm and a Recovering Beam Search (RBS) in order to efficiently explore the solution space. In this paper we present the GRBS framework and its application to the 1|rj|∑Cj problem. Computational results show that it consistently yields optimal or near-optimal solutions and that it provides interesting results by comparison to GLS and RBS algorithms. Moreover, these results highlight that the proposed algorithm outperforms the state-of-the-art heuristics. 相似文献
In a recent paper by Valente “Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time”’, Computers & Industrial Engineering, 55, 663–675, 2008, several beam search approaches are compared on a large set of instances of the total weighted earliness-tardiness problem on single machine with jobs independent weights and no machine idle time. That problem is denoted 1|nmit|∑jhEj+∑jwTj. This note points out that the standard iterated dynasearch procedure applied to that problem outperforms all the literature heuristics. Based on these results and others obtained on similar problems, we conclude that dynasearch for its efficiency and simplicity, should be used as a benchmark for future heuristics on those types of single machine no idle time problems. 相似文献
We consider a sequencing problem in which there are n jobs to be processed nonpreemptively on m nonidentical processors. The processing time of the j-th processor is exponentially distributed with rate μj, where μ1μ2μm. Job i incurs a holding cost at rate ci per unit time while still in the system, where c1c2cn. We show that to minimize total expected holding costs (weighted flowtime), it is optimal to take the fastest (lowest indexed) available processor, say processor j, and assign job k to it if k>(Σij−1μi)/μj−jk−1. After each assignment the jobs are renumbered (so that job k+1 becomes job k, etc.), and the procedure is repeated with the next fastest available processor, etc. Note that the policy does not depend on the values of the holding costs ci. This result is a generalization of the result of Agrawala et al. (1984) for minimizing expected flowtime, i.e., minimizing total holding cost when the holding costs of all the jobs are the same. We give a simpler proof of the more general result. 相似文献
Let A=〈a1,a2,…,am〉 and B=〈b1,b2,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai1=bj1,ai2=bj2,…,ail=bjl〉, where i1<i2<?<il and j1<j2<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space. 相似文献