| Traditionally, Cutting stock problems (CSP) consist of determining the best way of cutting a set of available large stock objects to smaller ordered items. In many articles, CSPs haave been studied with different goals such as minimal trim-loss, minimal production costs, minimal number of patterns, minimal total length and overproduction, etc. However, in some papers, they have also been used to describe value-maximization problems. CSPs occur in a wide range of industries and an extensive body of literature exists on solving these problems. Then, CSPs have been studied in many research disciplines such as management sciences, engineering sciences, information and computer sciences, mathematics, operations research and other. In many real world applications, Cutting stock is one of the production procedures in an enterprise. So, an enterprise not only considers the logical relationships between stocks and items, but also studies the other resource constraints on CSPs, for example cutting tools, the number of open stacks, and items with due date and other. According to the entire set of business optimization, a company not only pays attention to inside production and business procedures, but focus on the outside environment and resources constraints as well. In the environment of upstream and downstream supply chain operations, providing products or services timely and increasing customer satisfaction is one of the more important in enhancing the enterprise core competitive capacity.Firstly, this dissertation studies multi-period capacitated one-dimensional cutting stock problem (1D-CSP) in more detail. Secondly, based on above problem, it researches on integrated optimization problem of stock procurement and CSP and integrated optimization problem of CSP and item transportation based on supply chain. Finally, it studies integrated optimization problem of CSP and scheduling. The last problem includes integrated optimization problem of CSP and scheduling with considering the number of stack constraints and the coordination optimization problem of CSP and common due date scheduling.The major research and innovations are as follows:(1) For optimization model of multi-period1D-CSP, with increasing number of different item lengths and number of items the stock utilization generally improves, and hence the total stock cost decreases. On the other hand, a larger number of different cutting-patterns results in more frequent changes and setup consuming time and increases the inventory costs of items. Considering capacity of cutting process and cutting-pattern setup consuming time, the dissertation presents a multi-objective nonlinear integer programming model which studies balance among stock, cutting-pattem setup and inventory. The model’s objective is to minimize the costs of stock, cutting-pattern setup and inventory. Lagrangian relaxation of the capacity constraints allows this model to be decomposed into a set of multi-period uncapacitated1D-CSP Then, an approach integrated based on dynamic programming and column generation is presented for solving multi-period uncapacitated1D-CSP. Sub-gradient approach is employed for updating the Lagrangean multipliers and obtaining a feasible solution. Finally, a heuristic algorithm improving a solution conflicting with cutting process capacity is presented. Computational experiments are carried out to solve multi-period and one-by-one period1D-CSP. Such experiments showed that the multi-period model could obtain effective gains when compared with the one-by-one period solution. Further the cost of stock of multi-period cutting stock is lower than the total costs of stock of cutting stock in one-by-one period. (2) For coordination model of stock procurement and1D-CSP, firstly, this dissertation studies an integrated stock procurement with ordering cost and CSP with multiple length in a single period. A coordination optimization model of procurement and cutting stock with multi-products and multi-suppliers is formulated. This model’s objective function is to minimize stock, ordering and cutting-pattern setup costs. This dissertation studies not only1D-CSP with stock assortment problem, but also multiple product procurement with multiple supplier selection. This model makes up for a lack of stock assortment problem. Many different types of stock lengths which increase the ratio of the average stock to average order length can increase stock utilization rate and decrease trim loss. Lagrangian relaxation is employed to decompose the model. Heuristic algorithm based on the methods of column generation, branch-and-bound and subgradient, is developed for solving the problem. A distinctive solution steps is given. The calculation results demonstrate that1D-CSP with many different types of stock lengths greatly excelled single stock-size1D-CSP. Secondly, this disseitation presents an integrated stock procurement and cutting stock with multiple lengths in multiple periods. A multi-objective nonlinear integer programming model is formulated, and this model’s objective function is to minimize stock, item inventory, stock transportation, stock procurement and stock inventory costs. This model is decomposed into multi-period cutting stock problem with multi-length stock and multi-period multi-product procurement with supplier selection by means of Lagrangian relaxation technique. Multi-period1D-CSP model limits the number of types of stock and ignores cutting-pattern setup. This dissertation presents a hybrid heuristic which is composed of branch-and-bound and column generation and dynamic programming. For multi-period procurement with supplier selection problem, this dissertation develops a heuristic approach for this model which is based on dynamic programming and branch-and-bound. The sub-gradient algorithm is employed to calculate the optimal solution of the original problem.(3) For integrated1D-CSP and scheduling optimization model, firstly, this dissertation studies an integrated problem of1D-CSP and cutting-pattern sequencing with given the number of stacks. Considering constraint on the number of different types of items in a cutting pattern, it presents new model on coordination and optimization problem of1D-CSP and cutting-pattern sequencing, whose objective function is to minimize stock cost and span of items. Two-phase algorithm is proposed for solving the problem. The steps are given briefly. Secondly, it studies a coordination and optimization problem of1D-CSP and scheduling with a common due date. A non-linear mixed integer programming model is formulated. The objective function minimizes stock costs and item total weighted tardiness. Finally, the dissertation presents two two-stage heuristic optimization algorithms for each model.(4) For the coordination optimization problems of CSP and item transportation, firstly, an integrated optimization problem of1D-CSP and transportation is studied in a single-period. Depended on the1D-CSP, item transportation batches is divided into multiple stages according to the number of cutting patterns. A multi-objective nonlinear integer programming model is formulated, the model’s objective function is to minimize the total costs of stock, item inventory and transportation. Lagrangian relaxation is employed and then the model is decomposed into1D-CSP and transportation problem. Two heuristic algorithms are proposed for solving1D-CSP and transportation problem respectively. The subgradient algorithm is employed for solving the original model. Secondly, this dissertation studies integrating optimization problem of1D-CSP with multiple stock lengths and item transportation in multiple periods. It establishes a multi-objective non-linear integer programming model, whose objective function is to minimize stock costs, cutting-pattern setup costs, item inventory costs, vehicle costs, fixed transportation costs and product inventory costs. Then, the model is decomposed into multi-period CSP and multi-period transportation problem by means of Lagrangian relaxation. Multi-period CSP objective function includes setup costs of changing stock of different length and ignores cutting-pattern setup costs. Further, considering R types of different stock identical stock setup and ignoring identical stock setup, this dissertation decomposes multi-period CSP into R types of multi-period CSP. A heuristic algorithm, based on dynamic programming and column generation, is developed for solving R types of multi-period CSP. The inventory and transportation problem is a problem which one supplier serves a customer and supplier management client inventory. Based on dynamic programming, a heuristic algorithm is proposed for solving the inventory and transportation problem. A subgradient algorithm is employed for the original model. |
PDF Full Text Request