Estimating parameters of the synchronous twofold-stochastic flow of events

Consideration was given to estimation of the parameters of the synchronous twofold-stochastic flow of events which makes up a mathematical model of the information flow of demands circulating in the queuing systems and networks. Two variants were studied. For the first variant, the problem of optimal estimation of the parameters of a synchronous flow of events with a finite arbitrary number of states was solved. The second variant differs in that the event flow operates in the environment where part of events is lost during the so-called dead time. Consideration was given to a synchronous flow with two states. The problem of estimating the length of the dead time in the conditions of continued dead time was solved. The results of numerical estimation based on the simulation model of the synchronous flow were presented for both variants.     

The three-color and two-color Tantrix™ rotation puzzle problems are NP-complete via parsimonious reductions

Holzer and Holzer [M. Holzer, W. Holzer, Tantrix? rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] proved that the Tantrix? rotation puzzle problem with four colors is NP-complete, and they showed that the infinite variant of this problem is undecidable. In this paper, we study the three-color and two-color Tantrix? rotation puzzle problems (3-TRP and 2-TRP) and their variants. Restricting the number of allowed colors to three (respectively, to two) reduces the set of available Tantrix? tiles from 56 to 14 (respectively, to 8). We prove that 3-TRP and 2-TRP are NP-complete, which answers a question raised by Holzer and Holzer [M. Holzer, W. Holzer, Tantrix? rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] in the affirmative. Since our reductions are parsimonious, it follows that the problems Unique-3-TRP and Unique-2-TRP are DP-complete under randomized reductions. We also show that the another-solution problems associated with 4-TRP, 3-TRP, and 2-TRP are NP-complete. Finally, we prove that the infinite variants of 3-TRP and 2-TRP are undecidable.     

Cellular automaton-based algorithms for the dispersion of mobile wireless sensor networks

Due to the advent of sensor technology and its applications, mobile wireless sensor networks (MWSNs) have gained a significant amount of research interest. In a typical MWSN, sensors can move within the network. We develop a set of probabilistic and deterministic cellular automaton (CA)-based algorithms for motion planning problems in MWSNs. First, we consider a scenario where a group of sensors are deployed and they need to disperse in order to maximise the area covered by the network. In this variant of the problem we do not explicitly consider that the sensors should maintain the connectivity of the network while they move. Second, we consider a scenario where the sensors are initially randomly distributed and they need to disperse autonomously to both maximise the coverage of the network and maintain its connectivity. We carry out extensive simulations of both deterministic and randomised variants of the algorithms. For the first variant of the problem we compare our algorithms with one previous algorithm and find that our algorithm yields better network coverage than the earlier algorithm. We also find that probabilistic algorithms have better overall performance for the second variant. CA algorithms rely only on local information about the network and, hence, they can be used in practice for MWSN problems. On the other hand, locality of the algorithm implies that maintaining connectivity becomes a non-trivial problem.     

Optimal harmonic period assignment: complexity results and approximation algorithms

Harmonic periods have wide applicability in industrial real-time systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. As a result, all instances of a task are interfered by the same amount of workload. This property decreases the jitters that happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic and the task set is required to be feasible. We study two variants of this problem. In the first one, the objective is to maximize the system utilization, while in the second one, the goal is to minimize the total weighted sum of the periods. First, we assume that an interval is determined a priori for each task from which its period can be selected. We show that both variants of the problem are (at least) weakly NP-hard. This is shown by reducing the NP-complete number partitioning problem to the mentioned harmonic period assignment problems. Afterwards, we consider a variant of the second problem in which the periods are not restricted to a special interval. We present two approximation algorithms with polynomial-time complexity for this problem and show that the maximum relative error of these algorithms is bounded by a factor of 1.125. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.     

Online algorithms for scheduling two parallel machines with a single server

We consider an online scheduling problem on two identical parallel machines with a single server. Jobs arrive one by one and each job has to be loaded by the server before being processed on one of the machines, and unloaded immediately by the server after its processing. Both loading and unloading times are equal to one time unit. The goal is to minimize the makespan. For the variant of the problem involving both loading and unloading operations, we present an online algorithm with competitive ratio of 5/3. For the variant with loading operation only, we show that the competitive ratio of list scheduling is at least 8/5 and provide an improved online algorithm with competitive ratio of 11/7. Finally, we discuss the lower bounds for these problems. We show that both variants have a lower bound of 3/2. Furthermore, we show that the lower bound of the first variant is at least 8/5 if the online algorithm satisfies a certain constraint.     

HEART: Unrelated parallel machines problem with precedence constraints for task scheduling in cloud computing using heuristic and meta-heuristic algorithms

Cloud computing is becoming a profitable technology because of it offers cost-effective IT solutions globally. A well-designed task scheduling algorithm ensures the optimal utilization of clouds resources and reducing execution time dynamically. This research article deals with the task scheduling of inter-dependent subtasks on unrelated parallel computing machines in a cloud computing environment. This article considers two variants of the problem-based on two different objective function values. The first variant considers the minimization of the total completion time objective function while the second variant considers the minimization of the makespan objective function. Heuristic and meta-heuristic (HEART) based algorithms are proposed to solve the task scheduling problems. These algorithms utilize the property of list scheduling algorithm of unrelated parallel machine scheduling problem. A mixed integer linear programming (MILP) formulation has been provided for the two variants of the problem. The optimal solution is obtained by solving MILP formulation using A Mathematical Programming Language (AMPL) software. Extensive numerical experiments have been performed to evaluate the performance of proposed algorithms. The solutions obtained by the proposed algorithms are found to out-perform the existing algorithms. The proposed algorithms can be used by cloud computing service providers (CCSPs) for enhancing their resources utilization to reduce their operating cost.     

Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing

We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. We consider the case where the items have fixed orientation and the case where orthogonal rotations around all axes are allowed. For the unbounded 3D knapsack problem, we extend the recurrence formula proposed by [1] for the rectangular knapsack problem and present a dynamic programming algorithm that uses reduced raster points. We also consider a variant of the unbounded knapsack problem in which the cuts must be staged. For the 3D cutting stock problem and its variants in which the bins have different sizes (and the cuts must be staged), we present column generation-based algorithms. Modified versions of the algorithms for the 3D cutting stock problems with stages are then used to build algorithms for the 3D strip packing problem and its variants. The computational tests performed with the algorithms described in this paper indicate that they are useful to solve instances of moderate size.     

Vehicle routing problem with a heterogeneous fleet and time windows

In this paper, a problem variant of the vehicle routing problem with time windows is introduced to consider vehicle routing with a heterogeneous fleet, a limited number of vehicles and time windows. A method that extends an existing tabu search procedure to solve the problem is then proposed. To evaluate the performance of the proposed method, experiments are conducted on a large set of test cases, which comprises several benchmark problems from numerous problem variants of the vehicle routing problem with a heterogeneous fleet. It is observed that the proposed method can be used to give reasonably good results for these problem variants. In addition, some ideas are presented to advance the research in heuristics, such as fair reporting standards, publication of benchmark problems and executable routines developed for algorithmic comparison.     

Scale-space line curvature estimation for straight line and circle detection

A scale-space algorithm for estimating the local curvature of lines (edges or isolines) is presented. Two variants of edge curvature estimation based on differential invariants are suggested and compared. The first variant uses the edge curvature formula derived in the paper and the second is based on image preprocessing, which allows one to use the isoline curvature formula for edge curvature estimation. An analysis of scale selection needed to reach a desired accuracy is presented. Also, noise influence analysis has been performed. The application of curvature estimation to detection of straight lines and circles is suggested and implemented. Curvature information usage in parametric curve detection speeds up search algorithms and makes the results more stable.     

Discontinuous finite elements and godunov-type methods for the eulerian equations of gas dynamics

We investigate the numerical solution of typical problems in gas dynamics by discontinuous finite element methods, and compare the results with computations performed with variants of Godunov's conservative method.A one-dimensional shock wave problem with reflection, and a three-dimensional shock tube-type problem with convergent-divergent nozzle geometry are analyzed. For the one-dimensional problem we also present results obtained with a variant of Glimm's method. In one dimension, finite elements give valuable results, although they need a substantially larger computing time; in three space dimensions discontinuous elements appear to be too cumbersome, in the present form, to lend themselves to an efficient treatment of time-dependent shock wave problems.     

Enhanced simulated-annealing-based algorithms and their applications to process planning in reconfigurable manufacturing systems

Capabilities of enhanced simulated-annealing-based algorithms in solving process planning problems in reconfigurable manufacturing are investigated. The algorithms are enhanced by combining variants of the simulated annealing technique with other algorithm concepts such as (i) knowledge exploitation and (ii) parallelism. Four configurations of simulated annealing algorithms are devised and engaged to solve an instance of a process planning problem in reconfigurable manufacturing systems. These configurations include; a basic simulated annealing algorithm, a variant of the basic simulated annealing algorithm, a variant of the simulated annealing algorithm coupled with auxiliary knowledge and a variant of the simulated annealing algorithm implemented in a quasi-parallel architecture. Although differences in performances were observed, the implemented algorithms are capable of obtaining good solutions in reasonable time. Experimental results show that the performances of the variants of simulated annealing based algorithms are better in comparison to a basic simulated annealing algorithm. A computational analysis and comparison using ANOVA indicates that improvements towards a better optimal solution can be gained by implementing variants of the simulated annealing algorithm. In addition, little speed gains can be obtained by implementing variants of the simulated annealing algorithms that are coupled with other algorithmic concepts.     

Certified Reduced Basis Methods for Parametrized Elliptic Optimal Control Problems with Distributed Controls

In this paper, we consider the efficient and reliable solution of distributed optimal control problems governed by parametrized elliptic partial differential equations. The reduced basis method is used as a low-dimensional surrogate model to solve the optimal control problem. To this end, we introduce reduced basis spaces not only for the state and adjoint variable but also for the distributed control variable. We also propose two different error estimation procedures that provide rigorous bounds for the error in the optimal control and the associated cost functional. The reduced basis optimal control problem and associated a posteriori error bounds can be efficiently evaluated in an offline–online computational procedure, thus making our approach relevant in the many-query or real-time context. We compare our bounds with a previously proposed bound based on the Banach–Ne?as–Babu?ka theory and present numerical results for two model problems: a Graetz flow problem and a heat transfer problem. Finally, we also apply and test the performance of our newly proposed bound on a hyperthermia treatment planning problem.     

Comparison of deterministic and stochastic approaches to global optimization

In this paper, we compare two different approaches to nonconvex global optimization. The first one is a deterministic spatial Branch‐and‐Bound algorithm, whereas the second approach is a Quasi Monte Carlo (QMC) variant of a stochastic multi level single linkage (MLSL) algorithm. Both algorithms apply to problems in a very general form and are not dependent on problem structure. The test suite we chose is fairly extensive in scope, in that it includes constrained and unconstrained problems, continuous and mixed‐integer problems. The conclusion of the tests is that in general the QMC variant of the MLSL algorithm is generally faster, although in some instances the Branch‐and‐Bound algorithm outperforms it.     

A reclaimer scheduling problem arising in coal stockyard management

We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm.     

Self-adaptive learning based particle swarm optimization

Particle swarm optimization (PSO) is a population-based stochastic search technique for solving optimization problems over continuous space, which has been proven to be efficient and effective in wide applications in scientific and engineering domains. However, the universality of current PSO variants, i.e., their ability to achieve good performance on a variety of different fitness landscapes, is still unsatisfying. For many practical problems, where the fitness landscapes are usually unknown, employing a trial-and-error scheme to search for the most suitable PSO variant is computationally expensive. Therefore, it is necessary to develop a more adaptive and robust PSO version to provide users a black-box tool for various application problems. In this paper, we propose a self-adaptive learning based PSO (SLPSO) to make up the above demerits. SLPSO simultaneously adopts four PSO based search strategies. A probability model is used to describe the probability of a strategy being used to update a particle. The model is self-adaptively improved according to the strategies’ ability of generating better quality solutions in the past generations. In order to evaluate the performance of SLPSO, we compare it with eight state-of-the-art PSO variants on 26 numerical optimization problems with different characteristics such as uni-modality, multi-modality, rotation, ill-condition, mis-scale and noise. The experimental results clearly verify the advantages of SLPSO. Moreover, a practical engineering problem, the economic load dispatch problem of power systems (ELD), is used to further evaluate SLPSO. Compared with the previous effective ELD evolutionary algorithms, SLPSO can update the best solution records.     

Uniform convergence analysis of finite difference approximations for advection–reaction–diffusion problem on adaptive grids

A kind of singularly perturbed advection–reaction–diffusion problems with the exponential boundary layer are considered on an adaptive mesh. The existence, uniqueness and stability for the solution of the discrete problem are analysed with the maximum principle. The stability of the continuous problem is also considered. For the equidistribution problem composed by the difference scheme and equidistribution mesh equations, we establish a first-order ?-independent convergence rate for the numerical scheme defined on the equidistribution mesh and also an estimation for the accuracy of the solution computed on the final mesh generated by the adaptive algorithm. Numerical results are given to examine the validity of our theoretical analysis and the efficiency of the adaptive algorithm.     

Metaheuristic optimization for the Single-Item Dynamic Lot Sizing problem with returns and remanufacturing

The use of metaheuristics for solving the Single-Item Dynamic Lot Sizing problem with returns and remanufacturing has increasingly gained research interest. Recently, preliminary experiments with Particle Swarm Optimization revealed that population-based algorithms can be competitive with existing state-of-the-art approaches. In the current work, we thoroughly investigate the performance of a very popular population-based algorithm, namely Differential Evolution (DE), on the specific problem. The most promising variant of the algorithm is experimentally identified and properly modified to further enhance its performance. Also, necessary modifications in the formulation of the corresponding optimization problem are introduced. The algorithm is applied on an abundant test suite employed in previous studies. Its performance is analyzed and compared with a state-of-the-art approach as well as with a previously investigated metaheuristic algorithm. The results suggest that specific DE variants can be placed among the most efficient approaches, thereby enriching the available algorithmic artillery for tackling the specific type of problems.     

Parameter estimation of nonlinear, time-variant systems by the method of sensitivity functions

The applicability of sensitivity functions to parameter estimation of nonlinear, time variant systems was investigated. The method showed the ability to move the parameter vector toward the direction of optimality, but the nonlinearity of the system created problems of stability and rate of convergence of the algorithm. These problems were corrected by the introduction of artificial variable step sizes to improve the rate of convergence at start and to dampen the system near optimality. Thus modified, the method yielded a satisfactory solution of the estimation problem.     

The travelling salesman problem with time windows: Adapting algorithms from travel-time to makespan optimization

In combinatorial optimization it is not rare to find problems whose mathematical structure is nearly the same, differing only in some aspect related to the motivating application. For example, many problems in machine scheduling and vehicle routing have equivalent formulations and only differ with respect to the optimization objective, or particular constraints. Moreover, while some problems receive a lot of attention from the research community, their close relatives receive hardly any attention at all. Given two closely related problems, it is intuitive that it may be effective to adapt state-of-the-art algorithms—initially introduced for the well-studied problem variant—to the less-studied problem variant. In this paper we provide an example based on the travelling salesman problem with time windows that supports this intuition. In this context, the well-studied problem variant minimizes the travel time, while the less-studied problem variant minimizes the makespan. Indeed, the results show that the algorithms that we adapt from travel-time minimization to makespan minimization significantly outperform the existing state-of-the-art approaches for makespan minimization.     

Use of observers for the inversion of nonlinear maps

In this paper we deal with the problem of the inversion of nonlinear maps. The first contribution of the paper is the definition, in a formal framework, of some problems related to map inversion, which are already present in the literature, for instance in the robotics area and in observer theory. The second and the main contribution consists in the solution of such problems by means of observers, for which some structures are proposed, for the state estimation of a time-varying nonlinear system associated with the given map and reference trajectory.