Scheduling three chains on two parallel machines

We consider the problem of scheduling n tasks subject to chain-precedence constraints on two identical machines with the objective of minimizing the makespan. The problem is known to be strongly NP-hard. Here, we prove that it is binary NP-hard even with three chains. Furthermore, we characterize the complexity of this case by presenting a pseudopolynomial time algorithm and a fully polynomial time approximation scheme.     

A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints

This study concerns the domain of cyclic scheduling. More precisely we consider the cyclic job shop scheduling problem with linear constraints. The main characteristic of this problem is that the tasks of each job are cyclic and are subjected to linear precedence constraints. First we review some approaches in the field of cyclic scheduling and present the cyclic job shop scheduling problem definition, which has an open complexity. Then we present a general approach for solving it, based on the coupling of a genetic algorithm and a scheduler. This scheduler utilises a Petri-net modelling the linear precedence constraints between cyclic tasks. The goal of this genetic algorithm is to propose an order of priority for jobs on the machines, to be used by the scheduler for solving resource conflicts. Finally a benchmark and some preliminary results of this approach are presented.     

Transient resonance problems in the case of the series of short duration loads

The indicated in the title of this paper vibration problem concern the ferroconcrete slab – type industrial ceilings. The presence of unilateral constraints which my arise as a result of construction damages is taken into consideration. As an example, it is analysed a construction of a ceiling in shape of a rectangular slab supported on a regular net of columns and a non deformed solid, being a model of a machine, placed on the construction. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors

This paper investigates the computational complexity of preemptive and nonpreemptive scheduling of biprocessor tasks on dedicated processors in general and some of its special cases. We consider two criteria of optimality: the schedule length and sum of task completion times. In addition, we analyze the complexity of these problems when precedence constraints are involved. We show that in general all these problems are NP-hard in the strong sense.     

A new heuristic for the multi-mode resource investment problem

This paper considers the problem of minimizing resource investment required to execute the tasks in a project network by a given project due date. A project consists of non-pre-emptive tasks executed in a known and required precedence order. Each task is completed in one of its feasible modes, which may differ not only in task duration but also in consumption of renewable resources. A priority rule heuristic with polynomial computational complexity is presented for this computationally intractable problem. This heuristic simultaneously considers due date constraints and resource usage to select and schedule tasks with one decision rule. This differs from prior multi-mode priority rule scheduling heuristics that apply two consecutive decision rules to schedule tasks. Extensive computational testing indicates promising results.     

Crew rostering problem in a public transport company

In this paper, we present an applied study commissioned by Metro Bilbao on how to establish a more egalitarian annual allocation of work to drivers. Task allocation is mixed, with some tasks allocated on a rotating basis and others not. The model proposed is solved as a sequence of four types of integer programming problem. The solution obtained is quasi-optimal: all drivers carry out practically the same tasks over the full year. The main contribution of this paper is its method for combining semi-rotating allocation with a planning time frame divided into five periods of three different types with a workload distributed in a non uniform fashion over the days of the week, and with constraints agreed with employees to obtain an egalitarian solution. This method is being implemented at Metro Bilbao, and Eusko Tren has commissioned a study into a similar method by the authors.     

Route problem with constraints depending on a list of tasks

An additive route problem with preceding conditions is considered in which the cost function and the move constraints both depend on a list of tasks that have not been performed by the current time. The problem is solved by applying a dynamic programming method that takes into account both these factors and is implemented in the construction of a (generally) incomplete array of Bellman function values.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

The complexity of a cyclic scheduling problem with identical machines and precedence constraints

We consider a set T of tasks with unit processing times. Each of them must be executed infinitely often. A uniform constraint is defined between two tasks and induces a set of precedence constraints on their successive executions. We limit our study to a subset of uniform constraints corresponding to two hypotheses often verified in practice: Each execution of T must end by a special task f, and uniform constraints between executions from different iterations start from f. We have a fixed number of identical machines. The problem is to find a periodic schedule of T which maximizes the throughput. We prove that this problem is NP-hard and show that it is polynomial for two machines. We also present another nontrivial polynomial subcase which is a restriction of uniform precedence constraints.     

Complexity and algorithms for nonlinear optimization problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005.     

Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap

Coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has a constant exact length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(n?log?n).     

Symmetric LDPC codes and local testing

Coding theoretic and complexity theoretic considerations naturally lead to the question of generating symmetric, sparse, redundant linear systems. This paper provides a new way of construction with better parameters and new lower bounds.Low Density Parity Check (LDPC) codes are linear codes defined by short constraints (a property essential for local testing of a code). Some of the best (theoretically and practically) used codes are LDPC. Symmetric codes are those in which all coordinates “look the same,” namely there is some transitive group acting on the coordinates which preserves the code. Some of the most commonly used locally testable codes (especially in PCPs and other proof systems), including all “low-degree” codes, are symmetric. Requiring that a symmetric binary code of length n has large (linear or near-linear) distance seems to suggest a “con ict” between 1/rate and density (constraint length). In known constructions, if one is constant, then the other is almost the worst possible - n/poly(logn).Our main positive result simultaneously achieves symmetric low density, constant rate codes generated by a single constraint. We present an explicit construction of a symmetric and transitive binary code of length n, near-linear distance n/(log logn)², of constant rate and with constraints of length (logn)⁴. The construction is in the spirit of Tanner codes, namely the codewords are indexed by the edges of a sparse regular expander graph. The main novelty is in our construction of a transitive (non Abelian!) group acting on these edges which preserves the code. Our construction is one instantiation of a framework we call Cayley Codes developed here, that may be viewed as extending zig-zag product to symmetric codes.Our main negative result is that the parameters obtained above cannot be significantly improved, as long as the acting group is solvable (like the one we use). More specifically, we show that in constant rate and linear distance codes (aka “good” codes) invariant under solvable groups, the density (length of generating constraints) cannot go down to a constant, and is bounded below by (log^(Ω(?)) n)(an Ω(?) iterated logarithm) if the group has a derived series of length ?. This negative result precludes natural local tests with constantly many queries for such solvable “good” codes.     

On the complexity of project scheduling to minimize exposed time

We consider project scheduling where the project manager’s objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the problem identifying both polynomially solvable and NP-hard versions of the problem. The complexity of the problem is seen to be dependent on the nature of renewable resource constraints, precedence constraints, and the ability to crash activities in the project.     

A note on Pythagorean hodograph quartic spiral

By using the geometric constraints on the control polygon of a Pythagorean hodograph (PH) quartic curve, we propose a sufficient condition for this curve to have monotone curvature and provide the detailed proof. Based on the results, we discuss the construction of spiral PH quartic curves between two given points and formulate the transition curve of a G² contact between two circles with one circle inside another circle. In particular, we deduce an attainable range of the distance between the centers of the two circles and summarize the algorithm for implementation. Compared with the construction of a PH quintic curve, the complexity of the solution of the equation for obtaining the transition curves is reduced.     

Model Based Control of a Parallel Robot – A Comparison of Control Algorithms

In this contribution the control behavior of a special construction of a parallel robot, called multi-axes test facility, is investigated. After a brief discussion of the different tasks of the robot the construction of the robot is briefly presented. To solve the tasks, different control algorithms are derived based on model equations of different complexity of the robot. Depending on the task to be performed by the robot, the controllers compensate the kinematic and/or kinetic coupling of the degrees of freedom of the robot, stabilize the system and achieve the desired spatial motion of each degree of freedom as well as sufficient robustness with respect to parameter uncertainties and load variations. A few results obtained in computer simulations and laboratory experiments are presented and judged with respect to the quality of control, the closeness to reality of the computer simulations, and the amount of costs and work needed to realize the different solutions.     

On maximum length convolutional codes under a trellis complexity constraint

We look at convolutional codes with maximum possible code length for prescribed redundancy, conditioned on constraints on the free distance and on the bit-oriented trellis state complexity. Rate (n−1)/n codes have been studied to some extent in the literature, but more general rates have not been studied much. In this work we consider convolutional codes of rate (n−r)/n, r⩾1. Explicit construction techniques for free distance d_free=3 and 4 codes are described. For codes with r=2, an efficient exhaustive search algorithm is outlined. For the more general case with r⩾2, a heuristic approach is suggested. Several new codes were found for r=1 and in particular for r=2 and 3. Compared to previously known codes of similar free distance and complexity constraints, the new codes have either strictly higher rate, or the same rate but smaller low distance multiplicities.     

Optimization of Nonlinear Mechanical Systems under Constraints with the Particle Swarm Method

In recent years, stochastic optimization methods have gained increasing attention in parameter optimization of mechanical systems. Most popular techniques are Evolutionary Computation and the Simulating Annealing algorithm, which are applied more frequently to mechanical problems due to the increasing computing resources available now. Since theses methods do not require any gradient information, they are well suited for non‐smooth or discontinuous optimization tasks occurring in nonlinear multibody systems. In addition to these techniques, Kennedy and Eberhart [5] introduced the Particle Swarm Optimization method (PSO) based on the simulation of bird flocking. In this work, the efficiency of an extended PSO algorithm has been compared with an Evolutionary Strategy (ES) [6] and an Adapted Simulated Annealing method (ASA) [4]. In order to solve optimization tasks with both equality and inequality constraints the PSO algorithm has been extended by the Augmented Lagrangian Multiplier Method [2]. The proposed method shows often superior results and is quite simple to implement. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Scheduling groups of tasks with precedence constraints on three dedicated processors

We study the problem of scheduling groups of tasks with precedence constraints on three dedicated processors. Each task requires a specified set of processors. Up to three precedence constraints are considered among groups of tasks requiring the same set of processors. The objective of the problem is to find a nonpreemptive schedule which minimizes the maximum completion time (makespan). This scheduling problem is equivalent to the problem of finding an extension of the constraint graph (i.e. the graph which represents the conflicts between tasks and the precedence constraints) to a comparability graph with minimum (over all the extensions) maximum clique weight. The problem is NP-hard in the strong sense. A normal schedule is such that all the tasks requiring the same set of processors are scheduled consecutively. With a normal schedule the problem reduces to the quotient graph of the constraint graph. In this paper we obtain tight approximation results for the minimum makespan of a normal schedule through tight results on the minimum increase of the maximum clique weight when the (partially oriented) quotient graph is extended to a comparability graph.     

大规模严格凸二次规划问题一个新算法

根据广义乘子法的思想,将具有等式约束和非负约束的凸二次规划问题转化只有非负约束的简单凸二次规划,通过简单凸二次规划来得到解等式约束一非负约束的凸二次规划新算法,新算法不用求逆矩阵,这样可充分保持矩阵的稀疏性,用来解大规模稀疏问题,数值结果表明：在微机４８６／３３上就能解较大规模的凸二次规划。     

Scheduling multiprocessor tasks with chain constraints

This paper is concerned with a new model in deterministic scheduling theory, where certain tasks may require more than one processor at a time. This model is motivated by several applications of multimicroprocessor systems and it has received much attention in the last years. In the paper it is assumed that each task can be processed on any processor subset of a given task-dependent size. Tasks are nonpreemptable and there are precedence constraints among them. It is proved that the problem of minimizing schedule length is NP-hard for three processors even if all the tasks have unit processing times and precedence constraints form a set of chains. Thus, it is unlikely to be solvable in polynomial time. On the other hand, two low order polynomial-time algorithms are given for the m processor case if processor requirements of the tasks in each chain are either uniform or monotonically decreasing (increasing).