Section Steel usually is a order-oriented production and not easy to resell. The material cost is large percentages of overall production cost. Hence, the key to boost efficient management is to increase the material output rate. In other words, we need to publish a efficient and reasonable cutting plan before production. And the cutting plan can cope with change to meet the market demand. The cutting plan designing is a one-dimensional cutting stock problem, and also is a typical bin packing problem. In this study we examine a combined heuristic approach for this problem. The proposed approach combines two themes of solving method¡Ga neighborhood search algorithm with threshold accepting techniques, and a Branch and Bound method. The performance of the combined heuristic approach was verified by running several benchmarking problems and the results were reported. Experimental results indicate that the proposed solving process can effectively search the feasible region and avoid being trapped in local optimal.

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions