Polynomial programming, a class of non-linear programming where the objective and the constraints are multivariate polynomials, has attracted the attention of many researchers in the past decade. Polynomial programming is a powerful modeling tool that captures various optimization models. Due to the wide range of applications, a research topic of high interest is the development of computationally efficient algorithms for solving polynomial programs. Even though some solution methodologies are already available and have been studied in the literature, these approaches are often either problem specific or are inapplicable for large-scale polynomial programs. Most of the available methods are based on using hierarchies of convex relaxations to solve polynomial programs; these schemes grow exponentially in size becoming rapidly computationally expensive. The present work proposes methods and implementations that are capable of solving polynomial programs of large sizes. First we propose a general framework to construct conic relaxations for binary polynomial programs, this framework allows us to re-derive previous relaxation schemes and provide new ones. In particular, three new relaxations for binary quadratic polynomial programs are presented. The first two relaxations, based on second-order cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of non-convex binary quadratic polynomial problems. The third relaxation is based purely on second-order cone programming, it outperforms the semidefinite-based relaxations that are proposed in the literature in terms of computational efficiency while being comparable in terms of bounds. To strengthen the relaxations further, a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs is presented. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. The scheme can be used on any initial relaxation of the polynomial program whether it is second-order cone based or semidefinite based relaxations. The proposed scheme is specialized for binary polynomial programs and is in principle scalable to large general combinatorial optimization problems. In the case of binary polynomial programs, the proposed scheme converges to the global optimal solution under mild assumptions on the initial approximation of the binary polynomial program. Finally, for binary polynomial programs the proposed relaxations are integrated with the dynamic scheme in a branch-and-bound algorithm to find global optimal solutions.

In this study, a single machine batch-scheduling problem with incompatible jobs and dynamic arrivals is examined. The objective function is the minimization of the total flow time of the jobs. For solving problems a case specific branch and bound algorithm with a heuristic upper bound scheme and two alternative lower bound procedures is used. An extensive computational experiment is conducted to investigate the effects of certain parameters on the computation time. For the most difficult parameter combination branch and bound algorithm can solve the problems about 25 jobs with 4 different job types in a 10 minutes time on average. For the problem types with higher number of jobs and the most difficult parameter combination proposed upper bound heuristic can be used to obtain near optimal solutions.

In this study, we address job sequencing and tool switching problem arising in Flexible Manufacturing Systems. We consider a single machine with limited tool slots on its tool magazine. The available tool slots cannot accommodate all the tools required by all jobs, therefore tool switches between jobs are required. A single tool transporter with limited capacity is used in transporting the tools from the storage area to the machine. Our aim is to minimize the number of tool transporter movements. We provide two mixed integer linear programming formulations of the problem, one of which is based on the traveling salesman problem. We develop a Branch-and-Bound algorithm powered with various lower and upper bounding techniques for optimal results. In order to obtain good solutions in reasonable times, we propose Beam Search algorithms. Our computational results reveal the satisfactory performance of the B&amp / B algorithm for moderate sized problems. Moreover, Beam Search techniques perform well for large-sized problems.

In this thesis, we develop an exact algorithm for an assembly line balancing problem with equipment selection decisions. Two objectives are considered: minimizing the total equipment costs and the number of workstations. Our aim is to choose the type of the equipment(s) in every workstation and determine the assignment of the tasks to each workstation and equipment type. We aim to propose a set of efficient solutions for each problem and leave the choice of the best solution to the decision maker&rsquo / s preferences. A branch and bound algorithm is developed whose efficiency is increased with some dominance rules and powerful lower bounds. Moreover, modified ranked positional weight heuristic method is used as initial upper bound. The effectiveness of the proposed procedure is demonstrated by computational analysis in which the effects of changing certain parameter values are investigated. We find that our algorithm is capable of solving the problem instances with up to 25 tasks and 5 equipments.

In this study, we consider the disassembly problem of end-of-life (EOL) products for recovering valuable parts or assemblies. All parts obtained by disassembly processes of an EOL product may not be profitable due to their high recovery costs. Our problem is to select the parts to be released and determine the associated disassembly tasks so as to maximize the total profit. We first tackle the simple part selection problem, and then introduce a time constraint for the tasks to be performed for selected parts and search for incomplete time constrained sequences. We formulate our first problem as a Mixed Integer Problem and show that the constraint set of this formulation is totally unimodular. We also provide the dual formulation of our problem and its interpretation. For time-constrained part selection problem we propose a branch-and-bound algorithm. We first develop some reduction mechanism to reduce the size of the problem. Our solution procedure is capable of solving problems with up to 94 parts and tasks.

Thesis (Ph. D.)--Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 121-128).

Universiẗat, Diss., 2006--Karlsruhe.

Thesis (M.S.) -- Mississippi State University. Department of Computer Science and Engineering. / Title from title screen. Includes bibliographical references.

Olofsfors AB beställer idag stålplåtar, remsor och stänger av stålleveran- törer för sin produktion av skop- och vägstål samt skogsband. Stålremsorna för produktion av skop- och vägstål beställs i dimensioner som är redo att skä- ras endimensionellt och vidarebehandlas till skopstålsdetaljer i fabriken. För att effektivisera produktionen i form av ekonomibesparingar och minskning av spill har Olofsfors AB köpt en ny maskin som kan behandla större plåtar och skära ut mindre remsor från dessa och de kan således göra ekonomiska besparingar tack vare billigare inköp. Företaget vill hitta en metod som minimerar spill av material vilket ska leda till ekonomiska besparingar. Syftet med projektet är att utveckla ett program som Olofsfors AB kan använda sig av i den dagliga verksamheten för att optimera materialanvändningen. Problemet att skära ut mindre bitar ur ett större råmaterial är vanligt i industrier och kallas Cutting stock problem. Vi har använt oss av en redan utvecklad modell bestående av en modifierad branch & bound-algoritm för att hitta möjliga mönster som kan skäras ut ur råmaterialet, implementerat den i MATLAB® samt förbättrat den. Vidare har det använts fyra olika optimeringsmodeller vilka lett till olika heltalsprogram som samtliga lösts med den inbyggda MATLAB®-metoden intlinprog, vilken använder sig av branch & bound som lösningsmetod. Resultatet gav ett för användaren lättanvänt program som ger förslag på en optimal dimension bland en mängd möjliga dimensioner på ett råmate- rial, utifrån årsvolym och dimensioner för remsor eller stänger. Föreslagen dimension är den dimension som resulterar i så låg materialförbrukning som möjligt. Utöver detta kan Olofsfors AB använda detta program för att hitta vilka mönster som ska skäras ut givet efterfrågan, samt använda utdata från programmet för att reda ut kapacitetsgräns i restbitslager och finna vilka lagerartiklar som är särskilt lämpliga att producera från restbitar.

O objetivo desse trabalho é o de estudar o problema de programação de tarefas num ambiente produtivo com uma única máquina com data comum de entrega. Nesse caso, as tarefas, depois de processadas uma única vez na máquina, devem ser entregues em uma data comum e sofrem penalidades de adiantamento e de atraso conforme o instante em que são completadas. Na prática, esse problema é encontrado em casos de pedidos de lotes de produtos com data de entrega comum préespecificada, embarques para exportação e material químico ou misturas que têm vida média de curta duração. Problemas desse tipo são NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991), sendo comumente tratados na literatura através de heurísticas e meta-heurísticas. Visto não ser de nosso conhecimento a existência na literatura de tratamento desse problema através de métodos exatos, propôs-se a utilização de um algoritmo do tipo branch-and-bound para obtenção da solução ótima do problema que minimize a soma das penalidades de adiantamento e de atraso. No desenvolvimento do algoritmo, a utilização de propriedades do problema foi importante na elaboração de limitantes inferiores e regras de dominância que melhoraram a eficiência do modelo. Os experimentos realizados avaliaram o desempenho de diferentes critérios elaborados, como escolha do nó pai, limitante inferior, ordem de execução das estratégias e ordem de construção da seqüência. Os resultados obtidos mostraram-se robustos quando comparados com o benchmark da literatura e revelaram o bom desempenho do modelo para problemas de pequeno porte, superando o desempenho de programas de otimização comerciais. / The objective of this work is to study the single-machine scheduling problem with a common due date. In this case, jobs, after be processed only once in the machine, must be delivered in a common due date and they are penalized of earliness or tardiness according to their completion time. This problem is found in cases of batch production with prespecified common due date, exportation shipping and chemical material that has short half-life period. This kind of problem is NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991) and it has been treated in the literature by heuristics and meta-heuristics. Not having knowledge about previous treatment by exact methods in the literature, it was proposed the implementation of a branch-and-bound algorithm to obtain the optimal solution that minimizes the total weighted earliness and tardiness penalties. In the development of the algorithm, the utilization of problem properties was important to the elaboration of lower bounds and pruning rules that have enhanced the efficiency of the model. The realized tests have evaluated the performance of different criteria, like the choice of father node, lower bound, strategy execution order and sequence construction order. The obtained results have demonstrated robustness comparing to benchmark and they have revealed the good working of the model for small problems, overcoming optimization software performance.