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.     

Inter-process synchronization in steel production

The development of strategies for sequencing slabs through the reheat furnace and rolling mill of a modern steel production facility is complicated by multiple, and often conflicting production objectives. Optimal energy efficiency through the reheat furnace may lead to inefficient rolling sequences or less than desirable product delivery schedules. Not only is model formulation complicated, but the combinatorial nature of the problem precludes optimal solution. A heuristic procedure for solving this multi-objective product sequencing problem has been developed and tested under production conditions in a Danish steel mill. The methodology, which is based on a modified ‘greedy’ algorithm is presented and results using actual production data are discussed     

The constraints satisfaction problem approach in the design of an architectural functional layout

A design support system with a new strategy for finding the optimal functional configurations of rooms for architectural layouts is presented. A set of configurations satisfying given constraints is generated and ranked according to multiple objectives. The method can be applied to problems in architectural practice, urban or graphic design—wherever allocation of related geometrical elements of known shape is optimized. Although the methodology is shown using simplified examples—a single story residential building with two apartments each having two rooms—the results resemble realistic functional layouts. One example of a practical size problem of a layout of three apartments with a total of 20 rooms is demonstrated, where the generated solution can be used as a base for a realistic architectural blueprint. The discretization of design space is discussed, followed by application of a backtrack search algorithm used for generating a set of potentially ‘good’ room configurations. Next the solutions are classified by a machine learning method (FFN) as ‘proper’ or ‘improper’ according to the internal communication criteria. Examples of interactive ranking of the ‘proper’ configurations according to multiple criteria and choosing ‘the best’ ones are presented. The proposed framework is general and universal—the criteria, parameters and weights can be individually defined by a user and the search algorithm can be adjusted to a specific problem.     

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.     

Joint economic production allocation and ordering policies in a supply chain consisting of multiple plants and a single retailer

This article discusses the production and ordering policies in a supply chain consisting of a single manufacturer and a single retailer. The retailer places orders based on the EOQ-like policy, and the manufacturer purchases raw materials and allocates them to the multiple plants in parallel to produce demand requirement from the retailer. The model is mathematically formulated, and the solution procedure is developed to determine the production cycle length, ordering quantity and frequency, and production allocation ratios for multiple plants. The closed forms of the production cycle length, ordering quantity, and frequency in terms of the production allocation ratios are obtained. It is also shown that the production allocation problem is NP-hard. An efficient and effective heuristic algorithm is proposed to determine the near-optimal production allocation ratios. A numerical experiment demonstrates that the proposed algorithm performs quite satisfactorily.     

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.     

Worker allocation in lean U-shaped production lines

U-shaped lines are widely used in lean systems. In U-shaped production lines, each worker handles one or more machines on the line: the worker allocation problem is to establish which machines are handled by which worker. This differs from the widely-investigated U-line assembly line balancing problem in that the assignment of tasks to line locations is fixed. This paper address the worker allocation problem for lean U-shaped production lines where the objectives are to minimize the quantity of workers and maximize full work: such allocations provide the opportunity to eliminate the least-utilized worker by improving processes accordingly. A mathematical model is developed: the model allows for any allocation of machines to workers so long as workers do not cross paths. Walking times are considered, where workers follow circular paths and walk around other worker(s) on the line if necessary. A heuristic algorithm for tackling the problem is developed, along with a procedure representing the ‘traditional’ approach of constructing standard operations routines. Computational experiments considering three line sizes (up to 20 machines) and three takt time levels are performed. The results show that the proposed algorithm both improves upon the traditional approach and is more likely to provide optimal solutions.     

Sequencing minimum product sets on mixed-model U-lines to minimise work overload

In a mixed-model assembly line (MMAL), varying models of the same basic product are produced in a facultative sequence. This gives rise to the short-term model sequencing problem, which has to decide on the production sequence of a given number of model copies so that work overload is minimised. Recently, many MMALs have been arranged in ‘U-lines’, where one operator supervises both the entrance and the exit. This paper addresses the model sequencing problem on a paced mixed-model U-line in a cyclic production environment. Some useful properties of the problem are characterised, and the problem is formulated to minimise the steady-state work overload. A branch-and-bound algorithm is proposed to solve small-sized problems, and a heuristic is proposed for practical-sized problems. Numerical experiments on 540 randomly generated instances show that the proposed heuristic can find near-optimal solutions efficiently.     

Single-item production–delivery scheduling problem with stage-dependent inventory costs and due-date considerations

This paper studies an integrated scheduling problem for a single-item, make-to-order supply chain system consisting of one supplier, one capacitated transporter and one customer. Specifically, we assume the existence in the production stage of an intermediate inventory that works as a buffer to balance the production rate and the transportation speed. Jobs are first processed on a single machine in the production stage, and then delivered to the pre-specified customer by a capacitated vehicle in the delivery stage. Each job has a due date specified by the customer, and must be delivered to the customer before its due date. Moreover, it is assumed that a job that is finished before its departure date or arrives at the customer before its due date will incur a stage-dependent corresponding inventory cost (WIP inventory, finished-good inventory or customer inventory cost). The objective is to find a coordinated production and delivery schedule such that the sum of setup, delivery and inventory costs is minimised. We formulate the problem as a nonlinear model in a general way and provide some properties. We then derive a precise instance from the general model and develop a heuristic algorithm for solving this precise instance. In order to evaluate the performance of the heuristic algorithm, we propose a simple branch-and-bound (B&B) approach for small-size problems, and a lower bound based on the Lagrangian relaxation method for large-size problems. Computational experiments show that the heuristic algorithm performs well on randomly generated problems.     

考虑库存信息的钢管批量计划优化算法

在考虑库存信息的基础上对钢管批量计划优化问题进行研究,建立了批量计划轧制位置与垛位钢坯多对多关系的批量计划模型,实现对倒垛次数的优化。结合问题特征,设计了一种基于钢坯连续倒垛的两阶段批量计划优化算法：第1阶段,确定当前最优钢坯,进而搜索同垛位上的下层钢坯,匹配最佳的连续轧制钢坯;第2阶段,针对每个轧制位置搜索垛位上的连续轧制钢坯,改进第1阶段的解。通过基于实际生产数据的实验验证,相对经典启发式算法,倒垛次数显著降低,算法和模型是可行且有效的。     

Interdependent order allocation in the two-echelon competitive and cooperative supply chain

In this paper, we consider an order allocation problem in a two-echelon supply chain with multiple suppliers and multiple demanders. The orders from the demanders are interdependent in terms of execution sequence. We consider both the competition and cooperation relationships between the suppliers and demanders. We provide formal definition for the order allocation problem and propose a negotiation mechanism which includes a two-stage negotiation protocol and two heuristic negotiation algorithms. Different negotiation strategies are proposed for the demanders and suppliers to resolve the order interdependency and competition conflict. An automated negotiation approach is introduced to implement the negotiation mechanism. The computational experiments show that orders under different supply chain contexts can be allocated with high success rate. We also numerically compare the influence of different negotiation strategies and investigate the interaction of conflict resolutions.     

Optimization of the LCD optical film cutting problem

The manufacturing of liquid crystal display (LCD) plays an important role in electronics manufacturing industries, such as televisions, smart phones, pads, laptops, monitors and electronic appliances. Due to the fact that the cost of LCD’s film materials may reach 60–70% of the production cost, appropriate cutting schemes can lead to better raw material utilisation and thus enhance manufacturers’ profitability. Accordingly, the determination of the optimal production plan for cutting different-sized LCD optimal films with the designed cutting angles to fulfil the customers’ orders is a critical issue for the LCD industry. In the past, few studies integrated the different cutting allocation strategies into a synthetic decision. This study proposes a mathematical programming model for the two-stage cutting problem for LCD optical films to determine the optimal cutting allocation strategy with consideration of the costs of raw materials, processing and disposal during the manufacturing process. For large-scale problems in which the runtime for obtaining the optimal solution may grow exponentially as the problem size increases, a heuristic algorithm is also provided to obtain the approximate solution within a reasonable time. Finally, the results of the practical case shows that, compared with the existing fixed-angle cutting method, the proposed approach reduces the total cost by 6.2% due to the better material utilisation. In addition, the processing cost is also reduced due to a decrease in the required materials.     

Optimal stocking strategies for inventory mechanism with a stochastic short-term price discount and partial backordering

Price discount is an important research topic in the field of inventory management. The existing research on this topic mainly considers fixed price discount, but ignores the situation in which stochastic short-term price discount may be involved. In this paper, we study an inventory problem considering stochastic short-term price discount and partial backordering. To address this problem, we propose an optimal replenishment and stocking model to maximise the retailers' profit. After that, a cost–benefit analysis-based heuristic method for solving the developed model is presented by considering two scenarios depending on whether a replenishment point belongs to a discount period or not. Furthermore, an algorithm is provided to elicit an optimal ordering policy from multiple solutions derived from the given heuristic solution method. Finally, a real case is offered to demonstrate the application of the proposed model, followed by a sensitivity analysis. The results indicate that a retailer can identify the optimal replenishment policy with the aim of achieving maximal profit in situations where stochastic short-term price discount and partial backordering are considered for certain inventory problems at hand. In addition, sensitivity analysis illustrates a fact that different values of the introduced parameters may influence the optimal replenishment policy.     

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.     

Product batching and batch sequencing for NC punch presses

This paper proposes a two-stage practical product batching and batch sequencing algorithm for NC punch presses used in the production of precision sheet metal electronics components. The first stage of the algorithm batches a given set of products in order to maximize the number of products in a batch as well as the tool magazine utilization. In this stage, tool magazine constraints such as number of available slots, size of slots, tool configurations and tool locations are taken into consideration. The resulting batches are passed to the second stage of the algorithm which sequences these batches. The sequencing is done by using the ‘ nearest neighbour’ heuristic for the ‘ travelling salesman problem’ Comparison of the new method with the procedure previously used by a manufacturer of such components demonstrated a significant reduction in setup times.     

Parallelized sequential value correction procedure for the one-dimensional cutting stock problem with multiple stock lengths

A heuristic approach with parallel computation is presented for the one-dimensional cutting stock problem with multiple stock lengths. The algorithm is based on the sequential heuristic procedure that generates each pattern to produce some items and repeats until all the required items are fulfilled. A recursion is used to solve the bounded knapsack problem heuristically in the pattern generation process to reduce running time. The item values are adjusted after the generation of each pattern using a value correction formula. The computational results show that the algorithm is more effective than a recently published evolutionary heuristic in improving solution quality, and can reduce computational time because of the efficient parallel implementation.     

Joint optimisation of capacity and safety stock allocation

We study the joint optimisation of capacity and safety stock allocation in assembly systems. Particularly, we consider capacitated systems with base-stock policies and periodic review. Capacity allocation is restricted by budget constraints, which can connect multiple systems. Our objective is to minimise overall inventory holding costs while satisfying service level as well as budget constraints. We propose an algorithm to jointly approximate optimal capacity allocation and base-stock levels. To this end, we introduce a set of convex approximations for this non-convex optimisation problem. In order to solve the resulting convex programmes, we analytically compute sample path derivatives via infinitesimal perturbation analysis. By iteratively adapting the approximations, we achieve good capacity allocations and base-stock levels for the original problem. Furthermore, we introduce a heuristic to allocate capacity, which originates from link capacity allocation in communication networks and use it as a benchmark. The algorithm is applied to small illustrative examples as well as cases motivated by the semiconductor manufacturing process at IBM Systems. It turns out that particularly for high utilisation levels, our algorithm can achieve significant improvements compared to the capacity allocation heuristic.     

钢铁企业副产煤气优化调度问题模型及算法

考虑钢铁企业副产煤气优化调度问题,在分析问题特征的基础上,建立了数学规划模型。针对模型特点,将遗传算法与混沌理论相结合进行模型求解,在初始种群中引入基于启发式规则生成的优良个体来提高收敛速度;通过建立个体精英库防止最优值的丢失;引入基于混沌序列的邻域搜索以提高算法的寻优效率。通过仿真实验验证了模型与算法的可行性和有效性。     

A Bound Heuristic Technique for Solving DRAMA Spares Optimizations

1IntroductionTodaythePublicrequiresthatallcomplexellgilleering,suchasatomicPOwerplants,airCrafl,automobilesandcomputer,etc.,behighlyreliable.Generally,tilesystemsarerepairableinventorysystemsthatarecomposedofitemswhicharerepairedalldretUrnedtouseratherthandiscarded.TherepairableinventoryProblemistypicallyconcernedwilhtheoptimalstockingofpartsatbases(orforwardlocations)andacentereddelx)t1'llcilitywhichrepairedunitsreturnedfromthehaseswhileprovidingsomePredeterminedlevelofservice.Themathemati…     

Initial allocation compensation algorithm for redundancy allocation: The scanning heuristic

The tiny feature size in current semiconductor integrated circuits naturally requires redundancy strategies to improve manufacturing yield and operating reliability. To find an optimal redundancy architecture that provides maximum yield and reliability is a trade-off problem. In the reliability optimization field, this type of problem is generally called a redundancy allocation problem. In this paper, we propose a new iterative algorithm, the scanning heuristic, to solve the redundancy allocation problem. The solution quality of conventional iterative heuristics is highly dependent on the initial starting point of the algorithm employed. To overcome this weakness, the scanning heuristic systematically divides the original solution space into several small bounded solution spaces. The local optimum in each divided solution space then becomes a candidate for the final solution. The experimental results demonstrate that the proposed heuristic, and subsequently some combinations of heuristics, are superior to existing heuristics in terms of solution quality.