A polynomial algorithm for one problem of guillotine cutting

We consider the problem of guillotine cutting a rectangular sheet into two rectangular pieces without rotations. The question is whether there exists a cutting pattern with given numbers of occurrences of both rectangular pieces. A polynomial time algorithm is described to construct the convex hull of solutions to this problem.     

Intercomparison of retrieval codes used for the analysis of high-resolution, ground-based FTIR measurements

A rigorous and systematic intercomparison of codes used for the retrieval of trace gas profiles from high-resolution ground-based solar absorption FTIR measurements is presented for the first time. Spectra were analyzed with the two widely used independent, retrieval codes: SFIT2 and PROFFIT9. Vertical profiles of O₃, HNO₃, HDO, and N₂O were derived from the same set of typical observed spectra. Analysis of O₃ was improved by using updated line parameters. It is shown that profiles and total column amounts are in excellent agreement, when similar constraints are applied, and that the resolution kernel matrices are also consistent. Owing to the limited altitude resolution of ground-based observations, the impact of the constraints on the solution is not negligible. It is shown that the results are also compatible for independently chosen constraints. Perspectives for refined constraints are discussed. It can be concluded that the error budget introduced by the radiative transfer code and the retrieval algorithm on total columns deduced from high-resolution ground-based solar FTIR spectra is below 1%.     

Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

一种改进的数字散斑相关方法用于检测人的口型变化

提出了一种基于数字散斑相关测量技术的口型变化检测技术,该技术以白光数字散斑相关测量方法为基础,根据实际应用的需要,引入重心算法并进行了改进,可以实时地检测人说话时的口型变化。通过实验表明,提出的方法是一种实用的、快速、高精度的口型变化测试方法,可为今后的唇语识别技术奠定基础。     

How to assess and report the performance of a stochastic algorithm on a benchmark problem: mean or best result on a number of runs?

Some authors claim that reporting the best result obtained by a stochastic algorithm in a number of runs is more meaningful than reporting some central statistic. In this short note, we analyze and refute the main argument brought in favor of this statement.     

Constraint incorporation in optimization

Numerical methods for solving constrained optimization problems need to incorporate the constraints in a manner that satisfies essentially competing interests; the incorporation needs to be simple enough that the solution method is tractable, yet complex enough to ensure the validity of the ultimate solution. We introduce a framework for constraint incorporation that identifies a minimal acceptable level of complexity and defines two basic types of constraint incorporation which (with combinations) cover nearly all popular numerical methods for constrained optimization, including trust region methods, penalty methods, barrier methods, penalty-multiplier methods, and sequential quadratic programming methods. The broad application of our framework relies on addition and chain rules for constraint incorporation which we develop here.     

Manufacturing cell formation using similarity coefficients and a parallel genetic TSP algorithm: Formulation and comparison

Many algorithms have been proposed to form manufacturing cells from component routings. However, many of these do not have the capability of solving large problems. We propose a procedure using similarity coefficients and a parallel genetic implementation of a TSP algorithm that is capable of solving large problems of up to 1000 parts and 1000 machines. In addition, we also compare our procedure with many existing procedures using nine well-known problems from the literature.

The results show that the proposed procedure compares well with the existing procedures and should be useful to practitioners and researchers.     

The effect of multiple optima on the simple GA run-time complexity

Genetic algorithms are stochastic search algorithms that have been applied to optimization problems. In this paper we analyze the run-time complexity of a genetic algorithm when we are interested in one of a set of distinguished solutions. One such case occurs when multiple optima exist. We define the worst case scenario and derive a probabilistic worst case bound on the number of iterations required to find one of these multiple solutions of interest.     

Optimisation of fault-tolerant fabric-cutting schedules using genetic algorithms and fuzzy set theory

In apparel industry, manufacturers developed standard allowed minutes (SAMs) databases on various manufacturing operations in order to facilitate better scheduling, while effective production schedules ensure smoothness of downstream operations. As apparel manufacturing environment is fuzzy and dynamic, rigid production schedules based on SAMs become futile in the presence of any uncertainty. In this paper, a fuzzification scheme is proposed to fuzzify the static standard time so as to incorporate some uncertainties, in terms of both job-specific and human related factors, into the fabric-cutting scheduling problem. A genetic optimisation procedure is also proposed to search for fault-tolerant schedules using genetic algorithms, such that makespan and scheduling uncertainties are minimised. Two sets of real production data were collected to validate the proposed method. Experimental results indicate that the genetically optimised fault-tolerant schedules not only improve the operation performance but also minimise the scheduling risks.