Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP-hard problem 1|r_j|L_max 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|r_j|L_max was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria L_max and C_max for complexity of O(n³logn) operations.     

Synthesis of multivariable,basically non-interacting systems with significant plant uncertainty

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 k_i¹(ω)?|τ_ii(jω)|?k_i²(ω), |τ_ij(jω)|?k_ij(ω), 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.     

Lower bounds for the smallest singular value

Let A = (a_ij) 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 g_ij ≡ a_i + a_j − [(a_i − a_j)² + (r_i + c_i)(r_j + c_j)]^1/2/2 with a_i ≡ |a_ii| and r_i,c_i are the i^th deleted absolute row sum and column sum of A, respectively. The result simplifies and improves that of Johnson and Szulc: σ_n ≥ min_i≠j σ_ij. (See [1].)     

Multi-criteria scheduling: an agent-based approach for expert knowledge integration

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|d _j |∑C _j ,L _max 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 P _m |d _j |∑U _j as well as more challenging multi-criteria scheduling problems, like P _m ||C _max,∑C _j and P _m |d _j |C _max,∑C _j ,∑U _j . The latter problems are evaluated with extensive simulations comparing the standard multi-criteria evolutionary algorithm NSGA-2 and the new agent-based model.     

A simplified approach for the design of basically non-interacting multiple-input-multiple-output systems using qft

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 = [T_ij]. In many practical applications the specifications are of the basically non-interacting (BNIA) type, i.e. a_ii(ω) < | T_ii(jω) | < b_ii(ω), | T_ij(jω) | < b_ij(ω), (i ≠ j) and b_ij(ω) < a_ii(ω) in a significant range of frequencies. In one QFT technique the design is based on expressing when the matrix of compensators G = diag(G_ii(s)), L_i = G_iiQ_ii, P^?1 = [1/Q_ij], D_ij 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(F_ii(s)), the effect of the disturbance acting on the main diagonal terms (i.e. D_ii) can be neglected. This observation saves some computational burden because satisfaction of specifications on the T_iis 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.     

Asynchronous deterministic rendezvous in graphs

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|²)$\mathrm{O}(D|L_{\min }{|}^2)$ when D   is known and O((D+|_Lmax|)³)$\mathrm{O}((D+\left|L_{\max }\right|{)}^3)$ if D   is unknown, where |_Lmin|$\left|L_{\min }\right|$ and |_Lmax|$\left|L_{\max }\right|$ 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|)$\mathrm{O}(n|L_{\min }|)$, if the size n   of the ring is known, and of cost O(n|_Lmax|)$\mathrm{O}(n|L_{\max }|)$, 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|)$\mathrm{O}(D|L_{\min }|)$ if the topology of the graph and the initial positions are known to agents.     

Approximation results for a bicriteria job scheduling problem on a single machine without preemption

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 pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine

The classical problem of scheduling theory that is NP-hard in the strong sense 1|r _j|L _max is considered. New properties of optimal schedules are found. A polynomially resolved case of the problem is selected, when the release times (r _j), the processing time (p _j), and due dates of completion of processing (d _j) of jobs satisfy the constraints d ₁ ≤ ... ≤ d _n and d ₁ ? r ₁ ? p ₁ ≥ ... ≥ d _n ? r _n ? p _n. An algorithm of run time O(n ³logn) finds Pareto-optimal sets of schedules according to the criteria L _max and C _max that contains no more than n variants.     

Optimal algorithms for the average-constrained maximum-sum segment problem

Given a real number sequence A=(a₁,a₂,…,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=−∞.     

基于改进的差别矩阵的快速属性约简算法

为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i相似文献   

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (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 L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ 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 ⁴ m) 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 region approach for computing relative neighbourhood graphs in the Lp metric

The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a setV={v ₁,v ₂, ...,v _n } of distinct points in atwo-dimensional space. The pointv _j is said to be arelative neighbour ofv _i ifd _p (v _i ,v _j )≤max{d _p (v _j ,v _k ),d _p (v _j ,v _k )} for allv _k ∈V, whered _p denotes the distance in theL _p metric, 1≤p≤∞. After dividing the space around the pointv _i into eight sectors (regions) of equal size, a closest point tov _i in some region is called anoctant (region, orgeographic) neighbour ofv _i. For anyL _p metric, a relative neighbour ofv _i is always an octant neighbour in some region atv _i. This gives a direct method for computing all relative neighbours, i.e. for establishing therelative neighbourhood graph ofV. For every pointv _i ofV, first search for the octant neighbours ofv _i in each region, and then for each octant neighbourv _j found check whether the pointv _j is also a relative neighbour ofv _i. In theL _p 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 θn ²) time. In theL ₁ 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). TheL ₁ (L _∞) algorithm is optimal within a constant factor.     

A Neural Algorithm for the Maximum Clique Problem: Analysis,Experiments, and Circuit Implementation

{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{d _i , d _j } , d _i 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 10n ² log ₂ 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.     

Fitting a least squares piecewise linear continuous curve in two dimensions

An optimal piecewise linear continuous fit to a given set of n data points D = {(x_i, y_i) : 1 ≤ i ≤ n} in two dimensions consists of a continuous curve defined by k linear segments {L₁, L₂,…,L_k} which minimizes a weighted least squares error function with weight w_i at (x_i, y_i), where k ≥ 1 is a given integer. A key difficulty here is the fact that the linear segment L_j, which approximates a subset of consecutive data points D_j ⊂ D in an optimal solution, is not necessarily an optimal fit in itself for the points D_j. 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 w_j of some data point (x_j, y_j) is split into the weights λw_j and (1 − λ)w_j, 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.     

Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates

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|r_j|∑C_j, 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|r_j|∑C_j 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.     

A note on “Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time”

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$1|\mathit{nmit}|{\sum }_j{\mathit{hE}}_j+{\sum }_j{\mathit{wT}}_j$. 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.     

Job scheduling to minimize expected weighted flowtime on uniform processors

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 μ₁μ₂μ_m. Job i incurs a holding cost at rate c_i per unit time while still in the system, where c₁c₂c_n. 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>(Σ_i^j−₁μ_i)/μ_j−j k−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 c_i. 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.     

PERFORMANCE FUNCTIONS AND SUBLEVEL SETS FOR FREQUENCY DOMAIN DESIGN OF SINGLE LOOP FEEDBACK CONTROL SYSTEMS WITH PLANT UNCERTAINTY

The frequency domain design of control systems involves the fitting of a designable complex function of frequency (e.g., loop transfer function, compensator transfer function) to specification derived constraints in the design space ℂ×ℝ. In the classical Bode approach and its recent modifications the designable function is the loop transfer function, the specifications lead to constraints on the magnitude of the loop transfer function and the constraints have circular cross-sections in ℂ. In more recent design procedures (e.g., H _∞ optimization or QFT) the specifications lead to more complex constraint surfaces in ℂ×ℝ and the design procedure must fit the designable function to these constraints. In this paper we develop explicit representations of some important ℂ×ℝ constraint surfaces encountered in the design of SISO control systems with both non-parametric (unstructured) and parametric plant uncertainty and study the characteristics of their frequency axis cross-sections or level sets: important information use in the fitting process. The results are presented in two systems of co-ordinates (i.e., designable functions): nominal closed loop transfer function T_o(jω) and and nominal open loop transfer function L_o(jω). While the results in T_o co-ordinates are more useful when using mathematical optimization (e.g., H _∞ optimization techniques), the results in L_o co-ordinates have significant advantages of insight and ease of graphical manipulation as demonstrated in QFT. The inclusion of results in both sets of co-ordinates increases their utility for workers in both areas and also reveals some links between these two different approaches. © 1997 by John Wiley & Sons, Ltd.     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,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 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<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.