Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry

This study examines a two-stage two-dimensional cutting stock problem encountered by a paper mill company. The problem includes various machine-related and operational constraints based on real-world situations. Paper products are manufactured using two major cutting processes. Each cutting machine has a specific minimum and maximum width for input and output rolls and is limited by the maximum number of rolls it can cut at the same time. A mathematical model is presented to formally address the problem and an efficient multiple-choice knapsack-based heuristic algorithm is proposed to solve the problem. To demonstrate the efficiency of the proposed heuristic algorithm, computational experiments are conducted on test data-set generated from real-world data provided by a large paper mill company in the Republic of Korea.     

A fast algorithm for buffer allocation problem

In this paper, we address the problem of seeking optimal buffer configurations in unreliable production lines with the objective of maximising their production rates. A fast algorithm is proposed for solving the problem. The key idea is to decompose a long production line into a set of overlapping three-machine two-buffer systems. The performance of the algorithm is demonstrated by a comparison with the degraded ceiling (DC) algorithm. Numerical results show that the proposed algorithm is almost as accurate as the DC algorithm, but it is much faster, especially for long production lines.     

An integrated formulation for hierarchical cast design problems in the steel making industry

Production design is a key decision problem of steel making industry but due to its complexity, solution properties are not well understood. The design problem can be viewed as a multi-stage problem of bin packing, matching and sequencing sub-problems. Traditionally a sequential approach which treats each sub-problem separately has been applied to the simple case where mould width change is not allowed. However, for more general cases where casting with width change and different width is allowed, the sequential approach fails to generate good solutions. In this paper, we propose a mathematical programming formulation which can solve the design problem in an integrative way. By introducing multi-layer network representation of the cast design problem, it is now possible to generate an integrated formulation for the proposed problem. Based on the formulation, we derive a heuristic algorithm. The algorithm is adopted and tested at a large international integrated steel mill. The computational tests with real data-sets show that the proposed algorithm is quite effective and practical.     

A bat algorithm for the redundancy allocation problem

This article uses a recently developed bat algorithm (BA) meta-heuristic optimization method to solve the reliability redundancy allocation problem (RAP). The RAP is a well-known NP-hard problem which has been the subject of much prior work, generally of a restricted form where each component must consist of identical components in parallel to make computations tractable. Meta-heuristic methods overcome this limitation and allow for larger instances to be solved for a more general case where different components can be placed in parallel. The BA has not yet been used in reliability design, as it was a method initially designed for continuous problems. A BA is devised and tested on a well-known suite of problems from the literature. It is shown that the BA is competitive with the best known heuristics for redundancy allocation.     

A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints

This paper addresses an integrated problem of vehicle routing and three-dimensional loading with additional practical constraints such as stability, fragility and LIFO. A column generation (CG) technique-based heuristic is proposed to handle this problem. To generate new columns in CG technique, first, an elementary shortest path problem is solved to find routes with negative reduced cost. Then an extreme point-based heuristic method is employed to verify feasibility of obtained routes in terms of loading and other constraints. To speed up the CG technique, fast column generation is also performed by applying an efficient heuristic pricing method. The CG technique, tested on the benchmark instances, outperforms the efficient tabu search method developed in the literature in terms of solution quality and computation time.     

Pattern-set generation algorithm for the one-dimensional multiple stock sizes cutting stock problem

A pattern-set generation algorithm (PSG) for the one-dimensional multiple stock sizes cutting stock problem (1DMSSCSP) is presented. The solution process contains two stages. In the first stage, the PSG solves the residual problems repeatedly to generate the patterns in the pattern set, where each residual problem is solved by the column-generation approach, and each pattern is generated by solving a single large object placement problem. In the second stage, the integer linear programming model of the 1DMSSCSP is solved using a commercial solver, where only the patterns in the pattern set are considered. The computational results of benchmark instances indicate that the PSG outperforms existing heuristic algorithms and rivals the exact algorithm in solution quality.     

Modelling and a tabu search solution for the slab reallocation problem in the steel industry

This paper considers a slab reallocation problem arising from operations planning in the steel industry. The problem involves reallocating steel slabs to customer orders to improve the utilisation of slabs and the level of customer satisfaction. It can be viewed as an extension of a multiple knapsack problem. We firstly formulate the problem as an integer nonlinear programming (INLP) model. With variable replacement, the INLP model is then transformed into a mixed integer linear programming (MILP) model, which can be solved to optimality by MILP optimisers for very small instances. To obtain satisfactory solutions efficiently for practical-sized instances, a heuristic algorithm based on tabu search (TS) is proposed. The algorithm employs multiple neighbourhoods including swap, insertion and ejection chain in local search, and adopts solution space decomposition to speed up computation. In the ejection chain neighbourhood, a new and more effective search method is also proposed to take advantage of the structural properties of the problem. Computational experiments on real data from an advanced iron and steel company in China show that the algorithm generates very good results within a short time. Based on the model and solution approach, a decision support system has been developed and implemented in the company.     

A hybrid heuristic for the multiple choice multidimensional knapsack problem

In this article, a new solution approach for the multiple choice multidimensional knapsack problem is described. The problem is a variant of the multidimensional knapsack problem where items are divided into classes, and exactly one item per class has to be chosen. Both problems are NP-hard. However, the multiple choice multidimensional knapsack problem appears to be more difficult to solve in part because of its choice constraints. Many real applications lead to very large scale multiple choice multidimensional knapsack problems that can hardly be addressed using exact algorithms. A new hybrid heuristic is proposed that embeds several new procedures for this problem. The approach is based on the resolution of linear programming relaxations of the problem and reduced problems that are obtained by fixing some variables of the problem. The solutions of these problems are used to update the global lower and upper bounds for the optimal solution value. A new strategy for defining the reduced problems is explored, together with a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. An extensive set of computational experiments is reported for benchmark instances from the literature and for a large set of hard instances generated randomly. The results show that the approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.     

Ant colonies with cooperative process applied to the resource allocation problem

Abstract

In this paper, a novel algorithm describing ant colonies, with cooperation, is proposed to solve the resource allocation problem. The resource allocation problem is to allocate resources to activities, with the objective of optimizing the cost function. In our study, we viewed the search in ant colonies as a mechanism providing a main portion of diversity in search space. The cooperative process conducts fine‐tuning for the solution provided by ant colonies, and it has the ability to escape from poor local optima. In this paper, several examples are tested to prove the superiority of our proposed algorithm. From simulation results, the proposed algorithm indeed has remarkable performance.     

A heuristic for solving the redundancy allocation problem for multi-state series-parallel systems

The redundancy allocation problem is formulated with the objective of minimizing design cost, when the system exhibits a multi-state reliability behavior, given system-level performance constraints. When the multi-state nature of the system is considered, traditional solution methodologies are no longer valid. This study considers a multi-state series-parallel system (MSPS) with capacitated binary components that can provide different multi-state system performance levels. The different demand levels, which must be supplied during the system-operating period, result in the multi-state nature of the system. The new solution methodology offers several distinct benefits compared to traditional formulations of the MSPS redundancy allocation problem. For some systems, recognizing that different component versions yield different system performance is critical so that the overall system reliability estimation and associated design models the true system reliability behavior more realistically. The MSPS design problem, solved in this study, has been previously analyzed using genetic algorithms (GAs) and the universal generating function. The specific problem being addressed is one where there are multiple component choices, but once a component selection is made, only the same component type can be used to provide redundancy. This is the first time that the MSPS design problem has been addressed without using GAs. The heuristic offers more efficient and straightforward analyses. Solutions to three different problem types are obtained illustrating the simplicity and ease of application of the heuristic without compromising the intended optimization needs.     

A branch and price approach for the container relocation problem

The objective of the container relocation problem is to retrieve a set of containers from the bay (a part of the yard) of a container terminal in a given order with a minimum number of parasite movements. Up to now, only few exact solution approaches exist for this problem. They are only able to solve small and medium sized instances since the number of variables increases exponentially with the number of containers and the bay size. To overcome this problem, we introduce the first column generation approach for this problem and embed it into a branch and price procedure. We also introduce a new upper bound on the number of relocations based on the values of dual variables. Computational results show that our column generation approach provides a tight gap and solves small and medium instances with a small subset of columns within few iterations. But, the time spent on solving the subproblem prevents solving larger instances. Finding a way to reduce the time spent on the subproblem constitutes the next step of this work.     

Layer modelling for the inspection allocation problem in re-entrant production systems

In the past two decades, re-entrant production systems have received a great deal of attention. One of the most important characteristics of re-entrant production systems is that the work units are manufactured layer-by-layer, so that some defects are more difficult to inspect after they are covered by the next layer. In this research, a mathematical model considering layered fabrication is developed to find the optimal solution for allocating inspections in re-entrant production systems. Workstations of variables data and inspections of quality characteristics measurement are modelled. In addition, this study considers three possibilities for the treatment of detected non-conforming units, namely repair, rework and scrap. Moreover, a heuristic algorithm is proposed in order to improve the optimization method based on complete enumeration, which suffers from a large amount of computation time, especially as the number of workstations increases. The model is highly extensible and applicable, so it can serve as a production-planning tool to solve the inspection allocation problem in re-entrant production systems.     

A sample average approximation approach to the berth allocation problem with uncertain tides

The remarkable increases in containerized trade over the past few years have resulted in increased congestion and operational costs of container terminals, indicating the importance of the effective management of port resources under uncertainty. In this article, a novel berth allocation model is suggested for seaports, taking into consideration the disruptive effects of tides on the berthing schedule as well as the uncertainty in the arrival time of vessels. A rigorous mathematical model is presented along with a sample average approximation method to generate an efficient berth allocation plan. In addition, statistical analysis of real data gathered from a real case is presented. Numerical analysis has been conducted to verify the practical applications of the model proposed for the berth allocation problem under uncertainty. Computational results based on a real-world data set provided by Rajaee port, Iran, demonstrate the effectiveness of the proposed solution method.     

Auction-based approach to resolve the scheduling problem in the steel making process

Steel production is an extremely complex process and determining coherent schedules for the wide variety of production steps in a dynamic environment, where disturbances frequently occur, is a challenging task. In the steel production process, the blast furnace continuously produces liquid iron, which is transformed into liquid steel in the melt shop. The majority of the molten steel passes through a continuous caster to form large steel slabs, which are rolled into coils in the hot strip mill. The scheduling system of these processes has very different objectives and constraints, and operates in an environment where there is a substantial quantity of real-time information concerning production failures and customer requests. The steel making process, which includes steel making followed by continuous casting, is generally the main bottleneck in steel production. Therefore, comprehensive scheduling of this process is critical to improve the quality and productivity of the entire production system. This paper addresses the scheduling problem in the steel making process. The methodology of winner determination using the combinatorial auction process is employed to solve the aforementioned problem. In the combinatorial auction, allowing bidding on a combination of assets offers a way of enhancing the efficiency of allocating the assets. In this paper, the scheduling problem in steel making has been formulated as a linear integer program to determine the scheduling sequence for different charges. Bids are then obtained for sequencing the charges. Next, a heuristic approach is used to evaluate the bids. The computational results show that our algorithm can obtain optimal or near-optimal solutions for combinatorial problems in a reasonable computation time. The proposed algorithm has been verified by a case study.     

A flexible labour division approach to the polygon packing problem based on space allocation

This paper deals with the two-dimensional satellite module polygon packing problem. Based on the duality of material and space, it regards the polygon packing problem as a space allocation problem, which involves allocating the container space to the given polygons reasonably and efficiently. Ant colony’s labour division is essentially a kind of task allocation. Using this task allocation to achieve the space allocation in polygon packing problems, a flexible labour division approach (FLD) is proposed based on the response threshold model. According to the characteristics of space allocation in polygon packing problems, FLD designs three actions for polygons to occupy the container space. With the interaction between environmental stimulus and response threshold, each polygon takes an appropriate action to complete the space allocation and a layout that meets the requirements of satellite module layout is obtained. The results of standard test instances demonstrate the effectiveness of FLD when compared with self-organisation emergence algorithm. Moreover, experiments on the general polygon packing problem also show that FLD is competitive with other existing algorithms.     

钢筋锈蚀对全珊瑚海水钢筋/混凝土柱大偏心受压性能的影响

通过对不同混凝土强度等级、不同种类钢筋的全珊瑚海水钢筋/混凝土柱（CA/CC）进行大偏心受压性能试验,研究了CA/CC的破坏形态、变形和承载力,建立了荷载-位移、荷载-应变等关系,探讨了CA/CC大偏心受压极限承载力（N_u）的计算模型。结果表明:CA/CC的受力破坏机制和形态与普通骨料钢筋/混凝土柱（OA/CC）基本相似。随着混凝土强度等级的提高,CA/CC纵向受拉钢筋应变开始突变所对应的荷载逐渐增大。在加载过程中,有机新涂层钢筋与珊瑚/混凝土（CA/C）之间产生较大的滑移,使在相同混凝土强度下,普钢钢筋CA/CC的N_u比有机新涂层钢筋CA/CC的N_u大约高7.1%~20.8%。建议在CA/C结构中采用有机新涂层钢筋,能有效的抑制钢筋发生锈蚀,从而延长CA/C结构的有效服役寿命。综合考虑钢筋锈蚀和涂层钢筋滑移的影响,提出了适用于满足高强、高耐久性要求的CA/CC大偏心受压N_u计算模型。      

混合整数双层线性规划的全局优化算法

本文讨论了上层决策变量为整数变量、下层决策变量为连续变量的混合整数双层线性规划问题,利用其可行解均落在约束域边界上的性质,提出了一种求解混合整数双层线性规划全局最优解的算法,并举例说明了算法的执行过程。     

Hierarchical scheduling of continuous casters and hot strip mills in the steel industry: a block planning application

This work addresses the joint scheduling of continuous caster and hot strip mill processes in the steel industry. Traditionally, slab yards are used to decouple these two stages. However, the rising importance of energy costs and reduced logistic effort gives motivation for a combined scheduling. For each of the processes, a mixed-integer linear optimisation model based on the block planning principle is presented. This approach develops production schedules that take technological sequences of steel grades and milling programmes into account. We consider the integrated steel plant of an international steel company as a case study. Numerical results demonstrate the practicability of this approach under experimental conditions, which reflect typical settings from an industrial application in the steel industry.     

A modified particle swarm optimisation algorithm to solve the part feeding problem at assembly lines

The Assembly Line Part Feeding Problem (ALPFP) is a complex combinatorial optimisation problem concerned with the delivery of the required parts to the assembly workstations in the right quantities at the right time. Solving the ALPFP includes simultaneously solving two sub-problems, namely tour scheduling and tow-train loading. In this article, we first define the problem and formulate it as a multi-objective mixed-integer linear programming model. Then, we carry out a complexity analysis, proving the ALPFP to be NP-complete. A modified particle swarm optimisation (MPSO) algorithm incorporating mutation as part of the position updating scheme is subsequently proposed. The MPSO is capable of finding very good solutions with small time requirements. Computational results are reported, demonstrating the efficiency and effectiveness of the proposed MPSO.     

A simulated annealing algorithm to the multi-period fixed charge distribution problem associated with backorder and inventory

This paper addresses a multi-period fixed charge distribution problem associated with backorder and inventory. The objective is to determine the size of the shipments, backorder and inventory at each period, so that the total cost incurred during the entire period towards transportation, backorder and inventory is minimised. A pure integer non-linear programming problem is formulated. A simulated annealing based heuristic is proposed to solve and is illustrated. The proposed methodology is evaluated by comparing its solutions with the lower bound and equivalent variable cost solutions. The comparisons reveal that the simulated annealing generates better solutions than the equivalent variable cost solutions and is capable of providing solutions closer to the lower bound solutions of the problems.