Дисертації: "Method of «branch and bound»"

1

Stix, Volker. "Stochastic branch & bound applying target oriented branch & bound method to optimal scenario tree reduction." Institut für Informationsverarbeitung und Informationswirtschaft, WU Vienna University of Economics and Business, 2002. http://epub.wu.ac.at/1212/1/document.pdf.

Повний текст джерела

Анотація:

In this article a new branch & bound method is described. It uses an artificial target to improve its bounding capabilities. Therefore the new approach is faster compared to the classical one. It is applied to the stochastic problem of optimal scenario tree reduction. The aspects of global optimization are emphasized here. All necessary components for that problem are developed and some experimental results underline the benefits of the new approach. (author's abstract)
Series: Working Papers on Information Systems, Information Business and Operations

Стилі APA, Harvard, Vancouver, ISO та ін.

2

Stix, Volker. "Target oriented branch & bound method for global optimization." Institut für Informationsverarbeitung und Informationswirtschaft, WU Vienna University of Economics and Business, 2002. http://epub.wu.ac.at/1696/1/document.pdf.

Повний текст джерела

Анотація:

We introduce a very simple but efficient idea for branch & bound (B&B) algorithms in global optimization (GO). As input for our generic algorithm, we need an upper bound algorithm for the GO maximization problem and a branching rule. The latter reduces the problem into several smaller subproblems of the same type. The new B&B approach delivers one global optimizer or, if stopped before finished, improved upper and lower bounds for the problem. Its main difference to commonly used B&B techniques is its ability to approximate the problem from above and from below while traversing the problem tree. It needs no supplementary information about the system optimized and does not consume more time than classical B&B techniques. Experimental results with the maximum clique problem illustrate the benefit of this new method. (author's abstract)
Series: Working Papers on Information Systems, Information Business and Operations

Стилі APA, Harvard, Vancouver, ISO та ін.

3

Ryoo, Moo Bong. "A constraint branch-and-bound method for set partitioning problems." Thesis, Monterey, California : Naval Postgraduate School, 1990. http://handle.dtic.mil/100.2/ADA227092.

Повний текст джерела

Анотація:

Thesis (M.S. in Operations Research)--Naval Postgraduate School, March 1990.
Thesis Advisor(s): Wood, R. Kevin. Second Reader: Brown, Gerald Gerard. "March 1990." Description based on signature page as viewed on October 21, 2009. Author(s) subject terms: Set partitioning problem, constraint branch and bound method, enumeration tree. Includes bibliographical references (p. 34-36). Also available online.

Стилі APA, Harvard, Vancouver, ISO та ін.

4

Hu, Sha S. M. Massachusetts Institute of Technology. "Semidefinite relaxation based branch-and-bound method for nonconvex quadratic programming." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/39217.

Повний текст джерела

Анотація:

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006.
Includes bibliographical references (leaves 73-75).
In this thesis, we use a semidefinite relaxation based branch-and-bound method to solve nonconvex quadratic programming problems. Firstly, we show an interval branch-and-bound method to calculate the bounds for the minimum of bounded polynomials. Then we demonstrate four SDP relaxation methods to solve nonconvex Box constrained Quadratic Programming (BoxQP) problems and the comparison of the four methods. For some lower dimensional problems, SDP relaxation methods can achieve tight bounds for the BoxQP problem; whereas for higher dimensional cases (more than 20 dimensions), the bounds achieved by the four Semidefinite programming (SDP) relaxation methods are always loose. To achieve tight bounds for higher dimensional BoxQP problems, we combine the branch-and-bound method and SDP relaxation method to develop an SDP relaxation based branch-and-bound (SDPBB) method. We introduce a sensitivity analysis method for the branching process of SDPBB. This sensitivity analysis method can improve the convergence speed significantly.
(cont.) Compared to the interval branch-and-bound method and the global optimization software BARON, SDPBB can achieve better bounds and is also much more efficient. Additionally, we have developed a multisection algorithm for SDPBB and the multisection algorithm has been parallelized using Message Passing Interface (MPI). By parallelizing the program, we can significantly improve the speed of solving higher dimensional BoxQP problems.
by Sha Hu.
S.M.

Стилі APA, Harvard, Vancouver, ISO та ін.

5

Mutlu, Mustafa Cagdas. "A Branch And Bound Algorithm For Resource Leveling Problem." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612259/index.pdf.

Повний текст джерела

Анотація:

Resource Leveling Problem (RLP) aims to minimize undesired fluctuations in resource distribution curves which cause several practical problems. Many studies conclude that commercial project management software packages can not effectively deal with RLP. In this study a branch and bound algorithm is presented for solving RLP for single and multi resource, small size networks. The algorithm adopts a depth-first strategy and stores start times of non-critical activities in the nodes of the search tree. Optimal resource distributions for 4 different types of resource leveling metrics can be obtained via the developed procedure. To prune more of the search tree and thereby reduce the computation time, several lower bound calculation methods are employed. Experiment results from 20 problems showed that the suggested algorithm can successfully locate optimal solutions for networks with up to 20 activities. The algorithm presented in this study contributes to the literature in two points. First, the new lower bound improvement method (maximum allowable daily resources method) introduced in this study reduces computation time required for achieving the optimal solution for the RLP. Second, optimal solutions of several small sized problems have been obtained by the algorithm for some traditional and recently suggested leveling metrics. Among these metrics, Resource Idle Day (RID) has been utilized in an exact method for the first time. All these solutions may form a basis for performance evaluation of heuristic and metaheuristic procedures for the RLP. Limitations of the developed branch and bound procedure are discussed and possible further improvements are suggested.

Стилі APA, Harvard, Vancouver, ISO та ін.

6

Poliquit, Elmer S. "A method for solving the minimization of the maximum number of open stacks problem within a cutting process." View electronic thesis, 2008. http://dl.uncw.edu/etd/2008-1/r1/poliquite/elmerpoliquit.pdf.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

7

Ku, Wen-Yang. "Lattice preconditioning for the real relaxation based branch and bound method for integer least squares problems." Thesis, McGill University, 2012. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=106555.

Повний текст джерела

Анотація:

Lattice basis reduction is a powerful tool for solving complex problems both in pure mathematics and practical applications. In this thesis, we use lattice basis reduction as a preconditioning technique to accelerate the real relaxation based branch and bound (RRBB) method for solving integer least squares (ILS) problems. We give theoretical arguments and simulation results to show that applying lattice preconditioning to the RRBB method can greatly reduce the size of the RRBB tree for ordinary ILS problems, making the method more efficient. We then propose new reduction strategies, which are more effective than some typical existing reduction strategies for lattice preconditioning. Finally we extend the preconditioning techniques to the RRBB method for box-constrained and more general linear-inequality constrained ILS problems. Numerical test results indicate lattice preconditioning is also very effective to reduce the computation time of the RRBB method for these constrained problems.
Les techniques de réduction de réseaux est un outil puissant pour résoudre des problèmes complexes tant en mathématiques pures et les applications pratiques. Dans cette thèse, nous utilisons reduction de réseaux comme une technique de préconditionnement pour accélérer la branche réelle détente et de base lié (RRBB) méthode pour résoudre les problèmes de moindres carrés en nombres entiers (ILS). Nous donnons des arguments théoriques et des résultats de simulation pour montrerque l'application de treillis de préconditionnement de la méthode RRBB peut réduire considérablement la taille de l'arbre RRBB pour des problèmes ILS ordinaires, cequi rend la méthode plus efficace. Nous proposons ensuite de nouvelles stratégies de réduction, qui sont plus efficaces que certaines stratégies de réduction de type existants pour le préconditionnement treillis. Enfin nous étendons les techniques de préconditionnement de la méthode RRBB pour la contrainte des boîtes et des contraintes linéaires-inégalité plus générales des problémes ILS. Les résultats des simulations numériques indiquent que le préconditionnement treillis est également très efficace pour réduire le temps de calcul de la méthode RRBB pour ces problèmes contraints.

Стилі APA, Harvard, Vancouver, ISO та ін.

8

Morén, Björn. "Utilizing problem specic structures in branch and bound methods for manpower planning." Thesis, Linköpings universitet, Optimeringslära, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-84327.

Повний текст джерела

Анотація:

This thesis is about solving the manpower planning problem concerning stangand transitioning of pilots. The objective of the planning is to have enoughpilots to satisfy the demand while minimizing the cost. The main decisions totake are how many pilots to hire, which pilots to train and which courses toschedule. The planning problems that arise are both large and dicult whichmakes it important to use ecient solution methods. Seniority rules betweenpairs of pilots are the most complicating factor.A major part in the solution process is the solving of mixed integer programs.The emphasis in the thesis is to develop and test adaptations of the branch andbound algorithm to solve mixed integer programs faster. One of these is abranching principle that takes a problem specic structure into account. Agraph of implications is constructed from the seniority rules and this graph isthen used to estimate the impact of each branching candidate. The implementedmethods outperform the software XPRESS on some instances, while for mostinstances the performance is comparable.

Стилі APA, Harvard, Vancouver, ISO та ін.

9

Hailer, Angelika Christina. "Verification of branch and bound algorithms applied to water distribution network design." Berlin Logos-Verl, 2006. http://deposit.d-nb.de/cgi-bin/dokserv?id=2844475&prov=M&dok_var=1&dok_ext=htm.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

10

Bischoff, Martin. "Location of connection facilities /." Aachen : Shaker, 2008. http://d-nb.info/988141434/04.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

11

Villela, Pedro Ferraz 1982. "Um algoritmo exato para a otimização de carteiras de investimento com restrições de cardinalidade." [s.n.], 2008. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307123.

Повний текст джерела

Анотація:

Orientador: Francisco de Assis Magalhães Gomes Neto
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-12T16:09:04Z (GMT). No. of bitstreams: 1 Villela_PedroFerraz_M.pdf: 727069 bytes, checksum: d87d64ae49bfc1a53017a463cf10b453 (MD5) Previous issue date: 2008
Resumo: Neste trabalho, propomos um método exato para a resolução de problemas de programação quadrática que envolvem restrições de cardinalidade. Como aplicação, empregamos o método para a obtenção da fronteira eficiente de um problema (bi-objetivo) de otimização de carteiras de investimento. Nosso algoritmo é baseado no método Branch-and-Bound. A chave de seu sucesso, entretanto, reside no uso do método de Lemke, que é aplicado para a resolução dos subproblemas associados aos nós da árvore gerada pelo Branch-and-Bound. Ao longo do texto, algumas heurísticas também são introduzidas, com o propósito de acelerar a convergência do método. Os resultados computacionais obtidos comprovam que o algoritmo proposto é eficiente.
Abstract: In this work, we propose an exact method for the resolution of quadratic programming problems involving cardinality restrictions. As an application, the algorithm is used to generate the effective Pareto frontier of a (bi-objective) portfolio optimization problem. This algorithm is based on the Branch-and-Bound method. The key to its success, however, resides in the application of Lemke's method to the resolution of the subproblems associated to the nodes of the tree generated by the Branch-and-Bound algorithm. Throughout the text, some heuristics are also introduced as a way to accelerate the performance of the method. The computational results acquired show that the proposed algorithm is efficient.
Mestrado
Otimização
Mestre em Matemática Aplicada

Стилі APA, Harvard, Vancouver, ISO та ін.

12

Belov, Gleb. "Problems, Models and Algorithms in One- and Two-Dimensional Cutting." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2004. http://nbn-resolving.de/urn:nbn:de:swb:14-1077284830765-13397.

Повний текст джерела

Анотація:

Within such disciplines as Management Science, Information and Computer Science, Engineering, Mathematics and Operations Research, problems of cutting and packing (C&P) of concrete and abstract objects appear under various specifications (cutting problems, knapsack problems, container and vehicle loading problems, pallet loading, bin packing, assembly line balancing, capital budgeting, changing coins, etc.), although they all have essentially the same logical structure. In cutting problems, a large object must be divided into smaller pieces; in packing problems, small items must be combined to large objects. Most of these problems are NP-hard. Since the pioneer work of L.V. Kantorovich in 1939, which first appeared in the West in 1960, there has been a steadily growing number of contributions in this research area. In 1961, P. Gilmore and R. Gomory presented a linear programming relaxation of the one-dimensional cutting stock problem. The best-performing algorithms today are based on their relaxation. It was, however, more than three decades before the first `optimum? algorithms appeared in the literature and they even proved to perform better than heuristics. They were of two main kinds: enumerative algorithms working by separation of the feasible set and cutting plane algorithms which cut off infeasible solutions. For many other combinatorial problems, these two approaches have been successfully combined. In this thesis we do it for one-dimensional stock cutting and two-dimensional two-stage constrained cutting. For the two-dimensional problem, the combined scheme provides mostly better solutions than other methods, especially on large-scale instances, in little time. For the one-dimensional problem, the integration of cuts into the enumerative scheme improves the results of the latter only in exceptional cases. While the main optimization goal is to minimize material input or trim loss (waste), in a real-life cutting process there are some further criteria, e.g., the number of different cutting patterns (setups) and open stacks. Some new methods and models are proposed. Then, an approach combining both objectives will be presented, to our knowledge, for the first time. We believe this approach will be highly relevant for industry.

Стилі APA, Harvard, Vancouver, ISO та ін.

13

Bringmann, Oliver. "Symbolische Interpretation Technischer Zeichnungen." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2003. http://nbn-resolving.de/urn:nbn:de:swb:14-1045648731734-96098.

Повний текст джерела

Анотація:

Gescannte und vektorisierte technische Zeichnungen werden automatisch unter Nutzung eines Netzes von Modellen in eine hochwertige Datenstruktur migriert. Die Modelle beschreiben die Inhalte der Zeichnungen hierarchisch und deklarativ. Modelle für einzelne Bestandteile der Zeichnungen können paarweise unabhängig entwickelt werden. Dadurch werden auch sehr komplexe Zeichnungsklassen wie Elektroleitungsnetze oder Gebäudepläne zugänglich. Die Modelle verwendet der neue, sogenannte Y-Algorithmus: Hypothesen über die Deutung lokaler Zeichnungsinhalte werden hierarchisch generiert. Treten bei der Nutzung konkurrierender Modelle Konflikte auf, werden diese protokolliert. Mittels des Konfliktbegriffes können konsistente Interpretationen einer kompletten Zeichnung abstrakt definiert und während der Analyse einer konkreten Zeichnung bestimmt werden. Ein wahrscheinlichkeitsbasiertes Gütemaß bewertet jede dieser alternativen, globalen Interpretationen. Das Suchen einer bzgl. dieses Maßes optimalen Interpretation ist ein NP-hartes Problem. Ein Branch and Bound-Algorithmus stellt die adäquate Lösung dar.

Стилі APA, Harvard, Vancouver, ISO та ін.

14

Oliveira, Lilian Kátia de. "Métodos exatos baseados em relaxação lagrangiana e surrogate para o problema de carregamento de paletes do produtor." Universidade Federal de São Carlos, 2004. https://repositorio.ufscar.br/handle/ufscar/3407.

Повний текст джерела

Анотація:

Made available in DSpace on 2016-06-02T19:50:17Z (GMT). No. of bitstreams: 1 TeseLKO.pdf: 834201 bytes, checksum: 994d7b70c6b1001f9dec962fafc8b72e (MD5) Previous issue date: 2004-12-13
Universidade Federal de Sao Carlos
The purpose of this work is to develop exact methods, based on Lagrangean and Surrogate relaxation, with good performance to solve the manufacturer s pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. Such methods involve a tree search procedure of branch and bound type and they use, in each node of the branch and bound tree, bounds derived from Lagrangean and/or Surrogate relaxations of a 0-1 linear programming formulation. Subgradient optimization algorithms are used to optimize such bounds. Problem reduction tests and Lagrangean and Surrogate heuristics are also applied in the subgradient optimization to obtain good feasible solution. Computational experiments were performed with instances from the literature and also real instances obtained from a carrier. The results show that the methods are able to solve these instances, on average, more quickly than other exact methods, including the software GAMS/CPLEX.
O objetivo deste trabalho é desenvolver métodos exatos, baseados em relaxação Lagrangiana e Surrogate, com bom desempenho para resolver o problema de carregamento de paletes do produtor. Tal problema consiste em arranjar ortogonalmente e sem sobreposição o máximo número de retângulos de dimensões ( , ) l w ou ( , ) w l sobre um retângulo maior ( , ) L W . Tais métodos exatos são procedimentos de busca em árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de relaxações Lagrangiana e/ou Surrogate de uma formulação de programação linear 0 1 − . Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes. São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e Surrogate na otimização do subgradiente para obter boas soluções factíveis. Testes computacionais foram realizados utilizando exemplos da literatura e exemplos reais, obtidos de uma transportadora. Os resultados mostram que os métodos são capazes de resolvê-los, em média, mais rapidamente do que outros métodos exatos, incluindo o software GAMS/CPLEX.

Стилі APA, Harvard, Vancouver, ISO та ін.

15

Alves, Alexsandro de Oliveira. "IntegraÃÃo de heurÃsticas lagrangeanas com algoritmos exatos para a otimizaÃÃo de particionamento de conjuntos." Universidade Federal do CearÃ, 2007. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1374.

Повний текст джерела

Анотація:

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico
Neste trabalho avaliamos mÃtodos heurÃsticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurÃsticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e mÃtodo de otimizaÃÃo pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiÃncia de nossas heurÃsticas na obtenÃÃo de limites inferiores e superiores de boa qualidade, em tempo computacional razoÃvel, para instÃncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instÃncias do PPC ÃÂotimalidade e para comprovar a qualidade dos resultados alcanÃados por nossas heurÃsticas.
In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem.

Стилі APA, Harvard, Vancouver, ISO та ін.

16

Alves, Alexsandro de Oliveira. "Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos." reponame:Repositório Institucional da UFC, 2007. http://www.repositorio.ufc.br/handle/riufc/16938.

Повний текст джерела

Анотація:

ALVES, Alexsandro de Oliveira. Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos. 2007. 49 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007.
Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:05:04Z No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5)
Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:08:40Z (GMT) No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5)
Made available in DSpace on 2016-05-20T18:08:40Z (GMT). No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) Previous issue date: 2007
In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem.
Neste trabalho avaliamos métodos heurísticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurísticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e método de otimização pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiência de nossas heurísticas na obtenção de limites inferiores e superiores de boa qualidade, em tempo computacional razoável, para instâncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instâncias do PPC à otimalidade e para comprovar a qualidade dos resultados alcançados por nossas heurísticas.

Стилі APA, Harvard, Vancouver, ISO та ін.

17

Mesyagutov, Marat. "Exact Approaches for Higher-Dimensional Orthogonal Packing and Related Problems." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2014. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-137905.

Повний текст джерела

Анотація:

NP-hard problems of higher-dimensional orthogonal packing are considered. We look closer at their logical structure and show that they can be decomposed into problems of a smaller dimension with a special contiguous structure. This decomposition influences the modeling of the packing process, which results in three new solution approaches. Keeping this decomposition in mind, we model the smaller-dimensional problems in a single position-indexed formulation with non-overlapping inequalities serving as binding constraints. Thus, we come up with a new integer linear programming model, which we subject to polyhedral analysis. Furthermore, we establish general non-overlapping and density inequalities and prove under appropriate assumptions their facet-defining property for the convex hull of the integer solutions. Based on the proposed model and the strong inequalities, we develop a new branch-and-cut algorithm. Being a relaxation of the higher-dimensional problem, each of the smaller-dimensional problems is also relevant for different areas, e.g. for scheduling. To tackle any of these smaller-dimensional problems, we use a Gilmore-Gomory model, which is a Dantzig-Wolfe decomposition of the position-indexed formulation. In order to obtain a contiguous structure for the optimal solution, its basis matrix must have a consecutive 1's property. For construction of such matrices, we develop new branch-and-price algorithms which are distinguished by various strategies for the enumeration of partial solutions. We also prove some characteristics of partial solutions, which tighten the slave problem of column generation. For a nonlinear modeling of the higher-dimensional packing problems, we investigate state-of-the-art constraint programming approaches, modify them, and propose new dichotomy and intersection branching strategies. To tighten the constraint propagation, we introduce new pruning rules. For that, we apply 1D relaxation with intervals and forbidden pairs, an advanced bar relaxation, 2D slice relaxation, and 1D slice-bar relaxation with forbidden pairs. The new rules are based on the relaxation by the smaller-dimensional problems which, in turn, are replaced by a linear programming relaxation of the Gilmore-Gomory model. We conclude with a discussion of implementation issues and numerical studies of all proposed approaches
Es werden NP-schwere höherdimensionale orthogonale Packungsprobleme betrachtet. Wir untersuchen ihre logische Struktur genauer und zeigen, dass sie sich in Probleme kleinerer Dimension mit einer speziellen Nachbarschaftsstruktur zerlegen lassen. Dies beeinflusst die Modellierung des Packungsprozesses, die ihreseits zu drei neuen Lösungsansätzen führt. Unter Beachtung dieser Zerlegung modellieren wir die Probleme kleinerer Dimension in einer einzigen positionsindizierten Formulierung mit Nichtüberlappungsungleichungen, die als Bindungsbedingungen dienen. Damit entwickeln wir ein neues Modell der ganzzahligen linearen Optimierung und unterziehen dies einer Polyederanalyse. Weiterhin geben wir allgemeine Nichtüberlappungs- und Dichtheitsungleichungen an und beweisen unter geeigneten Annahmen ihre facettendefinierende Eigenschaft für die konvexe Hülle der ganzzahligen Lösungen. Basierend auf dem vorgeschlagenen Modell und den starken Ungleichungen entwickeln wir einen neuen Branch-and-Cut-Algorithmus. Jedes Problem kleinerer Dimension ist eine Relaxation des höherdimensionalen Problems. Darüber hinaus besitzt es Anwendungen in verschiedenen Bereichen, wie zum Beispiel im Scheduling. Für die Behandlung der Probleme kleinerer Dimension setzen wir das Gilmore-Gomory-Modell ein, das eine Dantzig-Wolfe-Dekomposition der positionsindizierten Formulierung ist. Um eine Nachbarschaftsstruktur zu erhalten, muss die Basismatrix der optimalen Lösung die consecutive-1’s-Eigenschaft erfüllen. Für die Konstruktion solcher Matrizen entwickeln wir neue Branch-and-Price-Algorithmen, die sich durch Strategien zur Enumeration von partiellen Lösungen unterscheiden. Wir beweisen auch einige Charakteristiken von partiellen Lösungen, die das Hilfsproblem der Spaltengenerierung verschärfen. Für die nichtlineare Modellierung der höherdimensionalen Packungsprobleme untersuchen wir moderne Ansätze des Constraint Programming, modifizieren diese und schlagen neue Dichotomie- und Überschneidungsstrategien für die Verzweigung vor. Für die Verstärkung der Constraint Propagation stellen wir neue Ablehnungskriterien vor. Wir nutzen dabei 1D Relaxationen mit Intervallen und verbotenen Paaren, erweiterte Streifen-Relaxation, 2D Scheiben-Relaxation und 1D Scheiben-Streifen-Relaxation mit verbotenen Paaren. Alle vorgestellten Kriterien basieren auf Relaxationen durch Probleme kleinerer Dimension, die wir weiter durch die LP-Relaxation des Gilmore-Gomory-Modells abschwächen. Wir schließen mit Umsetzungsfragen und numerischen Experimenten aller vorgeschlagenen Ansätze

Стилі APA, Harvard, Vancouver, ISO та ін.

18

Bringmann, Oliver. "Symbolische Interpretation Technischer Zeichnungen." Doctoral thesis, Technische Universität Dresden, 2001. https://tud.qucosa.de/id/qucosa%3A24202.

Повний текст джерела

Анотація:

Gescannte und vektorisierte technische Zeichnungen werden automatisch unter Nutzung eines Netzes von Modellen in eine hochwertige Datenstruktur migriert. Die Modelle beschreiben die Inhalte der Zeichnungen hierarchisch und deklarativ. Modelle für einzelne Bestandteile der Zeichnungen können paarweise unabhängig entwickelt werden. Dadurch werden auch sehr komplexe Zeichnungsklassen wie Elektroleitungsnetze oder Gebäudepläne zugänglich. Die Modelle verwendet der neue, sogenannte Y-Algorithmus: Hypothesen über die Deutung lokaler Zeichnungsinhalte werden hierarchisch generiert. Treten bei der Nutzung konkurrierender Modelle Konflikte auf, werden diese protokolliert. Mittels des Konfliktbegriffes können konsistente Interpretationen einer kompletten Zeichnung abstrakt definiert und während der Analyse einer konkreten Zeichnung bestimmt werden. Ein wahrscheinlichkeitsbasiertes Gütemaß bewertet jede dieser alternativen, globalen Interpretationen. Das Suchen einer bzgl. dieses Maßes optimalen Interpretation ist ein NP-hartes Problem. Ein Branch and Bound-Algorithmus stellt die adäquate Lösung dar.

Стилі APA, Harvard, Vancouver, ISO та ін.

19

Amrani-Benhalima, Faïza. "Problèmes de MIN-MAX en variables 0-1 : Algorithmes de résolution exacts et approchés." Valenciennes, 1997. https://ged.uphf.fr/nuxeo/site/esupversions/6fb2c7ce-df58-4bc6-bb55-a1a7c0529fcf.

Повний текст джерела

Анотація:

Le problème de Minmax en variables continues ou en variables entières a toujours suscité un intérêt croissant d'une part, parce que son champs d'application est vaste. Que ce soit dans le domaine des mathématiques, l'allocation de ressource, l'économie, l'aéronautique et même des jeux. D'autres part, parce que les problèmes traités sont classés en théorie de la complexité comme NP-difficile même quand il s'agit d'un problème de Minmax en variables 0-1 sans contrainte et avec seulement deux objectifs. Cette thèse contribue à l'étude des problèmes en variables bivalentes. Elle propose la résolution exacte et approchée des problèmes de Minmax ou Maxmin en variables 0-1 qui consistent à minimiser un objectif exprimé sous la forme d'un minimum ou maximum de plusieurs fonctions linéaires et soumis à un ensemble de contraintes.

Стилі APA, Harvard, Vancouver, ISO та ін.

20

Belov, Gleb. "Problems, Models and Algorithms in One- and Two-Dimensional Cutting." Doctoral thesis, Technische Universität Dresden, 2003. https://tud.qucosa.de/id/qucosa%3A24305.

Повний текст джерела

Анотація:

Within such disciplines as Management Science, Information and Computer Science, Engineering, Mathematics and Operations Research, problems of cutting and packing (C&P) of concrete and abstract objects appear under various specifications (cutting problems, knapsack problems, container and vehicle loading problems, pallet loading, bin packing, assembly line balancing, capital budgeting, changing coins, etc.), although they all have essentially the same logical structure. In cutting problems, a large object must be divided into smaller pieces; in packing problems, small items must be combined to large objects. Most of these problems are NP-hard. Since the pioneer work of L.V. Kantorovich in 1939, which first appeared in the West in 1960, there has been a steadily growing number of contributions in this research area. In 1961, P. Gilmore and R. Gomory presented a linear programming relaxation of the one-dimensional cutting stock problem. The best-performing algorithms today are based on their relaxation. It was, however, more than three decades before the first `optimum? algorithms appeared in the literature and they even proved to perform better than heuristics. They were of two main kinds: enumerative algorithms working by separation of the feasible set and cutting plane algorithms which cut off infeasible solutions. For many other combinatorial problems, these two approaches have been successfully combined. In this thesis we do it for one-dimensional stock cutting and two-dimensional two-stage constrained cutting. For the two-dimensional problem, the combined scheme provides mostly better solutions than other methods, especially on large-scale instances, in little time. For the one-dimensional problem, the integration of cuts into the enumerative scheme improves the results of the latter only in exceptional cases. While the main optimization goal is to minimize material input or trim loss (waste), in a real-life cutting process there are some further criteria, e.g., the number of different cutting patterns (setups) and open stacks. Some new methods and models are proposed. Then, an approach combining both objectives will be presented, to our knowledge, for the first time. We believe this approach will be highly relevant for industry.

Стилі APA, Harvard, Vancouver, ISO та ін.

21

Blunck, Steffen. "Modellierung und Optimierung von Hub-and-Spoke-Netzen mit beschränkter Sortierkapazität." Karlsruhe : Univ.-Verl. Karlsruhe, 2005. http://deposit.d-nb.de/cgi-bin/dokserv?idn=97643962X.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

22

Moritz, Susanne. "A mixed integer approach for the transient case of gas network optimization." Phd thesis, [S.l.] : [s.n.], 2007. http://elib.tu-darmstadt.de/diss/000785.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

23

Homem, Thiago Pedro Donadon. "Procedimento híbrido envolvendo os métodos primal-dual de pontos interiores e branch and bound em problemas multiobjetivo de aproveitamento de resíduos de cana-de-açúcar /." Bauru : [s.n.], 2010. http://hdl.handle.net/11449/87192.

Повний текст джерела

Анотація:

Orientador: Antonio Roberto Balbo
Banca: Aparecido Nilceu Marana
Banca: Helenice de Oliveira F. Silva
Resumo: O Brasil é o maior produtor de cana-de-açúcar do mundo. Mas, existe uma grande preocupação com o sistema de colheita utilizado nesta cultura, pois é prática comum a colheita manual com a pré-queima do palhiço. Autoridades brasileiras têm aprovado leis proibindo a queimada nos canaviais. Entretanto, a colheita mecanizada, com cana-de-açúcar crua, cria novos problemas com a permanência do resíduo no solo. Assim, muitos estudos têm sido propostos para o uso deste resíduo para geração de energia. A maior dificuldade no uso desta biomassa está no custo de coletar e transferir o resíduo, do campo para o centro de processamento. Para análise da viabilidade deste sistema há a necessidade de um estudo do balanço de energia envolvido, devido ao grande número de maquinário utilizado no processo. O objetivo deste trabalho é investigar modelos matemáticos que auxiliem na escolha das variedades de cana-de-açúcar a serem implantadas, de forma a minimizar o custo de coleta da biomassa residual e avaliar o balanço de energia gerado, adicionado restrições sobre a produção de sacarose e limitações da área para plantio e considerando as distâncias entre os talhões e o centro de processamento. Para isto, técnicas de programação linear e inteira 0-1 foram utilizadas. A busca de soluções para problemas de programação inteira com grande número de variáveis e restrições é de difícil resolução, mas os resultados apresentados mostram que a utilização d eum procedimento híbrido envolvendo o método Primal-Dual de Pontos Interiores e o método Branch and Bound promove uma boa performance computacional, apresentando soluções confiáveis. Assim, o uso deste procedimento é viável para o auxílio na seleção de variedades, otimizando o custo do uso da biomassa residual de colheita ou o balanço de geração de energia
Abstract: It is that Brazil is the world's largest sugar cane producer. But there is great concern about the harvesting system used in this culture, because it is a common practice to burn the straw before the barvest. Brazilian authorities have approved laws prohibiting the burning in the sugar cane fields. However, with mechanized harvesting of sugar cane raw creates new problems with the accumulation of the waste biomass in the ground. Many studies have been proposed to use this waste for energy generation. The greatest difficulty to use this biomass is in the cost of collect and transfer the residues from the field to the the processing center. To analyze the feasibility of this system, it is necessary a study of the involved energy balance, because of the large number of machines in the process. The aim of this study is to investigate mathematical models that help on choosing varieties of sugar cane to be planted, to minimize the cost of collect of residual biomass and to analyze the balance of power generated, adding restrictions on the production on the production of sucrose and limitations on the area for planting and considering the distances among the plots the processing center. To this, techniques of 0-1 integer linear programming were used. The search for solutions to integer programming problems with many variables and constraints its very hard, but the results show that the use of a hybrid procedure involving the Primal-Dual Interior Point method and Branch and Bound method promotes good performance computing, with reliable solutions. Thus, the use of this procedure is feasible to help on select of varieties, optimizing the cost of collect of the waste biomass or the the balance of power generation
Mestre

Стилі APA, Harvard, Vancouver, ISO та ін.

24

Homem, Thiago Pedro Donadon [UNESP]. "Procedimento híbrido envolvendo os métodos primal-dual de pontos interiores e branch and bound em problemas multiobjetivo de aproveitamento de resíduos de cana-de-açúcar." Universidade Estadual Paulista (UNESP), 2010. http://hdl.handle.net/11449/87192.

Повний текст джерела

Анотація:

Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-08-24Bitstream added on 2014-06-13T18:07:18Z : No. of bitstreams: 1 homem_tpd_me_bauru.pdf: 3557697 bytes, checksum: a1fa6fe9ed118fd4c4f8be6400b6d78f (MD5)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
O Brasil é o maior produtor de cana-de-açúcar do mundo. Mas, existe uma grande preocupação com o sistema de colheita utilizado nesta cultura, pois é prática comum a colheita manual com a pré-queima do palhiço. Autoridades brasileiras têm aprovado leis proibindo a queimada nos canaviais. Entretanto, a colheita mecanizada, com cana-de-açúcar crua, cria novos problemas com a permanência do resíduo no solo. Assim, muitos estudos têm sido propostos para o uso deste resíduo para geração de energia. A maior dificuldade no uso desta biomassa está no custo de coletar e transferir o resíduo, do campo para o centro de processamento. Para análise da viabilidade deste sistema há a necessidade de um estudo do balanço de energia envolvido, devido ao grande número de maquinário utilizado no processo. O objetivo deste trabalho é investigar modelos matemáticos que auxiliem na escolha das variedades de cana-de-açúcar a serem implantadas, de forma a minimizar o custo de coleta da biomassa residual e avaliar o balanço de energia gerado, adicionado restrições sobre a produção de sacarose e limitações da área para plantio e considerando as distâncias entre os talhões e o centro de processamento. Para isto, técnicas de programação linear e inteira 0-1 foram utilizadas. A busca de soluções para problemas de programação inteira com grande número de variáveis e restrições é de difícil resolução, mas os resultados apresentados mostram que a utilização d eum procedimento híbrido envolvendo o método Primal-Dual de Pontos Interiores e o método Branch and Bound promove uma boa performance computacional, apresentando soluções confiáveis. Assim, o uso deste procedimento é viável para o auxílio na seleção de variedades, otimizando o custo do uso da biomassa residual de colheita ou o balanço de geração de energia
It is that Brazil is the world's largest sugar cane producer. But there is great concern about the harvesting system used in this culture, because it is a common practice to burn the straw before the barvest. Brazilian authorities have approved laws prohibiting the burning in the sugar cane fields. However, with mechanized harvesting of sugar cane raw creates new problems with the accumulation of the waste biomass in the ground. Many studies have been proposed to use this waste for energy generation. The greatest difficulty to use this biomass is in the cost of collect and transfer the residues from the field to the the processing center. To analyze the feasibility of this system, it is necessary a study of the involved energy balance, because of the large number of machines in the process. The aim of this study is to investigate mathematical models that help on choosing varieties of sugar cane to be planted, to minimize the cost of collect of residual biomass and to analyze the balance of power generated, adding restrictions on the production on the production of sucrose and limitations on the area for planting and considering the distances among the plots the processing center. To this, techniques of 0-1 integer linear programming were used. The search for solutions to integer programming problems with many variables and constraints its very hard, but the results show that the use of a hybrid procedure involving the Primal-Dual Interior Point method and Branch and Bound method promotes good performance computing, with reliable solutions. Thus, the use of this procedure is feasible to help on select of varieties, optimizing the cost of collect of the waste biomass or the the balance of power generation

Стилі APA, Harvard, Vancouver, ISO та ін.

25

Patel, Chirag B. "A multi-objective stochastic approach to combinatorial technology space exploration." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/29647.

Повний текст джерела

Анотація:

Thesis (Ph.D)--Aerospace Engineering, Georgia Institute of Technology, 2009.
Committee Chair: Dr. Dimitri N. Mavris; Committee Member: Dr. Brian J. German; Committee Member: Dr. Daniel P. Schrage; Committee Member: Dr. Frederic Villeneuve; Committee Member: Dr. Michelle R. Kirby; Committee Member: Ms. Antje Lembcke. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Стилі APA, Harvard, Vancouver, ISO та ін.

26

Stolpe, Mathias. "On Models and Methods for Global Optimization of Structural Topology." Doctoral thesis, KTH, Mathematics, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3478.

Повний текст джерела

Анотація:

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.

Keywords:topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.

Стилі APA, Harvard, Vancouver, ISO та ін.

27

Villela, Pedro Ferraz 1982. "Um algoritmo exato para obter o conjunto solução de problemas de portfólio." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307117.

Повний текст джерела

Анотація:

Orientador: Francisco de Assis Magalhães Gomes Neto
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica
Made available in DSpace on 2018-08-25T19:03:25Z (GMT). No. of bitstreams: 1 Villela_PedroFerraz_D.pdf: 10794575 bytes, checksum: 746b8aebf0db423d557d9c5fe1446592 (MD5) Previous issue date: 2014
Resumo: Neste trabalho, propomos um método exato para obter o conjunto solução de um problema biobjetivo quadrático de otimização de carteiras de investimento, que envolve variáveis binárias. Nosso algoritmo é baseado na junção de três algoritmos específicos. O primeiro encontra uma curva associada ao conjunto solução de problemas biobjetivo contínuos por meio de um método de restrições ativas, o segundo encontra o ótimo de um problema de programação quadrática inteira mista pelo método Branch-and-Bound, e o terceiro encontra a interseção de duas curvas associadas a problemas biobjetivo distintos. Ao longo do texto, algumas heurísticas e métodos adicionais também são introduzidos, com o propósito de acelerar a convergência do algoritmo proposto. Além disso, o nosso método pode ser visto como uma nova contribuição na área, pois ele determina, de forma exata, a curva associada ao conjunto solução do problemas biobjetivo inteiro misto, algo que é incomum na literatura, pois o problema alvo geralmente é abordado via métodos meta-heurísticos. Ademais, ele mostrou ser eficiente do ponto de vista do tempo computacional, pois encontra o conjunto solução do problema em poucos segundos
Abstract: In this work, we propose an exact method to find the solution set of a mixed quadratic bi-objective portfolio optimization problem. Our method is based on the combination of three specific algorithms. The first one obtains a curve associated with the solution set of a continuous bi-objective problem through an active set algorithm, the second one solves a mixed quadratic optimization problem through the Branch-and-Bound method, and the third one searches the intersection of two curves associated with distinct bi-objective problems. Throughout the text, some heuristics are also introduced in order to accelerate the performance of the method. Moreover, our method can be seen as a new contribution to the field, since it finds, in an exact way, the curve related to the solution set of the mixed integer bi-objective problem, something uncommon in the corresponding literature, where the target problem is usually approached by metaheuristic methods. Additionally, it has also shown to be efficient in terms of running time, being capable of finding the problem's solution set within a much faster time frame
Doutorado
Matematica Aplicada
Doutor em Matemática Aplicada

Стилі APA, Harvard, Vancouver, ISO та ін.

28

Stickel, Matthias. "Planung und Steuerung von Crossdocking-Zentren." Karlsruhe : Univ.-Verl. Karlsruhe, 2006. http://www.uvka.de/univerlag/volltexte/2006/184/.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

29

Beller, Thomas. "Zur Ablaufplanung bei zeitgesteuerten Feldbussystemen mit Funktionsblöcken /." [S.l. : s.n.], 1999. http://www.gbv.de/dms/ilmenau/toc/308225155.PDF.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

30

Degirmenci, Guvenc. "The Budget Constrained Discrete Time/cost Trade-off Problem In Project Networks." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/12609737/index.pdf.

Повний текст джерела

Анотація:

The time/cost trade-off models in project management aim to compress the project completion time by accelerating the activity durations at an expense of additional resources. The budget problem in discrete time/cost trade-off scheduling selects the time/cost mode -among the discrete set of specified modes- for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally, however each solution may have a different total cost value. In this study we aim to find the minimum cost solution among the optimal solutions of the budget problem. We analyze the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by linear programming relaxation and branch and bound based approximation and optimization algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the approximation algorithms produce high quality solutions. We also discuss the way our algorithms could be used to construct the time/cost trade-off curve.

Стилі APA, Harvard, Vancouver, ISO та ін.

31

Kämpf, Michael. "Probleme der Tourenbildung." Universitätsbibliothek Chemnitz, 2006. http://nbn-resolving.de/urn:nbn:de:swb:ch1-200601999.

Повний текст джерела

Анотація:

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

Стилі APA, Harvard, Vancouver, ISO та ін.

32

Santos, Marcio Costa. "Experimentos Computacionais com ImplementaÃÃes de Conjunto por EndereÃamento Direto e o Problema de Conjunto Independente MÃximo." Universidade Federal do CearÃ, 2013. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=12674.

Повний текст джерела

Анотація:

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior
A utilizaÃÃo de vetores de bits Ã prÃtica corrente na representaÃÃo de conjuntos por endereÃamento direto com o intuito de reduzir o espaÃo de memÃria necessÃrio e melhorar o desempenho de aplicaÃÃes com uso de tÃcnicas de paralelismo em bits. Nesta dissertaÃÃo, examinamos implementaÃÃes para representaÃÃo de conjuntos por endereÃamento direto. A estrutura bÃsica nessas implementaÃÃes Ã o vetor de bits. No entanto, alÃm dessa estrutura bÃsica, implementamos tambÃm duas variaÃÃes. A primeira delas consiste em uma estratificaÃÃo de vetores de bits, enquanto a segunda emprega uma tabela de dispersÃo. As operaÃÃes associadas Ãs estruturas implementadas sÃo a inclusÃo ou remoÃÃo de um elemento do conjunto e a uniÃo ou interseÃÃo de dois conjuntos. Especial atenÃÃo Ã dada ao uso de paralelismo em bits nessas operaÃÃes. As implementaÃÃes das diferentes estruturas nesta dissertaÃÃo utilizam uma interface e uma implementaÃÃo abstrata comuns, nas quais as operaÃÃes sÃo especificadas e o paralelismo em bits Ã explorado. A diferenÃa entre as implementaÃÃes estÃ apenas na estrutura utilizada. Uma comparaÃÃo experimental Ã realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente mÃximo. Duas abordagens sÃo utilizadas na implementaÃÃo de algoritmos enumerativos para o problema de conjunto independente mÃximo, ambas explorando o potencial de paralelismo em bits na representaÃÃo do grafo e na operaÃÃo sobre subconjuntos de vÃrtices. A primeira delas Ã um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o mÃtodo das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiÃncia quando empregado no cÃlculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais sÃo apresentados como forma de comparaÃÃo entre os dois algoritmos e como forma de avaliaÃÃo das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no mÃtodo das bonecas russas Ã mais eficiente quanto ao tempo de execuÃÃo e quanto ao consumo de memÃria. AlÃm disso, os resultados experimentais mostram tambÃm que o uso de estratificaÃÃo e tabelas de dispersÃo permitem ainda maior eficiÃncia no caso de grafos com muito vÃrtices e poucas arestas.
The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs.

Стилі APA, Harvard, Vancouver, ISO та ін.

33

Rieck, Julia. "Tourenplanung mittelständischer Speditionsunternehmen : Modelle und Methoden /." Wiesbaden : Gabler, 2008. http://d-nb.info/990563588/04.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

34

Takano, Mauricio Iwama. "Uma contribuição para o problema de programação de operações flow shop com buffer zero e tempos de setup dependente da sequência e da máquina." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/18/18156/tde-16032017-104814/.

Повний текст джерела

Анотація:

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases.
Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

Стилі APA, Harvard, Vancouver, ISO та ін.

35

Lê, Thi Hoai An. "Analyse numérique des algorithmes de l'optimisation D. C. . Approches locale et globale. Codes et simulations numériques en grande dimension. Applications." Rouen, 1994. http://www.theses.fr/1994ROUES047.

Повний текст джерела

Анотація:

Cette thèse est consacrée à l'analyse qualitative et quantitative de l'optimisation d. C. (différence de deux fonctions convexes). Le chapitre I est destiné à l'étude générale de la théorie et des algorithmes de l'optimisation d. C. - approche locale. Dans le chapitre II nous nous intéressons à la fois à l'étude théorique (la dualité lagrangienne, conditions d'optimalité) et algorithmique (algorithmes globaux, DCA) du problème de minimisation d'une forme quadratique sur une boule ou une sphère euclidienne. Nous présentons dans le chapitre III deux nouvelles méthodes (méthode globale de type branch and bound et DCA) pour la minimisation d'une forme quadratique indéfinie sur un polyèdre convexe. La résolution du problème d'optimisation multicritère par DCA via la pénalité exacte et par un algorithme global de type branch and bound fait l'objet du chapitre IV. Le chapitre V concerne le traitement du problème multidimensionnel des tableaux de dissimilarités (MDS) par DCA. La résolution du problème de calcul des valeurs propres extrêmes d'une matrice réelle symétrique par DCA est étudiée dans le chapitre VI. Enfin, dans le dernier chapitre nous étudions une méthode globale d'optimisation d. C. Et son application à la résolution d'un problème industriel d'optimisation non convexe de Pool carburant

Стилі APA, Harvard, Vancouver, ISO та ін.

36

Balau, Adriano Pereira. "Uso de métodos heurísticos e branch-and-bound para otimização do layout fabril da linha de montagem de um componente automotivo na região de Curitiba." Universidade Tecnológica Federal do Paraná, 2013. http://repositorio.utfpr.edu.br/jspui/handle/1/842.

Повний текст джерела

Анотація:

As empresas de manufatura, nos dias atuais, estão incessantemente em busca de redução de custos, motivadas pela concorrência e competição, que são características fortes da globalização. No Sistema Toyota de Produção (OHNO, 1988) é ressaltada a questão dos sete desperdícios que podem existir em um processo e que, consequentemente, geram custos no produto sem, contudo agregar valor ao mesmo. Um dos desperdícios mais comumente encontrados são os do fluxo do produto semiacabado (WIP), matéria-prima ou produto acabado. O estudo de Layout visa otimizar a disposição dos recursos dentro de um processo de modo a minimizar, entre outros, o fluxo de materiais. O presente estudo visa apresentar um caso real de uma grande empresa de autopeças na região de Curitiba, PR, que gasta milhões por ano em mudanças de Layout. O objeto de estudo é a linha de montagem de um determinado componente que esta empresa fabrica. Através do uso de Métodos Heurísticos propõe-se uma abordagem para a otimização do Layout desta linha de montagem. Esta abordagem foi dividida em duas etapas. Na primeira etapa, foi resolvido o problema de formação de células (visando melhorar os tempos computacionais, bem como a qualidade da solução), visando associar as máquinas disponíveis às peças a serem fabricadas. Na segunda etapa, resolve-se o problema de otimização do layout, considerando as associações de máquinas às peças feitas na primeira etapa. Nas duas etapas testou-se o uso de uma abordagem meta-heurística (busca tabu) híbrida, bem como o método exato denominado Branch-and-Bound (este na primeira etapa), para resolver o problema. Os resultados encontrados no arranjo físico das máquinas mostraram-se bastante promissores.
Nowadays, the manufacturing enterprises are constantly looking for costs reduction, driven by rivalry and competition, which are strong globalization characteristics. In the Toyota Production System (OHNO, 1988), are highlighted the seven wastes which can exist in a manufacturing process and that, consequently, generate costs to the product without, however, adding value to it. Some commonly found wastes are the work-in-process (WIP), raw material or finished products flow wastes. The layout study aims to optimize the layout of facilities inside a process to minimize, among others, the materials flow. This study aims to present a real case of a huge auto parts manufacturer enterprise located in Curitiba, PR, which spends millions a year on layout changes. The object of study is the assembly line of a specifical component that this company manufactures. Using Heuristic methods, it proposes an approach for the layout optimizing of this assembly line. This approach was divided in two stages: in the first one, the cell formation problem (in order to improve the computational time, as well as the solution quality) was solved in order to associate machines to parts. In the second stage, the layout optimizing problem is solved, considering the combination of machines to parts (made in first stage). In both stages the hybrid meta-heuristics approach (tabu search), as well as the Exact method so called Branch-and-Bound (this on first stage), were tested to solve this problem. The results found on layout of facilities were quite promising.

Стилі APA, Harvard, Vancouver, ISO та ін.

37

Doležal, Zbyněk. "Optimalisace výrobně-montážní linky." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2011. http://www.nusl.cz/ntk/nusl-229803.

Повний текст джерела

Анотація:

This work deals with the way of balancing production-assembly line, which would minimalize set up costs. The production-assembly line shall allow assembling more mutually similar variants of the same product. The time of duration of each operation is constant, but can differs between individual variants of the product. Cycle time is related to the variant of the product.

Стилі APA, Harvard, Vancouver, ISO та ін.

38

Thai, Quynh Phong. "Analyse numérique des méthodes d'optimisation globale. Codes et simulations numériques. Applications." Rouen, 1994. http://www.theses.fr/1994ROUES069.

Повний текст джерела

Анотація:

Cette thèse est consacrée à l'étude des méthodes de résolution des problèmes d'optimisation globale y compris leur implémentation sur ordinateur, les simulations numériques et aussi les applications de ces méthodes à certains problèmes industriels. Une revue systématique des techniques fondamentales utilisées en optimisation globale déterministe est présentée. Sur la base de ces techniques, des algorithmes de type approximation extérieure et séparation & évaluation sont élaborés pour la résolution de certaines classes importantes de problèmes d'optimisation globale qui font l'objet d'une recherche extensive pendant ces dernières années: programmation anti-convexe, programmation D. C. (différence de fonctions convexes), programmation quadratique. Ces méthodes sont ensuite appliquées à un problème industriel important, celui de pool carburant. D'autre part, une technique de décomposition est proposée pour traiter une classe de problèmes comportant des fonctions bilinéaires et quadratiques. Enfin, dans le dernier chapitre, nous présentons la résolution d'un problème fondamental dans la vision par ordinateur par la méthode de région de confiance, une méthode robuste et fiable pour la minimisation sans contrainte

Стилі APA, Harvard, Vancouver, ISO та ін.

39

Borba, Leonardo de Miranda. "Exact and heuristic methods for heterogeneous assembly line balancing problems of type 2." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2018. http://hdl.handle.net/10183/172211.

Повний текст джерела

Анотація:

A diferença entre estações de trabalho é considerada desprezível em linhas de montagem tradicionais. Por outro lado, linhas de montagem heterogêneas consideram o problema de indústrias nas quais os tempos das tarefas variam de acordo com alguma característica a ser selecionada para a tarefa. No Problema de Balanceamento e Atribuição de Trabalhadores em Linhas de Montagem (do inglês Assembly Line Worker Assignment and Balancing Problem, ALWABP), os trabalhadores são responsáveis por estações de trabalho e de acordo com as suas habilidades, eles executam as tarefas em diferentes quantidades de tempo. Em alguns casos, os trabalhadores podem até ser incapazes de executar algumas tarefas. No Problema de Balanceamento de Linhas de Montagem Robóticas (do inglês Robotic Assembly Line Balancing Problem, RALBP), há diferentes tipos de robôs e o conjunto de tarefas de cada estação deve ser executada por um robô. Robôs do mesmo tipo podem ser usados múltiplas vezes. Nós propomos métodos exatos e heurísticos para a minimização do tempo de ciclo destes dois problemas, para um número fixo de estações. Os problemas têm características similares que são exploradas para produzir limitantes inferiores, métodos inferiores, models de programação inteira mista, e regras de redução e dominância. Para a estratégia de ramificação do método de branch-and-bound, entretanto, as diferenças entre os problemas forçam o uso de dois algoritmos diferentes. Uma estratégia orientada a tarefas tem os melhores resultados para o ALWABP-2, enquanto uma estratégia orientada a estações tem os melhores resultados para o RALBP-2. Nós mostramos que os limitantes inferiores, heurísticas, modelos de programação inteira mista e algoritmos de branch-and-bound para estes dois problemas são competitivos com os métodos do estado da arte da literatura.
The difference among workstations is assumed to be negligible in traditional assembly lines. Heterogeneous assembly lines consider the problem of industries in which the task times vary according to some property to be selected for the task. In the Assembly Line Worker Assignment and Balancing Problem (ALWABP), workers are assigned to workstations and according to their abilities, they execute tasks in different amounts of time. In some cases they can even be incapable of executing some tasks. In the Robotic Assembly Line Balancing Problem (RALBP) there are different types of robots and each station must be executed by a robot. Multiple robots of the same type may be used. We propose exact and heuristic methods for minimizing the cycle time of these two problems, for a fixed number of stations. The problems have similar characteristics that are explored to produce lower bounds, heuristic methods, mixed-integer programming models, and reduction and dominance rules. For the branching strategy of the branch-and-bound method, however, the differences among the problem force the use of two different algorithms. A task-oriented strategy has the best results for the ALWABP-2 while a station-oriented strategy has the best results for the RALBP-2. The lower bounds, heuristics, MIP models and branch-and-bound algorithms for these two problems are shown to be competitive with the state-of-the-art methods in the literature.

Стилі APA, Harvard, Vancouver, ISO та ін.

40

Turpin, Heather Jane. "The branch-and-bound paradigm." Thesis, University of East Anglia, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.277168.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

41

Kooli, Anis. "Exact and heuristic methods for resource constrained project scheduling problem." Thesis, Tours, 2012. http://www.theses.fr/2012TOUR4031/document.

Повний текст джерела

Анотація:

Le problème de gestion de projet à contraintes de ressources est un des problèmesles plus étudiés dans la littérature. Il consiste à planifier des activités soumises à desrelations de précédence, et nécessitant des ressources renouvelables. L’objectif est deminimiser la durée du projet, soit le makespan. Nous étudions le problème de gestion deprojet à contraintes de ressources. Nous nous sommes intéressées à la résolution exactedu problème. Dans la première partie de la thèse, nous élaborons une série de bornesinférieures basées sur le raisonnement énergétique et des formulations mathématiques.Les résultats montrent que les bornes proposées surpassent ceux de la littérature. Dansla deuxième partie, nous proposons des procédures par séparation et évaluation utilisantles bornes inférieures dévelopées dans la première partie
Resource Constrained Project Scheduling Problem is one of the most studied schedulingproblems in the literature. It consists in scheduling activities, submitted to precedencerelationship, and requiring renewable resources to be processed. The objective isto minimize the project duration, i.e., the makespan. We study the Resource ConstrainedProject Scheduling Problem. We are interested on the exact resolution of the problem.In the first part of the thesis, we develop a series of lower bounds based on energeticreasoning and mathematical formulations. The computational results show that theproposed lower bounds outperform the ones of the literature. In the second part, wepropose Branch-and-Bound procedures using the lower bounds developed on the firstpart

Стилі APA, Harvard, Vancouver, ISO та ін.

42

Sands, William Alvah. "Phylogenetic Inference Using a Discrete-Integer Linear Programming Model." University of Akron / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=akron1492783280743802.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

43

Axehill, Daniel. "Applications of Integer Quadratic Programming in Control and Communication." Licentiate thesis, Linköping : Dept. of Electrical Engineering, Linköping University, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-5263.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

44

Rider, Flores Marcos Julio 1975. "Planejamento da expansão de sistemas de transmissão usando os modelos CC - CA e tecnicas de programação não-linear." [s.n.], 2006. http://repositorio.unicamp.br/jspui/handle/REPOSIP/260508.

Повний текст джерела

Анотація:

Orientador: Ariovaldo Verandio Garcia, Ruben Augusto Romero Lazaro
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
Made available in DSpace on 2018-08-06T06:56:43Z (GMT). No. of bitstreams: 1 RiderFlores_MarcosJulio_D.pdf: 1021887 bytes, checksum: 6000961c2f5457b410ac691912476270 (MD5) Previous issue date: 2006
Resumo: Neste trabalho são propostos modelos matemáticos e técnicas de solução para resolver o problema de planejamento da expansão de sistemas de transmissão através de três enfoques. a) Usando o modelo de corrente alternada do sistema de transmissão e um algoritmo heurístico construtivo especializado para resolver o problema de planejamento, e, ainda, realiza-se uma primeira tentativa de alocação de fontes de potência reativas; b) Usando o modelo de corrente contínua e técnicas de programação não-linear especializadas. Nesse caso emprega-se uma versão relaxada do problema de planejamento da expansão de sistemas de transmissão usando o modelo de corrente contínua, onde a integralidade das variáveis de investimento é desprezada. Resolve-se o problema de programação não-linear, modelado de forma matricial com um algoritmo de otimização especializado e, além disso, um algoritmo heurístico construtivo especializado é utilizado para resolver o problema de planejamento. c) Usando o modelo de corrente contínua e um algoritmo Branch and Bound (B&B) sem empregar técnicas de decomposição. Para isso foram redefinidos os chamados testes de sondagem no algoritmo B&B e em cada nó da árvore de B&B tem-se um problema de programação não-linear que são resolvidos usando a metodologia desenvolvida no item (b). Os ítens (a), (b) e (c) requerem a solução de problemas de programação não-linear diferenciados. Uma revisão das características principais da resolução iterativa dos métodos de pontos interiores é apresentada. Foi desenvolvida uma técnica baseada em uma combinação de métodos de pontos interiores de alta ordem (MPI-AO) para resolver os problemas de programação não-linear de forma rápida, eficiente e robusta. Essa combinação dos MPI-AO tem como objetivo colocar num único método as características particulares de cada um dos MPI-AO e melhorar o desempenho computacional comparado com os MPI-AO de forma individual
Abstract: In this work mathematical models and solution techniques are proposed to solve the power system transmission expansion planning problem through three approaches: a) Using the nonlinear model ofthe transmission system (AC model) and a specialized constructive heuristic algorithm to solve the problem and, yet, a first attempt to allocate reactive power sources is also considered; b) Using the direct-current (DC) model and specialized techniques of nonlinear programming. In this case a version of the power system transmission expansion planning problem using the DC model where the integrality of the investment variables is relaxed is used. The nonlinear programming problem is solved with a specialized optimization algorithm and, moreover, a constructive heuristic algorithm is employed to solve the planning problem. c) Using the DC model and Branch and Bound (B&B) algorithm without the use of decomposition techniques. The so called fathoming tests of the B&B were redefined and at each node of the tree a nonlinear programming problem is solved using the method developed in b). Items a), b) and c) require the solution of distinct problems of nonlinear programming. A revision of the main characteristics of the iterative solution of the interior points methods is presented. An optimization technique based on a combination of the higher order interior point methods (HO-IPM) had been developed to solve the nonlinear programming problems in a fast, efficient and robust way. This combination of the HO-IPM has as objective to explore the particular characteristics of each method in a single one and to improve the comparative computational performance with the HO-IPM of individual form
Doutorado
Energia Eletrica
Doutor em Engenharia Elétrica

Стилі APA, Harvard, Vancouver, ISO та ін.

45

Ібнухсейн, Інес. "Інформаційна система підтримки діяльності дитячого хору (комплексна тема). Загальна частина. Підсистема підтримки діяльності користувача. Індивідуальна частина № 1". Bachelor's thesis, КПІ ім. Ігоря Сікорського, 2020. https://ela.kpi.ua/handle/123456789/39066.

Повний текст джерела

Анотація:

Загальна частина (С. 1-147) та Індивідуальна частина № 1 (С. 148-235) комплексного дипломного проєкту на здобуття ступеня бакалавра на тему «Інформаційна система підтримки діяльності дитячого хору» (автори: Ібнухсейн Інес, Суворова Валерія Євгеніївна). Індивідуальна частина № 2: https://ela.kpi.ua/handle/123456789/39067
Загальна частина Структура та обсяг роботи. Пояснювальна записка дипломного проєкту складається з шести розділів, містить 11 рисунків, 11 таблиць, 1 додаток, 17 джерел. Дипломний проєкт присвячений розробці інформаційної системи підтримки діяльності дитячого хору. Цілі розробки – це популяризація діяльності хору «Щедрик» в Україні та за її межами та створення та автоматизація процесу складання розкладів прослуховувань та концертних виступів. У розділі загальних положень представлено опис предметного середовища, розглянуто наявні аналоги, сформульовано постановку задачі. У розділі інформаційного забезпечення описано вихідні дані для користувача та адміністратора, а також для програм, які будуть складати розклад прослуховувань та концертних виступів. Також наведено опис структури бази даних. Розділ математичного забезпечення присвячений порівняльному аналізу методів знаходження оптимального розкладу та вибрано кращий. У розділі програмного забезпечення описано технології, які було використано для розробки дипломного проєкту, наведено діаграми класів, послідовності та компонентів, описано специфікацію функцій. У технологічному розділі наведено керівництво користувача для розробленого застосування. Індивідуальна частина № 1 Структура та обсяг роботи. Пояснювальна записка дипломного проєкту складається з шести розділів, містить 14 рисунків, 6 таблиць, 1 додаток, 5 джерел. Дипломний проєкт присвячений розробці інформаційної системи для підтримки діяльності дитячого хору. Цілі розробки – це популяризація діяльності хору «Щедрик» в Україні та за її межами та створення та автоматизація процесу складання розкладів прослуховувань та концертних виступів. У розділі загальних положень представлено опис функціональної моделі з боку користувача, наведено діаграму варіантів використання для користувача. У розділі інформаційного забезпечення описано вхідні дані для користувача. Розділ математичного забезпечення присвячений аналізу такого методу знаходження оптимального розкладу, як Променевий пошук, розроблено алгоритм пошуку оптимального розкладу даним методом. У технологічному розділі представлено керівництво користувача для користувацької частини системи, а також проведено тестові випробування для програмного продукту з боку користувача.
The common part Structure and scope of work. The explanatory note of the diploma project consists of six sections, contains 11 figures, 11 tables, 1 appendix, 17 sources. The diploma project is devoted to the development of an information system to support the activities of the children's choir. The goals of the development are to popularize the activities of the Shchedryk Choir in Ukraine and abroad and to create and automate the process of scheduling auditions and concert performances. In the section of general provisions the description of the subject environment is presented, the available analogues are considered, the statement of a problem is formulated. The information support section describes the initial data for the user and the administrator, as well as for the programs that will schedule auditions and concert performances. A description of the database structure is also given. The section of mathematical support is devoted to the comparative analysis of methods of finding the optimal schedule and the best one is chosen. The software section describes the technologies that were used to develop the thesis project, provides diagrams of classes, sequences and components, describes the specification of functions. The technology section provides a user guide for the developed application. The individual part 1 Structure and scope of work. The explanatory note of the diploma project consists of six sections, contains 14 figures, 6 tables, 1 appendix, 5 sources. The diploma project is devoted to the development of an information system to support the activities of the children's choir. The goals of the development are to popularize the activities of the Shchedryk Choir in Ukraine and abroad and to create and automate the process of scheduling auditions and concert performances. In the section of general provisions the description of functional model from the user is presented, the diagram of variants of use for the user is resulted. The information section describes the input data for the user. The section of mathematical software is devoted to the analysis of such method of finding the optimal schedule as Radial search, the algorithm of search of the optimal schedule by this method is developed. The technological section presents a user manual for the user part of the system, as well as tests for the software product by the user.

Стилі APA, Harvard, Vancouver, ISO та ін.

46

Rahman, Mostafizur. "Branch and Bound Algorithm for Multiprocessor Scheduling." Thesis, Högskolan Dalarna, Datateknik, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:du-3790.

Повний текст джерела

Анотація:

The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound algorithm for the multiprocessor schedulingproblem. We investigate the algorithm by comparing two different lower bounds withtheir computational costs and the size of the pruned tree.Several experiments are made with small set of problems and results are compared indifferent sections.

Стилі APA, Harvard, Vancouver, ISO та ін.

47

Turkensteen, Marcel. "Advanced analysis of branch and bound algorithms." [S.l. : [Groningen : s.n.] ; University Library Groningen] [Host], 2006. http://irs.ub.rug.nl/ppn/299139158.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

48

Guilbeau, Jared T. "A Vector Parallel Branch and Bound Algorithm." Thesis, University of Louisiana at Lafayette, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10242153.

Повний текст джерела

Анотація:

Global optimization problems sometimes attain their extrema on infinite subsets of the search space, forcing mathematically rigorous programs to require large amounts of data to describe these sets. This makes these programs natural candidates for both vectorization methods and parallel computing. Here, we give a brief overview of parallel computing and vectorization methods, exploit their availability by constructing a fully distributed implementation of a mathematically rigorous Vector Parallel Branch and Bound Algorithm using MATLAB’s SPMD architecture and interval arithmetic, and analyze the performance of the algorithm across different methods of inter-processor communication.

Стилі APA, Harvard, Vancouver, ISO та ін.

49

Farias, Denilson Atilio Godry. "Paralelização da Técnica Branch and Bound com PVM." reponame:Repositório Institucional da UFPR, 2011. http://hdl.handle.net/1884/25089.

Повний текст джерела

Анотація:

Resumo: Este trabalho aborda a implementação paralela da técnica Branch-and-Bound em problemas de otimização combinatoria, especificamente busca em grafos. E utilizado na implementação o modelo de programação paralela por troca de mensagens com o uso da biblioteca Parallel Virtual Machine (PVM) sobre o sistema operacional Linux em uma arquitetura multicomputador. E analisado o comportamento da técnica Branch-and-Bound, em particular a relação entre (a) três critérios de busca, (b) a utilização dos recursos de memória e (c) granularidade de, processamento e comunicação entre processos. E proposto um esquema de implementação com processos mestre-escravos semi-distribuído, onde o processo mestre é responsável pela distribuição de tarefas e os processos escravos pela disseminação de resultados parciais no sistema. Resultados experimentais dessa implementação são exibidos e analisados, assim como algumas características relevantes ao desempenho global encontradas no uso da biblioteca PVM para esta arquitetura. De um modo geral obtivemos em média para os problemas investigados uma eficiência da execução paralela da ordem de 98% em comparação à execução serial.

Стилі APA, Harvard, Vancouver, ISO та ін.

50

Abdul-Razaq, Tariq S. "Machine scheduling problems : a branch and bound approach." Thesis, Keele University, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.328587.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Дисертації з теми "Method of «branch and bound»"

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями