A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

We give a $(2+?)$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).     

Backward–forward algorithms for structured monotone inclusions in Hilbert spaces

In this paper, we study the backward–forward algorithm as a splitting method to solve structured monotone inclusions, and convex minimization problems in Hilbert spaces. It has a natural link with the forward–backward algorithm and has the same computational complexity, since it involves the same basic blocks, but organized differently. Surprisingly enough, this kind of iteration arises when studying the time discretization of the regularized Newton method for maximally monotone operators. First, we show that these two methods enjoy remarkable involutive relations, which go far beyond the evident inversion of the order in which the forward and backward steps are applied. Next, we establish several convergence properties for both methods, some of which were unknown even for the forward–backward algorithm. This brings further insight into this well-known scheme. Finally, we specialize our results to structured convex minimization problems, the gradient-projection algorithms, and give a numerical illustration of theoretical interest.     

Monte Carlo study of the universal area distribution of clusters in the honeycomb O（n） loop model

We investigate the area distribution of clusters (loops) in the honeycomb O(n) loop model by means of the worm algorithm with n = 0.5, 1, 1.5, and 2. At the critical point, the number of clusters, whose enclosed area is greater than A, is proportional to A-1 with a proportionality constant C. We confirm numerically that C is universal, and its value agrees well with the predictions based on the Coulomb gas method.     

Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem

Airline crew scheduling problem is a complex and difficult problem faced by all airline companies.To tackle this problem, it was often decomposed into two subproblems solved successively. First, the airline crew-pairing problem, which consists on finding a set of trips – called pairings – i.e. sequences of flights, starting and ending at a crew base, that cover all the flights planned for a given period of time. Secondly, the airline crew rostering problem, which consists on assigning the pairings found by solving the first subproblem, to the named airline crew members. For both problems, several rules and regulations must be respected and costs minimized.It is sure that this decomposition provides a convenient tool to handle the numerous and complex restrictions, but it lacks, however, of a global treatment of the problem. For this purpose, in this study we took the challenge of proposing a new way to solve both subproblems simultaneously. The proposed approach is based on a hybrid genetic algorithm. In fact, three heuristics are developed here to tackle the restriction rules within the GA’s process.     

Sorting Using Complete Subintervals and the Maximum Number of Runs in a Randomly Evolving Sequence

We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0’s, and then evolves by changing each 0 to 1, with the n changes done in random order. What is the maximal number of runs of 1’s? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order n ^1/2, and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1; there is also a second order term of order n ^1/3. We also treat some variations, including priority queues and sock-sorting. The proofs use methods originally developed for random graphs.     

A robust parameter design for multi-response problems

Most real world search and optimization problems naturally involve multiple responses. In this paper we investigate a multiple response problem within desirability function framework and try to determine values of input variables that achieve a target value for each response through three meta-heuristic algorithms such as genetic algorithm (GA), simulated annealing (SA) and tabu search (TS). Each algorithm has some parameters that need to be accurately calibrated to ensure the best performance. For this purpose, a robust calibration is applied to the parameters by means of Taguchi method. The computational results of these three algorithms are compared against each others. The superior performance of SA over TS and TS over GA is inferred from the obtained results in various situations.     

On the solutions of the equation AXB = C under Toeplitz‐like and Hankel matrices constraint

In this paper, we are mainly concerned with 2 types of constrained matrix equation problems of the form AXB=C, the least squares problem and the optimal approximation problem, and we consider several constraint matrices, such as general Toeplitz matrices, upper triangular Toeplitz matrices, lower triangular Toeplitz matrices, symmetric Toeplitz matrices, and Hankel matrices. In the first problem, owing to the special structure of the constraint matrix , we construct special algorithms; necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions. In the second problem, we use von Neumann alternating projection algorithm to obtain the solutions of problem. Then we give 2 numerical examples to demonstrate the effectiveness of the algorithms.     

New Exact Travelling Wave Solutions to Kundu Equation

Based on a first-order nonlinear ordinary differential equation with six-degree nonlinear term, we first present a new auxiliary equation expansion method and its algorithm. Being concise and straightforward, the method is applied to the Kundu equation. As a result, some new exact travelling wave solutions are obtained, which include bright and dark solitary wave solutions, triangular periodic wave solutions, and singular solutions. This algorithm can also be applied to other nonlinear evolution equations in mathematical physics.     

Modeling of one-dimensional smoldering of polyurethane in microgravity conditions

Results are presented from a model of forward smoldering combustion of polyurethane foam in microgravity. The transient one-dimensional numerical-model is based on that developed at the University of Texas at Austin. The conservation equations of energy, species, and mass in the porous solid and in the gas phases are numerically solved. The solid and the gas phases are not assumed to be in thermal or in chemical equilibrium. The chemical reactions modeled consist of foam oxidation and pyrolysis reactions, as well as char oxidation. The model has been modified to account for new polyurethane kinetics parameters and radial heat losses to the surrounding environment. The kinetics parameters are extracted from thermogravimetric analyses published in the literature and using Genetic Algorithms as the optimization technique. The model results are compared with previous tests of forward smoldering combustion in microgravity conducted aboard the NASA Space Shuttle. The model calculates well the propagation velocities and the overall smoldering characteristics. Direct comparison of the solution with the experimental temperature profiles shows that the model predicts well these profiles at high temperature, but not as well at lower temperatures. The effect of inlet gas velocity is examined, and the minimum airflow for ignition is identified. It is remarkable that this one-dimensional model with simplified kinetics is capable of predicting cases of smolder ignition but with no self-propagation away from the igniter region. The model is used for better understanding of the controlling mechanisms of smolder combustion for the purpose of fire safety, both in microgravity and normal gravity, and to extend the unique microgravity data to wider conditions avoiding the high cost of space-based experiments.