Search

In the label printing problem (LPP), a set of labels must be printed in specified quantities, using n templates to be defined. Each template can accommodate a fixed number of printing plates. The LPP consists of determining: (1) an n-partition of the labels, where each block defines the labels that share a template, (2) for each label the number of identical printing plates to place in one of the n templates, and (3) the number of imprints to make with each template. The objective is to satisfy the labels' demand while minimising total waste. Since the LPP is NP-Hard, to solve it, we propose here an Iterated Local Search heuristic that, once tested on all the instances available to us, it improved many of the best known results or find the optimum, when it is known. [ABSTRACT FROM AUTHOR]

Featured Application: This research allows tracing optimized routes in corridors of long lengths and is applied to the installation of pipelines that transport valuable liquids, which can be oil or petroleum. Planning corridors for new facilities such as pipeline or transmission lines through geographical spaces is a topographical constraint optimization problem. The corridor planning problem requires finding an optimal route or a set of alternative paths between two locations. This article presents a simulated-annealing-based (SA) approach applying a variable neighborhood strategy in a continuous space to generate competitive and different alternative paths to solve the corridor planning problem. The variable neighborhood method randomly selects two points from a variable interval of the current solution generated by SA creating pseudo-random paths inside a corridor and finding spatially different alternatives. The proposed approach is evaluated with three practical problems using real topographic data from the Veracruz Basin in Mexico. The experimental results show that this approach obtains efficient and competitive solutions with improvements above 18% over those gotten by the compared method. [ABSTRACT FROM AUTHOR]

Featured Application: An uncorrelated instance is equivalent to solving any problem where the benefit is independent of the weight. A weakly correlated instance has a high correlation between the benefit and the weight of each element. Typically, the benefit differs from the weight by a small percentage. Such instances are the most practical in administration, such as with a return on an investment, which is generally proportional to the sum of the amount invested. This paper presents a process that is based on sets of parts, where elements are fixed and removed to form different binary branch-and-bound (BB) trees, which in turn are used to build a parallel algorithm called "multi-BB". These sequential and parallel algorithms calculate the exact solution for the 0–1 knapsack problem. The sequential algorithm solves the instances published by other researchers (and the proposals by Pisinger) to solve the not-so-complex (uncorrelated) class and some problems of the medium-complex (weakly correlated) class. The parallel algorithm solves the problems that cannot be solved with the sequential algorithm of the weakly correlated class in a cluster of multicore processors. The multi-branch-and-bound algorithms obtained parallel efficiencies of approximately 75%, but in some cases, it was possible to obtain a superlinear speedup. [ABSTRACT FROM AUTHOR]

Featured Application: This research allows working collaboratively between different institutions through a grid computing infrastructure, sharing supercomputing equipment to be able to find good solutions in a more efficient way to problems intractable that are of real application as the Vehicle Routing Problem. This paper describes one grid-based genetic algorithm approach to solve the vehicle routing problem with time windows in one experimental cluster MiniGrid. Clusters used in this approach are located in two Mexican cities (Cuernavaca and Jiutepec, Morelos) securely communicating with each other since they are configured as one virtual private network, and its use as a single set of processors instead of isolated groups allows one to increase the computing power to solve complex tasks. The genetic algorithm splits the population of candidate solutions in several segments, which are simultaneously mutated in each process generated by the MiniGrid. These mutated segments are used to build a new population combining the results produced by each process. In this paper, the MiniGrid configuration scheme is described, and both the communication latency and the speedup behavior are discussed. Experimental results show one information exchange reduction through the MiniGrid clusters as well as an improved behavior of the evolutionary algorithm. A statistical analysis of these results suggests that our approach is better as a combinatorial optimization procedure as compared with other methods. [ABSTRACT FROM AUTHOR]

Featured Application: This research allows improving the schedule of jobs in manufacturing workshops and this increases the amount of products without having the need to increase the production machines. This paper presents a parallel algorithm applied to the job shop scheduling problem (JSSP). The algorithm generates a set of threads, which work in parallel. Each generated thread, executes a procedure of simulated annealing which obtains one solution for the problem. Each solution is directed towards the best solution found by the system at the present, through a procedure called effective-address. The cooperative algorithm evaluates the makespan for various benchmarks of different sizes, small, medium, and large. A statistical analysis of the results of the algorithm is presented and a comparison of performance with other (sequential, parallel, and distributed processing) algorithms that are found in the literature is presented. The obtained results show that the cooperation of threads carried out by means of effective-address procedure permits to simulated annealing to work with increased efficacy and efficiency for problems of JSSP. [ABSTRACT FROM AUTHOR]

This paper presents a simulated annealing algorithm accelerated by a partial scheduling mechanism and a cooling schedule mechanism that is a function of the standard deviation. This facilitates a rapid approach to good solutions in the flexible job shop scheduling problem (FJSSP). The results demonstrate that for benchmark instances of several sizes, simulated annealing that implements the proposed mechanism converges more quickly to good solutions than simulated annealing that does not implement the proposed mechanism. [ABSTRACT FROM AUTHOR]

This paper proposes a real mathematical constraint satisfaction model which defines the timetabling problem in the Faculty of Chemical Sciences and Engineering (FCSE) at the Autonomous University of Morelos State, Mexico. A Constructive Approach Algorithm (CAA) is used to obtain solutions in the proposed model. A comparison is made between the CAA’s results and the schedule generated by the FCSE administration. Using the constraint satisfaction model, it is possible to improve the allocation of class hours in the FCSE so that classroom use is more efficient. [ABSTRACT FROM AUTHOR]

A stochastic algorithm for obtaining feasible initial populations to the Vehicle Routing Problem with Time Windows is presented. The theoretical formulation for the Vehicle Routing Problem with Time Windows is explained. The proposed method is primarily divided into a clustering algorithm and a two-phase algorithm. The first step is the application of a modified k-means clustering algorithm which is proposed in this paper. The two-phase algorithm evaluates a partial solution to transform it into a feasible individual. The two-phase algorithm consists of a hybridization of four kinds of insertions which interact randomly to obtain feasible individuals. It has been proven that different kinds of insertions impact the diversity among individuals in initial populations, which is crucial for population-based algorithm behavior. A modification to the Hamming distance method is applied to the populations generated for the Vehicle Routing Problem with Time Windows to evaluate their diversity. Experimental tests were performed based on the Solomon benchmarking. Experimental results show that the proposed method facilitates generation of highly diverse populations, which vary according to the type and distribution of the instances. [ABSTRACT FROM AUTHOR]

This paper presents a neighbourhood generation mechanism for the job shop scheduling problems (JSSPs). In order to obtain a feasible neighbour with the generation mechanism, it is only necessary to generate a permutation of an adjacent pair of operations in a scheduling of the JSSP. If there is no slack time between the adjacent pair of operations that is permuted, then it is proven, through theory and experimentation, that the new neighbour (schedule) generated is feasible. It is demonstrated that the neighbourhood generation mechanism is very efficient and effective in a simulated annealing. [ABSTRACT FROM PUBLISHER]

This paper presents a methodological scheme to obtain the maximum benefit in occupational health by attending to psychosocial risk factors in a company. This scheme is based on selecting an optimal subset of psychosocial risk factors, considering the departments' budget in a company as problem constraints. This methodology can be summarized in three steps: First, psychosocial risk factors in the company are identified and weighted, applying several instruments recommended by business regulations. Next, a mathematical model is built using the identified psychosocial risk factors information and the company budget for risk factors attention. This model represents the psychosocial risk optimization problem as a Multidimensional Knapsack Problem (MKP). Finally, since Multidimensional Knapsack Problem is NP-hard, one simulated annealing algorithm is applied to find a near-optimal subset of factors maximizing the psychosocial risk care level. This subset is according to the budgets assigned for each of the company's departments. The proposed methodology is detailed using a case of study, and thirty instances of the Multidimensional Knapsack Problem are tested, and the results are interpreted under psychosocial risk problems to evaluate the simulated annealing algorithm's performance (efficiency and efficacy) in solving these optimization problems. This evaluation shows that the proposed methodology can be used for the attention of psychosocial risk factors in real companies' cases. [ABSTRACT FROM AUTHOR]

Paper waste in the mockups design with regular, irregular, and amorphous patterns is a critical problem in digital printing presses. Paper waste reduction directly impacts production costs, generating business and environmental benefits. This problem can be mapped to the two-dimensional irregular bin-packing problem. In this paper, an iterated local search algorithm using a novel neighborhood structure to detect overlaps between amorphous shapes is introduced. This algorithm is used to solve the paper waste problem, modeled as one 2D irregular bin-packing problem. The experimental results show that this approach works efficiently and effectively to detect and correct the overlaps between regular, irregular, and amorphous figures. [ABSTRACT FROM AUTHOR]

This work presents an optimization proposal to better the computational convergence time in convection-diffusion and driven-cavity problems by applying a simulated annealing (SA) metaheuristic, obtaining optimal values in relaxation factors (RF) that optimize the problem convergence during its numerical execution. These relaxation factors are tested in numerical models to accelerate their computational convergence in a shorter time. The experimental results show that the relaxation factors obtained by the SA algorithm improve the computational time of the problem convergence regardless of user experience in the initial low-quality RF proposal. [ABSTRACT FROM AUTHOR]

Traditionally, it has been assumed that the compression of the sign of wavelet coefficients is not worth the effort because they form a zero-mean process. However, several image encoders such as JPEG 2000 include sign-coding capabilities. In this paper, we analyze the convenience of including sign-coding techniques into wavelet-based image encoders and propose a methodology that allows the design of sign-prediction tools for whatever kind of wavelet-based encoder. The proposed methodology is based on the use of metaheuristic algorithms to find the best sign prediction with the most appropriate context distribution that maximizes the resulting sign-compression rate of a particular wavelet encoder. Following our proposal, we have designed and implemented a sign-coding module for the LTW wavelet encoder, to evaluate the benefits of the sign-coding tool provided by our proposed methodology. The experimental results show that sign compression can save up to 18.91% of bit-rate when enabling sign-coding capabilities. Also, we have observed two general behaviors when coding the sign of wavelet coefficients: (a) the best results are provided from moderate to high compression rates; and (b) the sign redundancy may be better exploited when working with high-textured images. [ABSTRACT FROM AUTHOR]

This research proposes a genetic algorithm that provides a solution to the problem of deficient distribution of drinking water via the current hydraulic network in the neighborhood "Fraccionamiento Real Montecasino" (FRM), in Huitzilac, Morelos, Mexico. The proposed solution is the addition of new elements to the FRM network. The new elements include storage tanks, pipes, and pressure-reducing valves. To evaluate the constraint satisfaction model of mass and energy conservation, the hydraulic EPANET solver (HES) is used with an optimization model to minimize the total cost of changes in the network (new pipes, tanks, and valves). A genetic algorithm was used to evaluate the optimization model. The analysis of the results obtained by the genetic algorithm for the FRM network shows that adequate and balanced pressures were obtained by means of small modifications to the existing network, which entailed minimal costs. Simulations were performed for an extended period, which means that the pressure was obtained by simulation with HSE at one-hour intervals, during the algorithm execution, to verify adequate pressure at a specific point in the system, or to make corrections to ensure proper distribution, this with the aim of having a final optimized network design. [ABSTRACT FROM AUTHOR]

The objective of this research was to determine the main genera of nematodes associated with lychee adult plants and their association with the symptom of chlorosis. To do this, from March to August 2013, soil samples were collected from four commercial lychee plots in the tree drip zone. Five asymptomatic and five plants with chlorosis of the Brewster and Mauritius varieties were selected in three phenological stages: flowering, harvesting and vegetative development. Aphelenchus, Ditylenchus, Helicotylenchus, Hemicriconemoides, Longidorus, Mesocriconema, Pratylenchus, Psilenchus, Rotylenchus, Trichodorus, Tylenchorhynchus, Tylenchus and Xiphinema were the main genera identified. The highest number of total nematodes in Mauritius variety was obtained in the harvest stage (300.6, p=0.05), while in Brewster was in flowering (576, p=0.05). A direct relationship between the total population of nematodes and the symptom of chlorosis was not observed for the different phenological stages evaluated. [ABSTRACT FROM AUTHOR]