291 |
A MULTI-COMMODITY NETWORK FLOW APPROACH FOR SEQUENCING REFINED PRODUCTS IN PIPELINE SYSTEMSAcosta Amado, Rolando José 01 May 2011 (has links)
In the oil industry, there is a special class of pipelines used for the transportation of refined products. The problem of sequencing the inputs to be pumped through this type of pipeline seeks to generate the optimal sequence of batches of products and their destination as well as the amount of product to be pumped such that the total operational cost of the system, or another operational objective, is optimized while satisfying the product demands according to the requirements set by the customers. This dissertation introduces a new modeling approach and proposes a solution methodology for this problem capable of dealing with the topology of all the scenarios reported in the literature so far.
The system representation is based on a 1-0 multi commodity network flow formulation that models the dynamics of the system, including aspects such as conservation of product flow constraints at the depots, travel time of products from the refinery to their depot destination and what happens upstream and downstream the line whenever a product is being received at a given depot while another one is being injected into the line at the refinery. It is assumed that the products are already available at the refinery and their demand at each depot is deterministic and known beforehand. The model provides the sequence, the amounts, the destination and the trazability of the shipped batches of different products from their sources to their destinations during the entire horizon planning period while seeking the optimization of pumping and inventory holding costs satisfying the time window constraints.
A survey for the available literature is presented. Given the problem structure, a decomposition based solution procedure is explored with the intention of exploiting the network structure using the network simplex method. A branch and bound algorithm that exploits the dynamics of the system assigning priorities for branching to a selected set of variables is proposed and its computational results for the solution, obtained via GAMS/CPLEX, of the formulation for random instances of the problem of different sizes are presented. Future research directions on this field are proposed.
|
292 |
Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problemSachdeva, Sandeep 12 April 2006 (has links)
We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.
|
293 |
A new polyhedral approach to combinatorial designsArambula Mercado, Ivette 30 September 2004 (has links)
We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.
|
294 |
Vers un outil d’aide à la planification et à l’ordonnancement des blocs opératoiresFEI, Hongying 17 March 2006 (has links)
Résumé
Dans cette thèse, nous étudions la gestion des blocs opératoires, et plus particulièrement la planification et l’ordonnancement de ces blocs. Le choix d’études de ce secteur hospitalier est lié au fait qu’il est réputé comme un lieu hautement stratégique dans un établissement hospitalier, surtout en terme de coûts. Il est dès lors utile de s’intéresser à l’optimisation de l’utilisation des ressources hospitalières. Etant donné que l’optimisation du fonctionnement des blocs opératoires est un problème vaste et complexe, nous nous focalisons sur deux sous-problèmes déjà réputés difficiles : la planification et l’ordonnancement des interventions chirurgicales. Ce sont des problèmes centrés sur la programmation opératoire et dont l’objectif est d’obtenir un programme opératoire réalisable et efficace du bloc.
Les problèmes de planification sont premièrement formalisés comme des modèles mathématiques en nombres entiers et puis résolus par des procédures heuristiques et par un « Branch-and-Price » basés sur la génération de colonnes qui est utilisée pour résoudre les relaxations linéaires des modèles concernés afin de trouver les bornes inférieures. Les modèles d’ordonnancement sont traités comme des variantes de modèles de « flow shop » hybride à deux étages et résolus par des algorithmes génétiques hybrides. Finalement, nos modèles ont été testés et validés sur un cas réel.
ABSTRACT
This thesis presents our studies on the operating theatre management, especially on the operating theatre planning and scheduling problem in case that this surgical sector is always regarded as the kernel in a hospital in terms of the expenditure. Therefore, it’s necessary to optimize the assignment of hospital resources in the operating theatre. Since this type of problem is extremely complex, we concentrate on just two sub-problems that are also considered difficult ones by researchers: the surgical cases planning and scheduling problem, which aim to make a surgical cases programming with an objective of obtaining a realizable and efficient surgical cases operating schedule. At first the weekly planning problems of surgical cases are formulated as a mathematical integer programming, and then they are solved by heuristic procedures and Branch-and-Price one. All these procedures are based on the column generation procedure, which is used to solve the linear relaxation of each model for a lower bound. The scheduling models are treated as variants of hybrid two-stage flow shop problem and are solved by proposed hybrid genetic algorithms. Finally, our models are tested and validated in a real case.
|
295 |
On Models and Methods for Global Optimization of Structural TopologyStolpe, Mathias January 2003 (has links)
This thesis consists of an introduction and sevenindependent, but closely related, papers which all deal withproblems in structural optimization. In particular, we considermodels and methods for global optimization of problems intopology design of discrete and continuum structures. In the first four papers of the thesis the nonconvex problemof minimizing the weight of a truss structure subject to stressconstraints is considered. First itis shown that a certainsubclass of these problems can equivalently be cast as linearprograms and thus efficiently solved to global optimality.Thereafter, the behavior of a certain well-known perturbationtechnique is studied. It is concluded that, in practice, thistechnique can not guarantee that a global minimizer is found.Finally, a convergent continuous branch-and-bound method forglobal optimization of minimum weight problems with stress,displacement, and local buckling constraints is developed.Using this method, several problems taken from the literatureare solved with a proof of global optimality for the firsttime. The last three papers of the thesis deal with topologyoptimization of discretized continuum structures. Theseproblems are usually modeled as mixed or pure nonlinear 0-1programs. First, the behavior of certain often usedpenalization methods for minimum compliance problems isstudied. It is concluded that these methods may fail to producea zero-one solution to the considered problem. To remedy this,a material interpolation scheme based on a rational functionsuch that compli- ance becomes a concave function is proposed.Finally, it is shown that a broad range of nonlinear 0-1topology optimization problems, including stress- anddisplacement-constrained minimum weight problems, canequivalently be modeled as linear mixed 0-1 programs. Thisresult implies that any of the standard methods available forgeneral linear integer programming can now be used on topologyoptimization problems. <b>Keywords:</b>topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.
|
296 |
Single Machine Scheduling with Tardiness Involved Objectives : A SurveyMundt, Andreas, Wich, Thomas January 2007 (has links)
This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.
|
297 |
Locations On A Line And Generalization To The Dynamic P-mediansGuden, Huseyin 01 September 2012 (has links) (PDF)
This study deals with four location problems. The first problem is a brand new location problem on a line and considers the location decisions for depots and quarries in a highway construction project. We develop optimal solution properties of the problem. Using these properties, a dynamic programming algorithm is proposed. The second problem is also a brand new dynamic location problem on a line and locates concrete batching mobile and immobile facilities for a railroad construction project. We develop two mixed integer models to solve the problem. For solving large size problems, we propose a heuristic. Performances of models and the heuristic are tested on randomly generated instances plus a case study data and results are presented. The third problem is a generalization of the second problem to network locations. It is a dynamic version of the well known p-median problem and incorporates mobile facilities. The problem is to locate predetermined number of mobile and immobile facilities over a planning horizon such that sum of facility movement and allocation costs is minimized. Three constructive heuristics and a branch-and-price algorithm are proposed. Performances of these solution procedures are tested on randomly generated instances and results are presented. In the fourth problem we consider a special case of the third problem, allowing only conventional facilities. The algorithm for the third problem is improved so that generating columns and solving a mixed integer model are used repetitively. Performance of the algorithm is tested on randomly generated instances and results are presented.
|
298 |
Co-rotational beam elements in instability problemsBattini, Jean-Marc January 2002 (has links)
The purpose of the work presented in this thesis is to implement co-rotational beam elements and branch-switching procedures in order to analyse elastic and elastoplasticinstability problems. For the 2D beam elements, the co-rotational framework is taken from Crisfield [23]. The main objective is to compare three different local elasto-plastic elements. The 3D co-rotational formulation is based on the work of Pacoste and Eriksson [73],with new items concerning the parameterisation of the finite rotations, the definitionof the local frame, the inclusion of warping effects through the introduction of aseventh nodal degree of freedom and the consideration of rigid links. Differenttypes of local formulations are considered, including or not warping effects. It isshown that at least some degree of non-linearity must be introduced in the localstrain definition in order to obtain correct results for certain classes of problems. Within the present approach any cross-section can be modelled, and particularly, the centroid and shear center are not necessarily coincident.Plasticity is introduced via a von Mises material with isotropic hardening. Numericalintegration over the cross-section is performed. At each integration point, theconstitutive equations are solved by including interaction between the normal andshear stresses. Concerning instabilities, a new numerical method for the direct computation of elasticcritical points is proposed. This is based on a minimal augmentation procedure asdeveloped by Eriksson [32–34]. In elasto-plasticity, a literature survey, mainly concernedwith theoretical aspects is first presented. The objective is to get a completecomprehension of the phenomena and to give a basis for the two branch-switchingprocedures presented in this thesis.A large number of examples are used in order to assess the performances of the elements and the path-following procedures. / QC 20100512
|
299 |
Leverantörsrelationer : - i byggbranschen jämfört med ett företag i produktionsbranschenErvallius, David, Fjellström, Benjamin January 2007 (has links)
Study objects: JM, Folkhem and ABB. Purpose: The purpose with this study are to examine how the supplier relations are in the construction branch and compare that result with how the supplier relations are for ABB a production company. Theoretical: The theoretical chapter illustrates important and relevant parts of supplier relations, purchasing and supplier strategies to give good overview. The theoretical review will combine information from different fields to consent with the research problem. Method: A case study has been made on three different companies, one of the companies was active in the production industry the other two were active in the construction industry. Data was mainly collected through semi structured interviews on each of the three companies. Conclusions: The size of the company decided which point of view the company had on purchasing, traditional or modern view. All three companies had a centralized purchasing organization but the construction firms were more decentralized than the production company. The reason was that the construction firms were dependent with more flexibility when every construction project is unique.
|
300 |
The Effect of the Establishment of the Day Clearing Branch on Trading Costs: A Look at the NYSE In 1920Wong, Samuel W 01 January 2012 (has links)
As a financial institution that clears and settles payments for equity and other securities, a clearinghouse essentially reduces the counterparty risk. It diminishes the risk of one party failing to meet its obligations, and makes markets more efficient through netting. This paper examines the impact of the establishment of the Day Clearing Branch on April 26, 1920, which allowed the NYSE Clearinghouse to net cash values and clear loans, supposedly resulting in savings in banking, time, and labor. The common and preferred equity securities that traded on the NYSE during the year 1920 were analyzed. The effect on bid-ask spreads and volume traded were scrutinized. It was found that these securities had increases in bid-ask spreads and decreases in volume traded, contrary to prior hypotheses.
|
Page generated in 0.0284 seconds