Um modelo de otimização inteira mista e heurísticas relax and fix para a programação da produção de fábricas de refrigerantes de pequeno porte

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups

A lot sizing and scheduling problem from a foundry is considered in which key materials are produced and then transformed into many products on a single machine. A mixed integer programming (MIP) model is developed, taking into account sequence-dependent setup costs and times, and then adapted for rolling horizon use. A relax-and-fix (RF) solution heuristic is proposed and computationally tested against a high-performance MIP solver. Three variants of local search are also developed to improve the RF method and tested. Finally the solutions are compared with those currently practiced at the foundry.

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: (1) 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. © 2006 Elsevier Ltd. All rights reserved.

Genetic algorithm, MIP and improvement heuristic applied to the MLCLP with backlogging

The present paper solves the multi-level capacitated lot sizing problem with backlogging (MLCLSPB) combining a genetic algorithm with the solution of mixed-integer programming models and the improvement heuristic fix and optimize. This approach is evaluated over sets of benchmark instances and compared to methods from literature. Computational results indicate competitive results applying the proposed method when compared with other literature approaches. © 2013 IEEE.

A more efficient and effective heuristic algorithm for the MapReduce placement problem in cloud computing

The placement of the mappers and reducers on the machines directly affects the performance and cost of the MapReduce computation in cloud computing. From the computational point of view, the mappers/reducers placement problem is a generalization of the classical bin packing problem, which is NP-complete. Thus, in this paper we propose a new heuristic algorithm for the mappers/reducers placement problem in cloud computing and evaluate it by comparing with other several heuristics on solution quality and computation time by solving a set of test problems with various characteristics. The computational results show that our heuristic algorithm is much more efficient than the other heuristics. Also, we verify the effectiveness of our heuristic algorithm by comparing the mapper/reducer placement for a benchmark problem generated by our heuristic algorithm with a conventional mapper/reducer placement. The comparison results show that the computation using our mapper/reducer placement is much cheaper while still satisfying the computation deadline.

Some new results regarding spikes and a heuristic for spike construction

his paper addresses the problem of minimizing the number of columns with superdiagonal nonzeroes (viz., spiked columns) in a square, nonsingular linear system of equations which is to be solved by Gaussian elimination. The exact focus is on a class of min-spike heuristics in which the rows and columns of the coefficient matrix are first permuted to block lower-triangular form. Subsequently, the number of spiked columns in each irreducible block and their heights above the diagonal are minimized heuristically. We show that ifevery column in an irreducible block has exactly two nonzeroes, i.e., is a doubleton, then there is exactly one spiked column. Further, if there is at least one non-doubleton column, there isalways an optimal permutation of rows and columns under whichnone of the doubleton columns are spiked. An analysis of a few benchmark linear programs suggests that singleton and doubleton columns can abound in practice. Hence, it appears that the results of this paper can be practically useful. In the rest of the paper, we develop a polynomial-time min-spike heuristic based on the above results and on a graph-theoretic interpretation of doubleton columns.

Mix it and fix it: functions of composite olfactory signals in ring-tailed lemurs.

Animals communicating via scent often deposit composite signals that incorporate odorants from multiple sources; however, the function of mixing chemical signals remains understudied. We tested both a 'multiple-messages' and a 'fixative' hypothesis of composite olfactory signalling, which, respectively, posit that mixing scents functions to increase information content or prolong signal longevity. Our subjects-adult, male ring-tailed lemurs (Lemur catta)-have a complex scent-marking repertoire, involving volatile antebrachial (A) secretions, deposited pure or after being mixed with a squalene-rich paste exuded from brachial (B) glands. Using behavioural bioassays, we examined recipient responses to odorants collected from conspecific strangers. We concurrently presented pure A, pure B and mixed A + B secretions, in fresh or decayed conditions. Lemurs preferentially responded to mixed over pure secretions, their interest increasing and shifting over time, from sniffing and countermarking fresh mixtures, to licking and countermarking decayed mixtures. Substituting synthetic squalene (S)-a well-known fixative-for B secretions did not replicate prior results: B secretions, which contain additional chemicals that probably encode salient information, were preferred over pure S. Whereas support for the 'multiple-messages' hypothesis underscores the unique contribution from each of an animal's various secretions, support for the 'fixative' hypothesis highlights the synergistic benefits of composite signals.

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.

Relax and cut: limitantes duais para o problema do caixeiro viajante

Pós-graduação em Matemática - IBILCE

An order batching and processing heuristic to address aisle congestion in a manual order picking warehouse with order due dates

A heuristic for batching orders in a manual order-picking warehouse has been developed. It prioritizes orders based on due time to prevent mixing of orders of different priority levels. The order density of aisles criterion is used to form batches. It also determines the number of pickers required and assigns batches to pickers such that there is a uniform workload per unit of time. The effectiveness of the heuristic was studied by observing computational time and aisle congestion for various numbers of total orders and number of orders that form a batch. An initial heuristic performed well for small number of orders, but for larger number of orders, a partitioning technique is computationally more efficient, needing only minutes to solve for thousands of orders, while preserving 90% of the batch quality obtained with the original heuristic. Comparative studies between the heuristic and other published heuristics are needed. ^

Allocating reforestation areas for sediment flow minimization: an integer programming formulation and a heuristic solution method

Policy and decision makers dealing with environmental conservation and land use planning often require identifying potential sites for contributing to minimize sediment flow reaching riverbeds. This is the case of reforestation initiatives, which can have sediment flow minimization among their objectives. This paper proposes an Integer Programming (IP) formulation and a Heuristic solution method for selecting a predefined number of locations to be reforested in order to minimize sediment load at a given outlet in a watershed. Although the core structure of both methods can be applied for different sorts of flow, the formulations are targeted to minimization of sediment delivery. The proposed approaches make use of a Single Flow Direction (SFD) raster map covering the watershed in order to construct a tree structure so that the outlet cell corresponds to the root node in the tree. The results obtained with both approaches are in agreement with expert assessments of erosion levels, slopes and distances to the riverbeds, which in turn allows concluding that this approach is suitable for minimizing sediment flow. Since the results obtained with the IP formulation are the same as the ones obtained with the Heuristic approach, an optimality proof is included in the present work. Taking into consideration that the heuristic requires much less computation time, this solution method is more suitable to be applied in large sized problems.

Métodos de solução para um problema de sequenciamento da produção com sincronismo de execução de tarefas

Pós-graduação em Engenharia Mecânica - FEG

A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)