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.     

A cutting plane approach for the single-product assembly system design problem

This paper evaluates a new branch-and-cut approach, establishing a computational benchmark for the single-product, assembly system design (SPASD) problem. Our approach, which includes a heuristic, preprocessing, and two cutgenerating methods, outperformed OSL in solving a set of 102 instances of the SPASD problem. The approach is robust; test problems show that it can be applied to variations of the generic SPASD problem that we encountered in industry.     

A hybrid approach for the capacitated lot sizing problem with setup carryover

The capacitated lot sizing problem with setup carryover deals with the issue of planning multiple products on a single machine. A setup can be carried over from one period to the next by incorporating the partial sequencing of the first and last product. This study proposes a novel hybrid approach by combining Genetic Algorithms (GAs) and a Fix-and-Optimise heuristic to solve the capacitated lot sizing problem with setup carryover. Besides this, a new initialisation scheme is suggested to reduce the solution space and to ensure a feasible solution. A comparative experimental study is carried out using some benchmark problem instances. The results indicate that the performance of the pure GAs improves when hybridised with the Fix-and-Optimise heuristic. Moreover, in terms of solution quality, promising results are obtained when compared with the recent results in the literature.     

Optimisation of the multi-depots pick-up and delivery problems with time windows and multi-vehicles using PSO algorithm

Many sectors in the transport industry are concerned about the vehicle routing problem (VRP), hence the growing interest of researchers for this type of problem and its variants. This is due essentially to its many real applications in logistics for the transport of goods. The originality and contribution of our work is that we have dealt a problem that combines several variants: multiple vehicles (m), multiple depots (MD), pickup and delivery problem (PDP) with time windows (TW). Hence the notation of our problem: m-MDPDPTW. In this paper, we present the m-MDPDPTW, which is an optimisation problem belonging to the category of NP Hard problems. This problem must meet requests for transport between customers and suppliers satisfying precedence, capacity and time constraints. The goal is to find the best solution, which is the best route minimising the total travelled distance. To solve and optimise our m-MDPDPTW, we have developed a new algorithm based on the particle swarm optimisation (PSO) method. The performance of this new approach is tested on data set instances of Li and Lim's benchmark problems in which we have added multiple depot locations. Comparing with prior works, our proposed approach gave better results by decreasing the distance for several studied instances.     

An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem

This article presents an efficient heuristic placement algorithm, namely, a bidirectional heuristic placement, for solving the two-dimensional rectangular knapsack packing problem. The heuristic demonstrates ways to maximize space utilization by fitting the appropriate rectangle from both sides of the wall of the current residual space layer by layer. The iterative local search along with a shift strategy is developed and applied to the heuristic to balance the exploitation and exploration tasks in the solution space without the tuning of any parameters. The experimental results on many scales of packing problems show that this approach can produce high-quality solutions for most of the benchmark datasets, especially for large-scale problems, within a reasonable duration of computational time.     

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.     

Local search for nonpreemptive multi-mode resource-constrained project scheduling

This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewable resources. We provide a well known 0-1 problem formulation and stress the importance of the model by giving applications within production and operations management. Furthermore, we prove that the feasibility problem is already NP-complete. Solution procedures proposed so far have the following shortcomings: exact methods can solve only very small instances to optimality; heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search method that first tries to find a feasible solution and secondly performs a single-neighborhood search on the set of feasible mode assignments. To evaluate the new procedure we perform a rigorous computational study on two benchmark sets. The experiment includes a comparison of our procedure with other heuristics.     

Set-partitioning-based heuristic for balancing and configuration of automated flexible machining line

Flexible machining lines are used in a wide range of industries due to their ability of reconfiguration to meet high variety of customer demands. A novel problem is proposed in the current research to consider automated flexible machining line (AFML) with automated machining using computer numerical control machines and automated auxiliary operations using robots. A mixed-integer programming model for the current novel problem is developed. Moreover, a novel method named set-partitioning-based heuristic (SPH) is proposed to solve this new flexible machining line balancing problem to minimise the cycle time of the line and the performance is compared with both exact algorithm and random search algorithm. A set of benchmark instances based on different size of problems against different system parameters is made. Furthermore, sensitivity analysis of the system parameter in AFML is performed to know, how the number of machines and processing time can influence the cycle time and the utilisation of AFML. Computational experiments are performed to show the performance of the proposed method SPH against other methods and the results indicate that SPH performs best among all test methods in terms of solution quality and computation on both the proposed benchmark instances.     

Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem

This article addresses a Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem, an NP-hard combinatorial optimization problem. The problem is solved by using a cooperative approach that uses a local search for exploring a series of neighbourhoods induced from the Lagrangian relaxation. Each neighbourhood is submitted to an optimization process using two alternative strategies: reducing and moving strategies. The reducing strategy serves to reduce the current search space whereas the moving strategy explores the new search space. The performance of the proposed approach is evaluated on benchmark instances taken from the literature. Its obtained results are compared with those reached by some recent methods available in the literature. New solutions have been obtained for almost 80% of the instances tested.     

Scheduling multistage hybrid flowshops with multiprocessor tasks by an effective heuristic

This study considers the scheduling problem of multistage hybrid flowshops with multiprocessor tasks, which is a core topic for numerous industrial applications. An effective and efficient heuristic, namely the heuristic of multistage hybrid flowshops (HMHF) is proposed to solve this problem. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem set. The results are compared with 10 constructive heuristics and a tabu search (TS) based meta-heuristic from the relevant literature. These computational results show that the proposed HMHF heuristic is highly effective when compared to these algorithms for this problem on the same benchmark instances.     

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.     

A nested column generation algorithm to the meta slab allocation problem in the steel making industry

This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the ‘multi-stage multiple knapsack problem’ where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design ‘bins’, here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computational results showed that the proposed heuristic solved the real instances pretty well. The proposed algorithm was successfully deployed to the integrated steel mill.     

A multi-stage facility location problem with staircase costs and splitting of commodities: model,heuristic approach and application

In this paper a multi-stage facility location problem with staircase costs and splitting of commodities is introduced and formulated as a mixed integer program. The problem is motivated by an application in the context of a reverse supply chain for end-of-life vehicles. We propose a two-phase heuristic solution approach: The greedy construction heuristic utilizes the solution obtained by the LP-relaxation of the problem. In the improvement heuristic we combine ADD, DROP and SWAP neighborhoods with a diversification strategy to a Variable Neighborhood Descent (VND) and to a Variable Neighborhood Search (VNS) approach. Computational results show that this approach is able reduce the duality gap provided by state-of-the-art MIP solver CPLEX for small and medium-sized instances and is also able to provide high-quality solutions for large-scale instances with up to 2,900 candidate facilities. The building blocks of the solution approach can easily be rearranged in order to solve other facility location problems.     

Tabu search-based algorithm for the TOC product mix decision

The theory of constraints (TOC) is a management philosophy that maximizes profits in a manufacturing plant with a demonstrated bottleneck. The product mix decision is one application of TOC that involves determination of the quantity and the identification of each product to produce. However, the original TOC heuristic is considered to produce unrealizable solution when a manufacturing plant has multiple resource constraints. This paper presents a tabu search-based TOC product mix heuristic to identify optimal or near optimal product mix for small problem instances under conditions where the original TOC heuristic failed. The tabu search-based TOC product mix heuristic is further used to solve large problem instances typical of practical manufacturing scenario. The experimental results for small to medium size problem show that the tabu search-based TOC heuristic compares favourably with those of optimal methods. Large size problems for which optimal methods have not been established in terms of feasibility in computation times were also solved in reasonable times with good quality solutions, thus confirming that the proposed approach is appropriate for adoption by production planners for the product mix problem in the manufacturing industry.     

An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts

Puzzle-based storage systems consist of densely stored unit loads on a square grid. The problem addressed in this paper is to retrieve a stored unit load from a puzzle-based storage using the minimum number of item moves. While previous research contributed optimal algorithms for only up to two empty locations (escorts), our approach solves configurations where multiple empty locations are arbitrarily positioned in the grid. The problem is formulated as a state space problem and solved to optimality using an exact search algorithm. To reduce the search space, we derive bounds on the number of eligible empty locations and develop several search-guiding estimate functions. Furthermore, we present a heuristic variant of the search algorithm to solve larger problem instances. We evaluate both solution algorithms on a large set of problem instances. Our computational results show that the algorithms clearly outperform existing approaches where they are applicate and solve more general configurations, which could not be solved to optimality before. The heuristic variant efficiently yields high-quality solutions for significantly larger instances of practically relevant size.     

An exact method for solving the manufacturing cell formation problem

The cell formation problem is extensively studied in the literature, but very few authors have proposed exact methods. In this paper a linear binary programming formulation is introduced to generate a solution for the cell formation problem. To verify the behaviour of the proposed model, a set of 35 benchmark problems is solved using the branch and cut method implemented in the IBM ILOG CPLEX 10.11 Optimiser. Moreover, these results allow us to validate the quality of the solution generated with heuristic methods proposed in the literature. This experimentation indicates that, for the smaller problems, the best-known solutions are the same as those generated with CPLEX 10.11 Optimiser. These results indicate a fair confidence in the optimality of the best-known solutions generated by the heuristic methods. Furthermore, our approach is the first exact method providing results of this quality.     

Multi-degree cyclic hoist scheduling with time window constraints

This paper deals with the multi-degree cyclic single-hoist scheduling problem with time window constraints, in which multiple identical parts enter and leave the system during each cycle. We propose an analytical mathematical model and a branch-and-bound algorithm so as to find a cyclic sequence of hoist moves that maximises the throughput. The branch-and-bound algorithm implicitly enumerates the sequence of hoist moves and requires the solution of a specific set of linear programming problems (LPPs). Computational results on benchmark instances and randomly generated test instances are presented.     

Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window

This study addresses the single-machine scheduling problem with a common due window (CDW) that has a constant size and position. The objective is to minimise the total weighted earliness–tardiness penalties for jobs completed out of the CDW. To determine a schedule as close to optimum as possible, this study develops a dynamic dispatching rule and an effective constructive heuristic. The better performance of the proposed heuristic is demonstrated by comparing the results of it with those of a state-of-the-art greedy heuristic on a well-known benchmark problem set. In addition, we incorporate the constructive heuristic into a best-so-far meta-heuristic to examine the benefit of the proposed heuristic. The results show that the best known solutions in 144 out of the 250 benchmark instances are improved.     

Cooperative parallel adaptive neighbourhood search for the disjunctively constrained knapsack problem

This article investigates the use of parallel computing for solving the disjunctively constrained knapsack problem. The proposed parallel computing model can be viewed as a cooperative algorithm based on a multi-neighbourhood search. The cooperation system is composed of a team manager and a crowd of team members. The team members aim at applying their own search strategies to explore the solution space. The team manager collects the solutions from the members and shares the best one with them. The performance of the proposed method is evaluated on a group of benchmark data sets. The results obtained are compared to those reached by the best methods from the literature. The results show that the proposed method is able to provide the best solutions in most cases. In order to highlight the robustness of the proposed parallel computing model, a new set of large-scale instances is introduced. Encouraging results have been obtained.     

A mixed-integer programming formulation and Lagrangean relaxation for the cross-dock door assignment problem

In a cross-dock, goods are unloaded from incoming trucks, consolidated according to their destinations, and then, loaded into outgoing trucks with little or no storage in between. In this paper, we study the cross-dock door assignment problem in which the assignment of incoming trucks to strip doors, and outgoing trucks to stack doors is determined, with the objective of minimising the total material handling cost. We present a new mixed integer programming formulation which is embedded into a Lagrangean relaxation that exploits the special structure of the problem to obtain bounds on the optimal solution value. A primal heuristic is used at every iteration of the Lagrangean relaxation to obtain high quality feasible solutions. Computational results obtained on benchmark instances (with up to 20 origins and destinations, and 10 strip and stack doors) and on a new and more difficult set of instances (with up to 50 origins and destinations, and 30 strip and stack doors) confirm the efficiency of the algorithm.