On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials

LetS be a triangulation of andf(z) = z ^d +a _d–1 z ^d–1++a ₀, a complex polynomial. LetF be the piecewise linear approximation off determined byS. For certainS, we establish an upper bound on the complexity of an algorithm which finds zeros ofF. This bound is a polynomial in terms ofn, max{a _i } _i , and measures of the sizes of simplices inS.     

Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: the bottleneck lower bound

This paper studies minimizing the flow time of a cyclic schedule for repeated identical jobs, where one job is started/completed in each cycle, subject to the schedule achieving maximum throughput. We propose a branch and bound method for a single machine problem, and use this method to derive an improved lower bound for the multiple machine problem.     

Random linear programs with many variables and few constraints

We extend and simplify Smale's work on the expected number of pivots for a linear program with many variables and few constraints. Our analysis applies to new versions of the simplex algorithm and to new random distributions.     

An efficient genetic algorithm for the traveling salesman problem with precedence constraints

The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.     

Minimizing the number of machines for minimum length schedules

In this paper, we present a new objective function for scheduling on parallel machines: minimizing the number of machines for schedules of minimum length. We study its complexity and we prove the NP-completeness of this problem, even if there is no precedences or for unitary execution times. We propose several polynomial algorithms for various particular cases.     

Identification of special structure constraints in linear programs

In large LPs it may be that a major fraction of the constraints has a particularly simple form. Frequently this simple form may be exploited by either decomposition or implicit representation methods. In these cases, the effective size and computational difficulty are more closely related to the number of remaining nonspecial constraints than to the number of special constraints. A unified computational procedure is presented for mechanically identifying near maximal sets of special structure constraints for most of the kinds of special structures which have been identified thus far as being exploitable.     

An improved heuristic for one-machine scheduling with delays constraints

An improved heuristic is proposed for one-machine scheduling problem with delay constraints, thus an open problem raised by Wikumet al. is solved. The heuristic solves the corresponding unit-execution-time problem optimally.     

Scheduling linearly shortening jobs under precedence constraints

We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs.     

Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints

This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies exclusively on the decompostion of the solution space exploration. Four different parallel strategies are proposed and implemented on an asynchronous parallel machine under PVM: the master-slave model, with two different schemes for improved load balancing, and the single-program-multiple-data model, with single-token and multiple-token message passing schemes. The comparative analysis of these strategies shows that the tabu search approach for this problem is very suitable to the parallelization of the neighborhood search, with efficiency results almost always close to one for problems over a certain size.     

Minimizing total completion time for UET tasks with release time and outtree precedence constraints

Brucker et al. (Math Methods Oper Res 56: 407–412, 2003) have given an O(n ²)-time algorithm for the problems , outtree and , outtree . In this note, we show that their algorithm admits an O(n log n)-time implementation.     

A control parametrization algorithm for optimal control problems involving linear systems and linear 1

Computational schemes based on control parametrization techniques are known to be very efficient for solving optimal control problems. However, the convergence result is only available for the case in which the dynamic system is linear and without the terminal equality and inequality constraints. This paper is to improve this convergence result by allowing the presence of the linear terminal inequality. For illustration, an example arising in the study of optimally one-sided heating of a metal slab in a furnace is considered.     

周期线性微分方程解的一个关键性质

周期线性微分方程某解f(z)和f(z qω）的线性相关性是方程复振研究的起步关键,其中ω是方程系数的周期,q是某正整数。S.Bank和J.Langley于1992年证明了重要结果,但其优势条件有时不适用。本文提出“组合优势条件”产用其发展了这一结果,大大扩充了其适用性。     

Stability criteria for linear periodic impulsive Hamiltonian systems

In this paper we obtain stability criteria for linear periodic impulsive Hamiltonian systems. A Lyapunov type inequality is established. Our results improve also the ones previously obtained for systems without impulse effect.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

一类高阶周期系数线性微分方程解的性质

本文主要研究了一类高阶周期系数线性微分方程解的超级,e-型级,相关性等问题,并得到了e-型级与超级之间的一些关系,以及这两种级与系数的精确关系．本文是首次使用e-型级来估计方程解的增长性,这种估计比级,超级更为精确．     

Stability criteria for linear periodic Hamiltonian systems

In this paper, we obtain new stability criteria for linear periodic Hamiltonian systems. A Lyapunov type inequality is established. Our results improve the existing works in the literature.     

Systems of linear fuzzy constraints

Linear Fuzzy constraints are linear constraints where coefficients are fuzzy numbers. This paper demonstrates that two points of view can be considered to extend classical linear constraints: either tolerance constraints, or approximate (in)equality constraints can be obtained. Resolution of systems of linear fuzzy constraints is shown to be made easier by the use of fuzzy numbers analytically represented through a given type of membership function and three parameters. Solution methods are provided in the case of non fuzzy variables; as an illustration, some numerical examples are presented. The fuzzy variable case is also evoked.This paper is part of Purdue University Electrical Engineering technical report TR-EE 78-13.     

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.