An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

Model for facilities or vendors location in a global scale considering several echelons in the Chain

The facilities location problem for companies with global operations is very complex and not well explored in the literature. This work proposes a MILP model that solves the problem through minimization of the total logistic cost. Main contributions of the model are the pioneer carrying cost calculation, the treatment given to the take-or-pay costs and to the international tax benefits such as drawback and added value taxes in Brazil. The model was successfully applied to a real case of a chemical industry with industrial plants and sales all over the world. The model application recommended a totally new sourcing model for the company.

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics. (C) 2009 Elsevier B.V. All rights reserved.

Evaluating Patellar Kinematics Through Magnetic Resonance Imaging During Open- and Closed-Kinetic-Chain Exercises

Purpose: To evaluate patellar kinematics of volunteers Without knee pain at rest and during isometric contraction in open- and closed-kinetic-chain exercises. Methods: Twenty individuals took part in this study. All were submitted to magnetic resonance imaging (MRI) during rest and voluntary isometric contraction (VIC) in the open anti closed kinetic chain at 15 degrees, 30 degrees, and 45 degrees of knee flexion. Through MRI and using medical e-film software, the following measurements were evaluated: sulcus angle, patellar-tilt angle, and bisect offset. The mixed-effects linear model was used for comparison between knee positions, between rest and isometric contractions, and between (he exercises. Results: Data analysis revealed that the sulcus angle decreased as knee flexion increased and revealed increases with isometric contractions in both the open and closed kinetic chain for all knee-flexion angles. The patellar-tilt angle decreased with isometric contractions in both the open and closed kinetic chain for every knee position. However, in the closed kinetic chain, patellar tilt increased significantly with the knee flexed at 15 degrees. The bisect offset increased with the knee flexed at 15 degrees during isometric contractions and decreased as knee flexion increased during both exercises. Conclusion: VIC in the last degrees of knee extension may compromise patellar dynamics. On the other hand, it is possible to favor patellar stability by performing muscle contractions with the knee flexed at 30 degrees and 45 degrees in either the open or closed kinetic chain.

Optimal synthesis of Fenton reactor networks for phenol degradation

There is an increasing need to treat effluents contaminated with phenol with advanced oxidation processes (AOPs) to minimize their impact on the environment as well as on bacteriological populations of other wastewater treatment systems. One of the most promising AOPs is the Fenton process that relies on the Fenton reaction. Nevertheless, there are no systematic studies on Fenton reactor networks. The objective of this paper is to develop a strategy for the optimal synthesis of Fenton reactor networks. The strategy is based on a superstructure optimization approach that is represented as a mixed integer non-linear programming (MINLP) model. Network superstructures with multiple Fenton reactors are optimized with the objective of minimizing the sum of capital, operation and depreciation costs of the effluent treatment system. The optimal solutions obtained provide the reactor volumes and network configuration, as well as the quantities of the reactants used in the Fenton process. Examples based on a case study show that multi-reactor networks yield decrease of up to 45% in overall costs for the treatment plant. (C) 2010 The Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.

Optimized harvest scheduling in eucalyptus plantations under operational, spatial and climatic constraints

The representation of sustainability concerns in industrial forests management plans, in relation to environmental, social and economic aspects, involve a great amount of details when analyzing and understanding the interaction among these aspects to reduce possible future impacts. At the tactical and operational planning levels, methods based on generic assumptions usually provide non-realistic solutions, impairing the decision making process. This study is aimed at improving current operational harvesting planning techniques, through the development of a mixed integer goal programming model. This allows the evaluation of different scenarios, subject to environmental and supply constraints, increase of operational capacity, and the spatial consequences of dispatching harvest crews to certain distances over the evaluation period. As a result, a set of performance indicators was selected to evaluate all optimal solutions provided to different possible scenarios and combinations of these scenarios, and to compare these outcomes with the real results observed by the mill in the study case area. Results showed that it is possible to elaborate a linear programming model that adequately represents harvesting limitations, production aspects and environmental and supply constraints. The comparison involving the evaluated scenarios and the real observed results showed the advantage of using more holistic approaches and that it is possible to improve the quality of the planning recommendations using linear programming techniques.

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

Coactivation of the shoulder and arm muscles during closed kinetic chain exercises on an unstable surface

Introduction: The purpose of this study was to compare the electromyography index of muscle coactivation of the following muscle pairs: posterior deltoid and pectoralis major (PD/PM); triceps brachii and biceps brachii (TB/BB); and serratus anterior and upper trapezius (SA/UT) during three different closed kinetic chain exercises (wall-press, bench-press and push-up) on an unstable surface at the maximal load. Methods: A total of 20 healthy sedentary men participated in the study. Integral linear values were obtained from three sustained contractions of six seconds each for the three proposed exercises. Mean coactivation index values were compared using the mixed-effects linear model, with a five percent significance level. Results: Electromyography indexes of muscle coactivation showed significant differences for the PD/PM and TB/BB muscle pairs. No differences were found between exercises for the SA/UT muscle pair. Conclusion: Our results seem to differ from those of previous studies, which reported that the similarity in exercises performed is responsible for the comparable muscle activation levels.

Masseter muscle thickness three years after surgical correction of class III dentofacial deformity

Objective: To analyse the effect of integrated orthodontic treatment, orthognathic surgery and orofacial myofunctional therapy on masseter muscle thickness in patients with class III dentofacial deformity three years after orthognathic surgery. Design: A longitudinal study was conducted on 13 patients with class III dentofacial deformities, denoted here as group P1 (before surgery) and group P3 (same patients 3 years to 3 years and 8 months after surgery). Fifteen individuals with no changes in facial morphology or dental occlusion were assigned to the control group (CG). Masseter muscle ultrasonography was performed in the resting and biting situations in the three groups. Data were analysed statistically by a mixed-effects linear model considering a level of significance of P < 0.05. Results: Significantly higher values (P < 0.01) of masseter muscle thickness (cm) were detected in group P3 (right rest: 0.82 +/- 0.16, left rest: 0.87 +/- 0.21, right bite: 1 +/- 0.22, left bite: 1.04 +/- 0.28) compared to group P1 (right rest: 0.63 +/- 0.19, left rest: 0.64 +/- 0.15, right bite: 0.87 +/- 0.16, left bite: 0.88 +/- 0.14). Between P3 and CG (right rest: 1.02 +/- 0.19, left rest: 1 +/- 0.19, right bite: 1.18 +/- 0.22, left bite: 1.16 +/- 0.22) there was a significant difference on the right side of the muscle (P < 0.05) in both situations and on the left side at rest. Conclusion: The proposed treatment resulted in improved masseter muscle thickness in patients with class III dentofacial deformity. (C) 2011 Elsevier Ltd. All rights reserved.

Crop rotation scheduling with adjacency constraints

In this article we propose a 0-1 optimization model to determine a crop rotation schedule for each plot in a cropping area. The rotations have the same duration in all the plots and the crops are selected to maximize plot occupation. The crops may have different production times and planting dates. The problem includes planting constraints for adjacent plots and also for sequences of crops in the rotations. Moreover, cultivating crops for green manuring and fallow periods are scheduled into each plot. As the model has, in general, a great number of constraints and variables, we propose a heuristics based on column generation. To evaluate the performance of the model and the method, computational experiments using real-world data were performed. The solutions obtained indicate that the method generates good results.

An approach for solving the lot-sizing problem of a market-driven foundry

Foundries can be found all over Brazil and they are very important to its economy. In 2008, a mixed integer-programming model for small market-driven foundries was published, attempting to minimize delivery delays. We undertook a study of that model. Here, we present a new approach based on the decomposition of the problem into two sub-problems: production planning of alloys and production planning of items. Both sub-problems are solved using a Lagrangian heuristic based on transferences. An important aspect of the proposed heuristic is its ability to take into account a secondary practice objective solution: the furnace waste. Computational tests show that the approach proposed here is able to generate good quality solutions that outperform prior results. Journal of the Operational Research Society (2010) 61, 108-114. doi:10.1057/jors.2008.151

A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem

Industrial production processes involving both lot-sizing and cutting stock problems are common in many industrial settings. However, they are usually treated in a separate way, which could lead to costly production plans. In this paper, a coupled mathematical model is formulated and a heuristic method based on Lagrangian relaxation is proposed. Computational results prove its effectiveness. (C) 2009 Elsevier B.V. All rights reserved.

Lot sizing and furnace scheduling in small foundries

A lot sizing and scheduling problem prevalent in small market-driven foundries is studied. There are two related decision levels: (I the furnace scheduling of metal alloy production, and (2) moulding machine planning which specifies the type and size of production lots. A mixed integer programming (MIP) formulation of the problem is proposed, but is impractical to solve in reasonable computing time for non-small instances. As a result, a faster relax-and-fix (RF) approach is developed that can also be used on a rolling horizon basis where only immediate-term schedules are implemented. As well as a MIP method to solve the basic RF approach, three variants of a local search method are also developed and tested using instances based on the literature. Finally, foundry-based tests with a real-order book resulted in a very substantial reduction of delivery delays and finished inventory, better use of capacity, and much faster schedule definition compared to the foundry`s own practice. (c) 2006 Elsevier Ltd. All rights reserved.

Scheduling Grid Applications with Software Requirements

The aim of task scheduling is to minimize the makespan of applications, exploiting the best possible way to use shared resources. Applications have requirements which call for customized environments for their execution. One way to provide such environments is to use virtualization on demand. This paper presents two schedulers based on integer linear programming which schedule virtual machines (VMs) in grid resources and tasks on these VMs. The schedulers differ from previous work by the joint scheduling of tasks and VMs and by considering the impact of the available bandwidth on the quality of the schedule. Experiments show the efficacy of the schedulers in scenarios with different network configurations.