An exact penalty function method for optimising QAP formulation in facility layout problem

A quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach.     

A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem

The Quadratic Assignment Problem (QAP) is a difficult and important problem studied in the domain of combinatorial optimisation. It is possible to solve QAP instances with 10--20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. However, large QAP instances with more than 100 facilities are not solvable using exhaustive techniques. We have explored a variety of Genetic Algorithm crossover operators for this problem and verified its performance experimentally using well-known instances from the QAPLIB library. By increasing the number of processors, generations and population sizes we have been able to find solutions that are the same as (or very close to) the best reported solutions for large QAP instances in QAPLIB. In order to parallelise the Genetic Algorithm we generate and evolve separate solution pools on each cluster processor, using an island model. This model exchanges 10% of each processor’s solutions at the initial stages of optimisation. We show experimentally that both execution times and solution qualities are improved for large QAP instances by using our Island Parallel Genetic Algorithm.     

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.     

Cooperative inventory planning in a distribution network

This study addresses the problem of optimal ordering and collaborative inventory management in a distribution network as a two-stage decision problem. In the first stage, when demand is uncertain, the retailers (sellers) order the products from a warehouse. Then, when demand becomes known with certainty, retailers may exchange their products to better match local demands. Sellers should determine their optimal order quantities for the first stage, and quantities and prices of products exchanged in the second stage. This paper proposes to build sellers’ coalitions and solve the two-stage decision problem as a cooperative game. Stability of a sellers’ coalition can be achieved only if the benefits resulting from collaboration are maximised and distributed according to an allocation policy that is both efficient and rational. The profit maximisation problem is formulated as a stochastic optimisation problem with recourse. Using the scenario method, this problem is approximated by a deterministic linear problem for which the existence of a solution is guaranteed. The proposed pricing policy guarantees the rational allocation of benefits under the scenario approximation. An industrial example supports the modelling approach and is used to evaluate the profitability of the exchange practice in the case of real data.     

A simulation-optimisation approach for supply chain network design under supply and demand uncertainties

We investigate a three-echelon stochastic supply chain network design problem. The problem requires selecting suppliers, determining warehouses locations and sizing, as well as the material flows. The objective is to minimise the total expected cost. An important feature of the investigated problem is that both the supply and the demand are uncertain. We solve this problem using a simulation-optimisation approach that is based on a novel hedging strategy that aims at capturing the randomness of the uncertain parameters. To determine the optimal hedging parameters, the search process is guided by particle swarm optimisation procedure. We present the results of extensive computational experiments that were conducted on a large set of instances and that provide evidence that the proposed hedging strategy constitutes an effective viable solution approach.     

Genetic-algorithms-based algorithm portfolio for inventory routing problem with stochastic demand

This paper presents an algorithm portfolio methodology based on evolutionary algorithms to solve complex dynamic optimisation problems. These problems are known to have computationally complex objective functions, which make their solutions computationally hard to find, when problem instances of large dimensions are considered. This is due to the inability of the algorithms to provide an optimal or near-optimal solution within an allocated time interval. Therefore, this paper employs a bundle of evolutionary algorithms (EAs) tied together with several processors, known as an algorithm portfolio, to solve a complex optimisation problem such as the inventory routing problem (IRP) with stochastic demands. EAs considered for algorithm portfolios are the genetic algorithm and its four variants such as the memetic algorithm, genetic algorithm with chromosome differentiation, age-genetic algorithm, and gender-specific genetic algorithm. In order to illustrate the applicability of the proposed methodology, a generic method for algorithm portfolios design, evaluation, and analysis is discussed in detail. Experiments were performed on varying dimensions of IRP instances to validate different properties of algorithm portfolio. A case study was conducted to illustrate that the set of EAs allocated to a certain number of processors performed better than their individual counterparts.     

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.     

Supply chain optimisation with both production and transportation integration: multiple vehicles for a single perishable product

This paper deals with an extension of the integrated production and transportation scheduling problem (PTSP) by considering multiple vehicles (PTSPm) for optimisation of supply chains. The problem reflects a real concern for industry since production and transportation subproblems are commonly addressed independently or sequentially, which leads to sub-optimal solutions. The problem includes specific capacity constraints, the short lifespan of products and the special case of the single vehicle that has already been studied in the literature. A greedy randomised adaptive search procedure (GRASP) with an evolutionary local search (ELS) is proposed to solve the instances with a single vehicle as a special case. The method has been proven to be more effective than those published and provides shorter computational times with new best solutions for the single vehicle case. A new set of instances with multiple vehicles is introduced to favour equitable future research. Our study extends previous research using an indirect resolution approach and provides an algorithm to solve a wide range of one-machine scheduling problems with the proper coordination of single or multiple vehicles.     

Bilevel joint optimisation for product family architecting considering make-or-buy decisions

Product family architecting (PFA) aims at identification of common modules and selective modules to enable product family configuration for mass customisation. Due to nowadays manufacturers moving more towards assembly-to-order production throughout a distributed supply chain, the common practice of outsourcing of certain modules entails make-or-buy (MOB) decisions that must be taken into account in PFA. While the PFA and MOB decisions are enacted for different concerns of the manufacturer and the suppliers, it is important to deal with joint optimisation of the PFA and MOB problems. The prevailing decision models for joint optimisation are mainly originated from an ‘all-in-one’ approach that assumes both PFA and MOB decisions can be integrated into one single-level optimisation problem. Such an assumption neglects the complex trade-offs underlying two different decision-making problems and fails to reveal the inherent coupling of PFA and MOB decisions. This paper proposes to formulate joint optimisation of the PFA and MOB problems as a Stackelberg game, in which a bilevel decision mechanism model is deployed to reveal the inherent coupling and hierarchical relationships between PFA and MOB decisions. A nonlinear bilevel optimisation model is developed with the PFA problem acting as the leader and each MOB problem performing as a follower. A nested genetic algorithm is developed to solve the bilevel optimisation model. A case study of power transformer PFA subject to MOB considerations is presented to illustrate the feasibility and effectiveness of bilevel joint optimisation.     

Multi-dimensional clearing functions for aggregate capacity modelling in multi-stage production systems

Nonlinear clearing functions have been proposed in the literature as metamodels to represent the behaviour of production resources that can be embedded in optimisation models for production planning. However, most clearing functions tested to date use a single-state variable to represent aggregate system workload over all products, which performs poorly when product mix affects system throughput. Clearing functions using multiple-state variables have shown promise, but require significant computational effort to fit the functions and to solve the resulting optimisation models. This paper examines the impact of aggregation in state variables on solution time and quality in multi-item multi-stage production systems with differing degrees of manufacturing flexibility. We propose multi-dimensional clearing functions using alternative aggregations of state variables, and evaluate their performance in computational experiments. We find that at low utilisation, aggregation of state variables has little effect on system performance; multi-dimensional clearing functions outperform single-dimensional ones in general; and increasing manufacturing flexibility allows the use of aggregate clearing functions with little loss of solution quality.     

Supply chain network design with unreliable suppliers: a Lagrangian relaxation-based approach

This paper deals with the integrated facility location and supplier selection decisions for the design of supply chain network with reliable and unreliable suppliers. Two problems are addressed: (1) facility location/supplier selection; and (2) facility location/supplier reliability. We first consider the facility location and supplier selections problem where all the suppliers are reliable. The decisions concern the selection of suppliers, the location of distribution centres (DCs), the allocation of suppliers to DCs and the allocation of retailers to DCs. The objective is to minimise fixed DCs location costs, inventory and safety stock costs at the DCs and ordering costs and transportation costs across the network. The introduction of inventory costs and safety stock costs leads to a non-linear NP-hard optimisation problem. To solve this problem, a Lagrangian relaxation-based approach is developed. For the second problem, a two-period decision model is proposed in which selected suppliers are reliable in the first period and can fail in the second period. The corresponding facility location/supplier reliability problem is formulated as a non-linear stochastic programming problem. A Monte Carlo optimisation approach combining the sample average approximation scheme and the Lagrangian relaxation-based approach is proposed. Computational results are presented to evaluate the efficiency of the proposed approaches.     

Supply chain network optimization considering assembly line balancing and demand uncertainty

In supply chain optimisation problems, determining the location, number and capacity of facilities is concerned as strategic decisions, while mid-term and short-term decisions such as assembly policy, inventory levels and scheduling are considered as the tactical and operational decision levels. This paper addresses the optimisation of strategic and tactical decisions in the supply chain network design (SCND) under demand uncertainty. In this respect, a two-stage stochastic programming model is developed in which strategic location decisions are made in the first-stage, while the second-stage contains SCND problem and the assembly line balancing as a tactical decision. In the solution scheme, the combination of sample average approximation and Latin hypercube sampling methods is utilised to solve the developed two-stage mixed-integer stochastic programming model. Finally, computational experiments on randomly generated problem instances are presented to demonstrate the performance and power of developed model in handling uncertainty. Computational experiments showed that stochastic model yields better results compared with deterministic model in terms of objective function value, i.e. the sum of the first-stage costs and the expected second-stage costs. This issue proved that uncertainty would be a significant and fundamental element of developed model and improve the quality of solutions.     

Robust production management

The problem of production management can often be cast in the form of a linear program with uncertain parameters and risk constraints. Typically, such problems are treated in the framework of multi-stage Stochastic Programming. Recently, a Robust Counterpart (RC) approach has been proposed, in which the decisions are optimized for the worst realizations of problem parameters. However, an application of the RC technique often results in very conservative approximations of uncertain problems. To tackle this drawback, an Adjustable Robust Counterpart (ARC) approach has been proposed by Ben-Tal et al. In ARC, some decision variables are allowed to depend on past values of uncertain parameters. A restricted version of ARC, introduced by Ben-Tal et al. and which can be efficiently solved, is referred to as Affinely Adjustable Robust Counterpart (AARC). In this paper, we consider an application of the ARC and AARC methodologies to the problem of yearly electricity production management in France. We provide tractable formulations for the AARC of quadratic and of some conic quadratic optimization problems, as well as for the ARC and AARC of the electricity production problem. We then give the quality of robust solutions obtained by using different uncertainty sets estimated using simulated and historical data. Our methodology is finally compared with other management methods.     

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.     

Distribution planning for multi-echelon networks considering multiple sourcing and lateral transshipments

Nowadays, due to the increasing complexity of business environment, especially demand uncertainty, supply chain managers need to establish more-effective sourcing and distribution strategies to ensure high customer service and low stock costs. To overcome this challenge multi-echelon network structures and alternative distribution strategies such as lateral transshipments and multiple sourcing should be considered in inventory optimisation models. In this article, we propose a scenario-based modelling approach to solve a two-stage multi-echelon inventory optimisation problem with a non-stationary demand. The model is based on a distribution requirements planning (DRP) approach and minimises the expected total cost that is composed of the fixed allocation, inventory holding, procurement, transportation, and back-ordering costs. Alternative inventory optimisation models, including the lateral transshipment strategy and multiple sourcing, are thus built, and the corresponding stochastic programmes are solved using the sample average approximation method. Through a numerical investigation conducted with several generated instances and an empirical investigation based on the case of a major French retailer’s distribution network, we show the substantial benefit of lateral transshipments and multiple sourcing in reducing the expected total costs of the distribution network.     

Coordinated optimisation of platform-driven product line planning by bilevel programming

Product line planning (PLP) aims at an optimal combination of product feature offerings, suggesting itself to be a determinant decision for a company to satisfy diverse customer needs and gain competitive advantages. Fulfilment of planned product lines must make trade-offs between product variety and production costs. To balance the costs of product lines, manufacturers often adopt a product platform configuration (PPC) approach to redesign product and process platforms by adding new modules to the legacy platforms. The PPC is an effective means of providing product variety while controlling the manufacturing costs. The PLP and PPC problems have traditionally been investigated separately in the marketing research and engineering design fields. It is important to coordinate PLP and PPC decisions within a coherent optimisation framework. This paper proposes a bilevel mixed 0–1 nonlinear programming model to formulate coordinated optimisation for platform-driven product line planning. The upper level deals with the PLP problem by maximising the profit of an entire product line, whilst the lower level copes with the multiple product platforms optimisation for the optimal PPC in accordance with the upper level decisions of product line structure. To solve this bilevel programming model, a bilevel genetic algorithm is developed to find the optimal solution. A case study of coordinated optimisation between an automobile line and its product platforms is presented to demonstrate the feasibility and effectiveness of the proposed bilevel programming in comparison with a typical ‘all-in-one’ approach and a non-joint optimisation programming.     

A hybrid particle swarm based method for process planning optimisation

A process planning (PP) problem is defined as to determine a set of operation-methods (machine, tool, and set-up configuration) that can convert the given stock to the designed part. Essentially, the PP problem involves the simultaneous decision making of two tasks: operation-method selection and sequencing. This is a combinatorial optimisation problem and it is difficult to find the best solution in a reasonable amount of time. In this article, an optimisation approach based on particle swarm optimisation (PSO) is proposed to solve the PP problem. Due to the characteristic of discrete process planning solution space and the continuous nature of the original PSO, a novel solution representation scheme is introduced for the application of PSO in solving the PP problem. Moreover, two kinds of local search algorithms are incorporated and interweaved with PSO evolution to improve the best solution in each generation. The numerical experiments and analysis have demonstrated that the proposed algorithm is capable of gaining a good quality solution in an efficient way.     

Solving complex design problems through multiobjective optimisation taking into account judgements of users

In the design process of products or systems, a current trend consists in taking into account judgments of users. In this context, a multiobjective optimisation method taking into account judgments of a panel of subjects is proposed. It is aimed at identifying the best trade-offs between quantitative objectives and judgments of users. The method is divided in two steps: (1) judgment data acquisition and (2) integration of the judgment data into the multiobjective optimisation process. The method is based on a stochastic Pareto-based evolutionary algorithm for optimisation and on a multilinear interpolation for judgment modelling. The combination of these techniques makes it possible to solve complex problems, with up to eight decision variables and up to at least eight objectives. Relevant applications of the method include optimisation with judgments about various aspects of the product or system, identification of the best trade-offs satisfying at the same time several groups with different judgments, and analysis of the interest of market segmentation. For illustration purpose, a pilot study about an individual office lighting design problem is processed.     

Optimisation of production and subcontracting strategies

We consider the problem of optimising production and subcontracting decisions in a supply chain manufacturing engineered products. The supply chain manager can use a combination of internal production capacities, available capacity at qualified subcontractors, make capital investments and process improvements to minimise costs associated with production and penalties for not meeting desired operational metrics. We formulate this as an optimisation problem that requires simultaneous solution of a mathematical programming problem and queuing network model. We propose an efficient iterative approach to solve this problem and conduct numerical studies to demonstrate the effectiveness of the approach.     

Algorithm for a class of constrained weight least square problems and applications

An algorithm, based on ordinal optimisation (OO) and sensitive theories, is presented to solve a class of constrained weight least square problems with continuous and discrete variables. the proposed algorithm can cope with an enormous amount of computational complexity problems and has a high probability of obtaining a good enough solution according to the oo theory. this method has some advantages, such as computational efficiency, numerical stability and the superiority of the good enough solution. the proposed algorithm is explicit, compact and easy to program. test results demonstrate that the proposed approach is more computational-efficient than other existing approaches for solving constrained-state estimation problems with continuous and discrete variables on the ieee 30-bus and the ieee 118-bus systems.