A general corridor method-based approach for capacitated facility location

The Capacitated Facility Location Problem (CFLP) is a well-known optimisation problem with applications in a number of fields, such as distribution system planning, telecommunication network design, and supply chain design. The goal of this paper is to present a matheuristic algorithm based on the corridor method, to develop a general algorithm for a number of variants of the CFLP. The algorithm exploits solutions obtained via Lagrangean relaxation and builds corridors around such solutions via the introduction of constraints around the incumbent solution, used to limit the size of the solution space explored at each iteration. A thorough exploration of the neighbourhoods induced by the corridors is carried out using a mixed integer programming (MIP) solver. More precisely, we solve to (near) optimality over 500 benchmark instances, using the single-source as well as the multi-source formulations, both in the nominal variant, i.e. the deterministic version of the problem, and the robust variant, i.e. the version obtained when using robust optimisation to model the uncertainty of the problem parameters. The performance of the algorithm is highly competitive when compared with the best approaches proposed in the literature for each variant of the CFLP, especially considering that the algorithm has not been designed with a specific CFLP formulation in mind.     

Polymorphic uncertain nonlinear programming approach for maximizing the capacity of V-belt driving

In this paper, a polymorphic uncertain nonlinear programming (PUNP) approach is developed to formulate the problem of maximizing the capacity in a system of V-belt driving with uncertainties. The constructed optimization model is found to consist of a nonlinear objective function and some nonlinear constraints with some parameters which are of uncertain nature. These uncertain parameters are interval parameters, random interval parameters, fuzzy parameters or fuzzy interval parameters. To find a robust solution of the problem, a deterministic equivalent formulation (DEF) is established for the polymorphic uncertain nonlinear programming model. For a given satisfaction level, this DEF turns out to be a nonlinear programming involving only interval parameters. A solution method, called a sampling based interactive method, is developed such that a robust solution of the original model with polymorphic uncertainties is obtained by using standard smooth optimization techniques. The proposed method is applied into a real-world design of V-belt driving, and the results indicate that both the PUNP approach and the developed algorithm are useful to the optimization problem with polymorphic uncertainty.     

A hybrid genetic algorithm for the multi-depot open vehicle routing problem

This paper studies the multi-depot open vehicle routing problem (MDOVRP), a variant of the vehicle routing problem (VRP), in which vehicles start from several depots and are not required to return to the depot. Despite the vast amount of literature about VRPs, the MDOVRP has received very little attention from researchers. In this paper, a new hybrid genetic algorithm is presented for finding the routes that minimize the traveling cost of the vehicles. Computational results on a number of test instances indicate the proposed algorithm dominates the CPLEX solver and the existing approach in the literature. Meanwhile, experiments are conducted on multi-depot VRP benchmarks, and the results are compared with a sophisticated tabu search approach and an exact method.     

Minimising total weighted completion time on batch and unary machines with incompatible job families

This paper addresses the problem of scheduling on batch and unary machines with incompatible job families such that the total weighted completion time is minimised. A mixed-integer linear programming model is proposed to solve the problem to optimality for small instances. Tight lower bounds and a 4-approximation algorithm are developed. A constraint programming-based method is also proposed. Numerical results demonstrate that the proposed algorithms can obtain high quality solutions and have a competitive performance. Sensitivity analysis indicates that the performance of the proposed algorithms is also robust on different problem structures.     

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.     

Tactical production planning in a hybrid Make-to-Stock–Make-to-Order environment under supply,process and demand uncertainties: a robust optimisation model

In this paper, we consider a hybrid ‘Make-to-Stock–Make-to-Order’ environment to develop a novel optimisation model for medium-term production planning of a typical multi-product firm based on the competencies of the robust optimisation methodology. Three types of uncertainties: suppliers, processes and customers, are incorporated into the model to construct a robust practical model in an uncertain business environment. The modelling procedure is started with applying deterministic linear programming to develop a new multi-objective approach for the combination of multi-product multi-period production planning and aggregate production planning problems. Then, the proposed deterministic model is transformed into a robust optimisation framework and the solution procedure is designed according to the Lp-Metric methodology. Next, using the IBM ILOG CPLEX optimisation software, the proposed model is evaluated by applying the data collected from an industrial case study. Final results illustrate the applicability of the proposed model.     

Robust single machine scheduling with uncertain release times for minimising the maximum waiting time

We study a single machine scheduling problem (SMSP) with uncertain job release times (JRTs) under the maximum waiting time (MWT) criterion. To deal with the uncertainty, a robust model is established to find an optimal schedule, which minimises the worst-case MWT (W-MWT) when JRTs vary over given time intervals. Although infinite possible scenarios for JRTs exist, we show that only n scenarios are needed for calculating the W-MWT, where n is the number of jobs. Based on this property, the robust (SMSP) with uncertain JRTs to minimise the W-MWT is formulated as a mixed integer linear programming problem. To solve large-size problem instances, an efficient two-stage heuristic (TSH) is proposed. In the first stage, n near-optimal schedules are obtained by solving n deterministic scenario-based SMSPs, and their W-MWTs are evaluated. To speed up the solution and evaluation process, a modified Gusfield’s heuristic is proposed by exploiting the inner connections of these SMSPs. To further improve the schedule obtained in the first stage, the second stage consists of a variable neighbourhood search method by combining both swap neighbourhood search and insert neighbourhood search. We also develop a method to calculate the lower bound of the proposed model so that we can evaluate the performance of the solutions given by the TSH. Experimental results confirm the robustness of schedules produced and advantages of the proposed TSH over other algorithms in terms of solution quality and run time.     

Scenario-based approach for flexible resource loading under uncertainty

Order acceptance decisions in manufacture-to-order environments are often made based on incomplete or uncertain information. To quote reliable due dates in order processing, manage resource capacity adequately and take into account uncertainty, the paper presents and analyses models and tools for more robust resource loading. We refer to the problem as flexible resource loading under uncertainty. We propose a scenario-based solution approach that can deal with a wide range of uncertainty types. The approach is based on an MILP to find a plan with minimum expected costs over all relevant scenarios. To solve this MILP, we propose an exact branch-and-price algorithm. Further, we propose a much faster improvement heuristic based on an LP (linear programming) approximation. A disadvantage of the scenario-based MILP, is that a large number of scenarios may make the model intractable. We therefore propose an approximate approach that uses the aforementioned solution techniques and only a sample of all scenarios. Computational experiments show that, especially for instances with sufficient slack, solutions obtained with deterministic techniques that only use the expected scenario can be significantly improved with respect to their expected costs (i.e. robustness). We also show that for large instances, our heuristics outperform the exact approach given a maximum computation time as a stopping criterion. Moreover, it turns out that using a small sample of selected scenarios generally yields better results than using all scenarios.     

Extension of the hybrid linear programming method to optimize simultaneously the design and operation of groundwater utilization systems

This article proposes a hybrid linear programming (LP-LP) methodology for the simultaneous optimal design and operation of groundwater utilization systems. The proposed model is an extension of an earlier LP-LP model proposed by the authors for the optimal operation of a set of existing wells. The proposed model can be used to optimally determine the number, configuration and pumping rates of the operational wells out of potential wells with fixed locations to minimize the total cost of utilizing a two-dimensional confined aquifer under steady-state flow conditions. The model is able to take into account the well installation, piping and pump installation costs in addition to the operational costs, including the cost of energy and maintenance. The solution to the problem is defined by well locations and their pumping rates, minimizing the total cost while satisfying a downstream demand, lower/upper bound on the pumping rates, and lower/upper bound on the water level drawdown at the wells. A discretized version of the differential equation governing the flow is first embedded into the model formulation as a set of additional constraints. The resulting mixed-integer highly constrained nonlinear optimization problem is then decomposed into two subproblems with different sets of decision variables, one with a piezometric head and the other with the operational well locations and the corresponding pumping rates. The binary variables representing the well locations are approximated by a continuous variable leading to two LP subproblems. Having started with a random value for all decision variables, the two subproblems are solved iteratively until convergence is achieved. The performance and ability of the proposed method are tested against a hypothetical problem from the literature and the results are presented and compared with those obtained using a mixed-integer nonlinear programming method. The results show the efficiency and effectiveness of the proposed method for solving practical groundwater management problems.     

A simple and robust Monte Carlo hybrid local search algorithm for the facility location problem

In this article, a new Monte Carlo hybrid local search algorithm (Hyb-LS) is proposed for solving the uncapacitated facility location problem. Hyb-LS is based on repeated sampling using two local search strategies based on best improvement and randomized neighbourhood search. A major advantage of Hyb-LS for its practical use is that the number of restarts is its only parameter to tune. The algorithm is also simple to reimplement, scalable and robust to changes in coefficients within a problem instance. The stopping criterion for local search is learned automatically. Experimental results are presented for four representative and contrasting cost and distance models. The results obtained by Hyb-LS are compared to the optimal or near-optimal solutions found by a mixed integer linear programming (MILP) solver with a generous time limit. For three out of the four models, Hyb-LS obtains better solutions than the upper bound found by the MILP solver for at least one instance.     

Robust compliance topology optimization based on the topological derivative concept

In this paper, we present an approach for robust compliance topology optimization under volume constraint. The compliance is evaluated considering a point‐wise worst‐case scenario. Analogously to sequential optimization and reliability assessment, the resulting robust optimization problem can be decoupled into a deterministic topology optimization step and a reliability analysis step. This procedure allows us to use topology optimization algorithms already developed with only small modifications. Here, the deterministic topology optimization problem is addressed with an efficient algorithm based on the topological derivative concept and a level‐set domain representation method. The reliability analysis step is handled as in the performance measure approach. Several numerical examples are presented showing the effectiveness of the proposed approach. Copyright © 2015 John Wiley & Sons, Ltd.     

Exact and approximate algorithms for part-machine clustering based on a relationship between interval graphs and Robinson matrices

An important manufacturing cell formation problem requires permutations of the rows (parts) and columns (machines) of a part-machine incidence matrix such that the reordered matrix exhibits a block-diagonal form. Numerous objective criteria and algorithms have been proposed for this problem. In this paper, a new perspective is offered that is based on the relationship between the consecutive ones property associated with interval graphs and Robinson structure within symmetric matrices. This perspective enables the cell formation problem to be decomposed into two permutation subproblems (one for rows and one for columns) that can be solved optimally using dynamic programming or a branch-and-bound algorithm for matrices of nontrivial size. A simulated annealing heuristic is offered for larger problem instances. Results pertaining to the application of the proposed methods for a number of problems from the literature are presented.     

The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation,a Benders decomposition and a CP-based algorithm

This paper addresses a variant of two-dimensional cutting problems in which rectangular small pieces are obtained by cutting a rectangular object through guillotine cuts. The characteristics of this variant are (i) the object contains some defects, and the items cut must be defective-free; (ii) there is an upper bound on the number of times an item type may appear in the cutting pattern; (iii) the number of guillotine stages is not restricted. This problem commonly arises in industrial settings that deal with defective materials, e.g. either by intrinsic characteristics of the object as in the cutting of wooden boards with knotholes in the wood industry, or by the manufacturing process as in the production of flat glass in the glass industry. We propose a compact integer linear programming (ILP) model for this problem based on the discretisation of the defective object. As solution methods for the problem, we develop a Benders decomposition algorithm and a constraint-programming (CP) based algorithm. We evaluate these approaches through computational experiments, using benchmark instances from the literature. The results show that the methods are effective on different types of instances and can find optimal solutions even for instances with dimensions close to real-size.     

Fuzzy Regression Analysis by Quadratic Programming Reflecting Central Tendency

In this paper, we propose fuzzy regression analysis based on a quadratic programming approach. In fuzzy regression analysis, a quadratic programming approach gives more diverse spread coefficients than a linear programming approach. Moreover, a quadratic programming approach can integrate the central tendency of least squares and the possibilistic properties of fuzzy regression. Due to the characteristic of the quadratic programming problem, the proposed approach can obtain the optimal regression model representing possibilistic properties with the central tendency. In this approach, we classify the given data into two groups, i.e., the center-located group and the remaining group. Then, the upper and the lower approximation models can be obtained based on the classification result. By changing the weight coefficients of the objective function in the quadratic programming problem, we can analyze the given data in various angles.

     

Lagrangian relaxation and cut generation for sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness

The Lagrangian relaxation and cut generation technique is applied to solve sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness. The original problem is decomposed into individual job-level subproblems that can be effectively solved by dynamic programming. Two types of additional constraints for the violation of sequence-dependent setup time constraints are imposed on the decomposed subproblems in order to improve the lower bound. The decomposed subproblem with the additional setup time constraints on any subset of jobs is also effectively solved by a novel dynamic programming. Computational results show that the lower bound derived by the proposed method is much better than those of CPLEX and branch and bound for problem instances with 50 jobs and five stages with less computational effort.     

An entropy-based three-stage approach for multi-objective system reliability optimization considering uncertainty

This article presents a three-stage approach for solving multi-objective system reliability optimization problems considering uncertainty. The reliability of each component is considered in the formulation as a component reliability estimate in the form of an interval value and discrete values. Component reliability may vary owing to variations in the usage scenarios. Uncertainty is described by defining a set of usage scenarios. To address this problem, an entropy-based approach to the redundancy allocation problem is proposed in this study to identify the deterministic reliability of each component. In the second stage, a multi-objective evolutionary algorithm (MOEA) is applied to produce a Pareto-optimal solution set. A hybrid algorithm based on k-means and silhouettes is performed to select representative solutions in the third stage. Finally, a numerical example is presented to illustrate the performance of the proposed approach.     

Bi-objective scheduling on uniform parallel machines considering electricity cost

This article investigates a bi-objective scheduling problem on uniform parallel machines considering electricity cost under time-dependent or time-of-use electricity tariffs, where electricity price changes with the hours within a day. The aim is to minimize simultaneously the total electricity cost and the number of machines actually used. A bi-objective mixed-integer linear programming model is first formulated for the problem. An insertion algorithm is then proposed for the single-objective scheduling problem of minimizing the total electricity cost for a given number of machines. To obtain the whole Pareto front of the problem, an iterative search framework is developed based on the proposed insertion algorithm. Computational results on real-life and randomly generated instances demonstrate that the proposed approach is quite efficient and can find high-quality Pareto fronts for large-size problems with up to 5000 jobs.     

An algorithm for sequencing jobs to minimize total tardiness

Abstract

A theoretical framework and an efficient algorithm are presented to solve the problem of sequencing jobs on a single processor. The objective achieved is minimum total tardiness. Jobs must be independent, with deterministic processing times. A brief review of the literature concerning sequencing to achieve minimum total tardiness is presented. This review shows that Emmons’ algorithm generally results in a partial schedule, and an enumerative method, branch and bound method or dynamic programming method, was then applied to help obtain a complete sequence. Thus Emmons’ algorithm is applied as a precursor to several enumerative algorithms. Furthermore, to certain problems (i.e., LPSD: jobs which have the property of a longer processing time but a shorter due date), Emmons’ theorems would not apply before branching the problems. The algorithm presented in this paper effectively applies the partitioning method to eliminate the need for enumerative methods. A set of necessary conditions for an optimal sequence is presented with proofs in the theory section. This is followed by a statement of the algorithm. The algorithm is illustrated with an example problem taken from Ref. [7]. Computational results are then presented which show the efficiency of the algorithm relative to dynamic programming.     

Balancing transfer lines using Benders decomposition and ant colony optimisation techniques

In this paper, we investigate a transfer line balancing problem in order to find the line configuration that minimises the non-productive time. The problem is defined at an auto manufacturing company where the cylinder head is manufactured. Technological restrictions among design features and manufacturing operations are taken into consideration. The problem is represented by an integer programming model that assigns design features and cutting tools to machining stations, and specifies the number of machines and production sequence in each station. Three algorithms are developed to efficiently solve the problem under study. The first algorithm uses Benders decomposition approach that decomposes the proposed model into an assignment problem and a sequencing problem. The second algorithm is a hybrid algorithm that mixes Benders decomposition approach with the ant colony optimisation technique. The third algorithm solves the problem using two nested ant colonies. Using 15 different problem dimensions, we compare results of the three algorithms in a computational study. The first algorithm finds optimal solutions of small problem instances only. Second and third algorithms demonstrate optimality gaps less than 4.04 and 3.8%, respectively, when compared to the optimal results given by the first algorithm. Moreover, the second and third algorithms are very promising in solving medium and large-scale problem instances.     

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.