Modelos matemáticos para o problema integrado de dimensionamento de lotes e corte de estoque unidimensional

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Um estudo sobre limites duais para o problema integrado de dimensionamento de lotes e sequenciamento da produção

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

Lot production size problem and simulation of urban transport

OBJECTIVES AND STUDY METHOD: There are two subjects in this thesis: “Lot production size for a parallel machine scheduling problem with auxiliary equipment” and “Bus holding for a simulated traffic network”. Although these two themes seem unrelated, the main idea is the optimization of complex systems. The “Lot production size for a parallel machine scheduling problem with auxiliary equipment” deals with a manufacturing setting where sets of pieces form finished products. The aim is to maximize the profit of the finished products. Each piece may be processed in more than one mold. Molds must be mounted on machines with their corresponding installation setup times. The key point of our methodology is to solve the single period lot-sizing decisions for the finished products together with the piece-mold and the mold-machine assignments, relaxing the constraint that a single mold may not be used in two machines at the same time. For the “Bus holding for a simulated traffic network” we deal with One of the most annoying problems in urban bus operations is bus bunching, which happens when two or more buses arrive at a stop nose to tail. Bus bunching reflects an unreliable service that affects transit operations by increasing passenger-waiting times. This work proposes a linear mathematical programming model that establishes bus holding times at certain stops along a transit corridor to avoid bus bunching. Our approach needs real-time input, so we simulate a transit corridor and apply our mathematical model to the data generated. Thus, the inherent variability of a transit system is considered by the simulation, while the optimization model takes into account the key variables and constraints of the bus operation. CONTRIBUTIONS AND CONCLUSIONS: For the “Lot production size for a parallel machine scheduling problem with auxiliary equipment” the relaxation we propose able to find solutions more efficiently, moreover our experimental results show that most of the solutions verify that molds are non-overlapping even if they are installed on several machines. We propose an exact integer linear programming, a Relax&Fix heuristic, and a multistart greedy algorithm to solve this problem. Experimental results on instances based on real-world data show the efficiency of our approaches. The mathematical model and the algorithm for the lot production size problem, showed in this research, can be used for production planners to help in the scheduling of the manufacturing. For the “Bus holding for a simulated traffic network” most of the literature considers quadratic models that minimize passenger-waiting times, but they are harder to solve and therefore difficult to operate by real-time systems. On the other hand, our methodology reduces passenger-waiting times efficiently given our linear programming model, with the characteristic of applying control intervals just every 5 minutes.

Joint Power Control, Scheduling and Routing for Multihop Energy Harvesting Sensor Networks

We study wireless multihop energy harvesting sensor networks employed for random field estimation. The sensors sense the random field and generate data that is to be sent to a fusion node for estimation. Each sensor has an energy harvesting source and can operate in two modes: Wake and Sleep. We consider the problem of obtaining jointly optimal power control, routing and scheduling policies that ensure a fair utilization of network resources. This problem has a high computational complexity. Therefore, we develop a computationally efficient suboptimal approach to obtain good solutions to this problem. We study the optimal solution and performance of the suboptimal approach through some numerical examples.

Register Allocation and Optimal Spill code Scheduling in Software Pipelined Loops using 0-1 Integer Linear Programming Formulation

In achieving higher instruction level parallelism, software pipelining increases the register pressure in the loop. The usefulness of the generated schedule may be restricted to cases where the register pressure is less than the available number of registers. Spill instructions need to be introduced otherwise. But scheduling these spill instructions in the compact schedule is a difficult task. Several heuristics have been proposed to schedule spill code. These heuristics may generate more spill code than necessary, and scheduling them may necessitate increasing the initiation interval. We model the problem of register allocation with spill code generation and scheduling in software pipelined loops as a 0-1 integer linear program. The formulation minimizes the increase in initiation interval (II) by optimally placing spill code and simultaneously minimizes the amount of spill code produced. To the best of our knowledge, this is the first integrated formulation for register allocation, optimal spill code generation and scheduling for software pipelined loops. The proposed formulation performs better than the existing heuristics by preventing an increase in II in 11.11% of the loops and generating 18.48% less spill code on average among the loops extracted from Perfect Club and SPEC benchmarks with a moderate increase in compilation time.

Wireless scheduling with partial channel state information: large deviations and optimality

We consider a server serving a time-slotted queued system of multiple packet-based flows, where not more than one flow can be serviced in a single time slot. The flows have exogenous packet arrivals and time-varying service rates. At each time, the server can observe instantaneous service rates for only a subset of flows ( selected from a fixed collection of observable subsets) before scheduling a flow in the subset for service. We are interested in queue length aware scheduling to keep the queues short. The limited availability of instantaneous service rate information requires the scheduler to make a careful choice of which subset of service rates to sample. We develop scheduling algorithms that use only partial service rate information from subsets of channels, and that minimize the likelihood of queue overflow in the system. Specifically, we present a new joint subset-sampling and scheduling algorithm called Max-Exp that uses only the current queue lengths to pick a subset of flows, and subsequently schedules a flow using the Exponential rule. When the collection of observable subsets is disjoint, we show that Max-Exp achieves the best exponential decay rate, among all scheduling algorithms that base their decision on the current ( or any finite past history of) system state, of the tail of the longest queue. To accomplish this, we employ novel analytical techniques for studying the performance of scheduling algorithms using partial state, which may be of independent interest. These include new sample-path large deviations results for processes obtained by non-random, predictable sampling of sequences of independent and identically distributed random variables. A consequence of these results is that scheduling with partial state information yields a rate function significantly different from scheduling with full channel information. In the special case when the observable subsets are singleton flows, i.e., when there is effectively no a priori channel state information, Max-Exp reduces to simply serving the flow with the longest queue; thus, our results show that to always serve the longest queue in the absence of any channel state information is large deviations optimal.

装配车间的多品种变批量的生产调度优化模型

针对装配车间调度问题,提出了综合考虑生产中物料配送能力,车间存储物料能力以及装配工艺序列问题的多品种变批次的优化调度方法。主要是分两步解决:首先考虑不同类型产品的装配加工的顺序优化问题;然后,根据生产约束建立各类型产品的分批问题。最后,实现计划调度衔接,并应用于生产。该方法对于实际装配生产具有很强的可操作性。

Single machine scheduling and due date assignment under series-parallel precedence constraints

We consider a single machine due date assignment and scheduling problem of minimizing holding costs with no tardy jobs tinder series parallel and somewhat wider class of precedence constraints as well as the properties of series-parallel graphs.

A comparison of endoscopy versus pathology sizing of colorectal adenomas and potential implications for surveillance colonoscopy

Background and AimsTo compare endoscopy and pathology sizing in a large population-based series of colorectal adenomas and to evaluate the implications for patient stratification into surveillance colonoscopy.MethodsEndoscopy and pathology sizes available from intact adenomas removed at colonoscopies performed as part of the Northern Ireland Bowel Cancer Screening Programme, from 2010 to 2015, were included in this study. Chi-squared tests were applied to compare size categories in relation to clinicopathological parameters and colonoscopy surveillance strata according to current American Gastroenterology Association and British Society of Gastroenterology guidelines.ResultsA total of 2521 adenomas from 1467 individuals were included. There was a trend toward larger endoscopy than pathology sizing in 4 of the 5 study centers, but overall sizing concordance was good. Significantly greater clustering with sizing to the nearest 5 mm was evident in endoscopy versus pathology sizing (30% vs 19%, p<0.001), which may result in lower accuracy. Applying a 10-mm cut-off relevant to guidelines on risk stratification, 7.3% of all adenomas and 28.3% of those 8 to 12 mm in size had discordant endoscopy and pathology size categorization. Depending upon which guidelines are applied, 4.8% to 9.1% of individuals had differing risk stratification for surveillance recommendations, with the use of pathology sizing resulting in marginally fewer recommended surveillance colonoscopies.ConclusionsChoice of pathology or endoscopy approaches to determine adenoma size will potentially influence surveillance colonoscopy follow-up in 4.8% to 9.1% of individuals. Pathology sizing appears more accurate than endoscopy sizing, and preferential use of pathology size would result in a small, but clinically important, decreased burden on surveillance colonoscopy demand. Careful endoscopy sizing is required for adenomas removed piecemeal.

Sizing reserves within a landscape: the roles of villagers' reactions and the ecological-socioeconomic setting

Traditionally, siting and sizing decisions for parks and reserves reflected ecological characteristics but typically failed to consider ecological costs created from displaced resource collection, welfare costs on nearby rural people, and enforcement costs. Using a spatial game-theoretic model that incorporates the interaction of socioeconomic and ecological settings, we show how incorporating more recent mandates that include rural welfare and surrounding landscapes can result in very different optimal sizing decisions. The model informs our discussion of recent forest management in Tanzania, reserve sizing and siting decisions, estimating reserve effectiveness, and determining patterns of avoided forest degradation in Reduced Emissions from Deforestation and Forest Degradation programs.

An effective heuristic for stockyard planning and machinery scheduling at a coal handling facility

Coal handling is a complex process involving different correlated and highly dependent operations such as selecting appropriate product types, planning stockpiles, scheduling stacking and reclaiming activities and managing train loads. Planning these operations manually is time consuming and can result in non-optimized schedules as future impact of decisions may not be appropriately considered. This paper addresses the operational scheduling of the continuous coal handling problem with multiple conflicting objectives. As the problem is NP-hard in nature, an effective heuristic is presented for planning stockpiles and scheduling resources to minimize delays in production and the coal age in the stockyard. A model of stockyard operations within a coal mine is described and the problem is formulated as a Bi- Objective Optimization Problem (BOOP). The algorithm efficacy is demonstrated on different real-life data scenarios. Computational results show that the solution algorithm is effective and the coal throughput is substantially impacted by the conflicting objectives. Together, the model and the proposed heuristic, can act as a decision support system for the stockyard planner to explore the effects of alternative decisions, such as balancing age and volume of stockpiles, and minimizing conflicts due to stacker and reclaimer movements.

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.