Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete

The coordination of just-in-time production and transportation in a network of partially independent facilities to guarantee timely delivery to distributed customers is one of the most challenging aspect of supply chain management. From a theoretical perspective, the timely production/distribution can be viewed as a hybrid combination of planning, scheduling and routing problems, each notoriously affected by nearly prohibitive combinatorial complexity. From a practical viewpoint, the problem calls for a trade-off between risks and profits. This paper focuses on the ready-mixed concrete delivery: in addition to the mentioned complexity, strict time-constraints forbid both earliness and lateness of the supply. After developing a detailed model of the considered problem, we propose a novel meta-heuristic approach based on a hybrid genetic algorithm combined with constructive heuristics. A detailed case study derived from industrial data is used to illustrate the potential of the proposed approach.     

Hybrid algorithm for a vendor managed inventory system in a two-echelon supply chain

In this paper we address the issue of vendor managed inventory (VMI) by considering a two-echelon single vendor/multiple buyer supply chain network. We try to find the optimal sales quantity by maximizing profit, given as a nonlinear and non-convex objective function. For such complicated combinatorial optimization problems, exact algorithms and optimization commercial software such as LINGO are inefficient, especially on practical-size problems. In this paper we develop a hybrid genetic/simulated annealing algorithm to deal with this nonlinear problem. Our results demonstrate that the proposed hybrid algorithm outperforms previous methodologies and achieves more robust solutions.     

An optimal solution to a three echelon supply chain network with multi-product and multi-period

Recently, Kadadevaramath et al. (2012) [1] presented a mathematical model for optimizing a three echelon supply chain network. Their model is an integer linear programming (ILP) model. In order to solve it, they developed five algorithms; four of them are based on a particle swarm optimization (PSO) method and the other is a genetic algorithm (GA). In this paper, we develop a more general mathematical model that contains the model developed by Kadadevaramath et al. (2012) [1]. Furthermore, we show that all instances proved in Kadadevaramath et al. (2012) [1] can easily be solved optimally by any integer linear programming solver.     

Multiple-buyer multiple-vendor multi-product multi-constraint supply chain problem with stochastic demand and variable lead-time: A harmony search algorithm

In this paper, a multi-buyer multi-vendor supply chain problem is considered in which there are several products, each buyer has limited capacity to purchase products, and each vendor has warehouse limitation to store products. In this chain, the demand of each product is stochastic and follows a uniform distribution. The lead-time of receiving products from a vendor to a buyer is assumed to vary linearly with respect to the order quantity of the buyer and the production rate of the vendor. For each product, a fraction of the shortage is backordered and the rest are lost. The ordered product quantities are placed in multiple of pre-defined packets and there are service rate constraints for the buyers. The goal is to determine the reorder points, the safety stocks, and the numbers of shipments and packets in each shipment of the products such that the total cost of the supply chain is minimized. We show that the model of this problem is of an integer nonlinear programming type and in order to solve it a harmony search algorithm is employed. To validate the solution and to compare the performance of the proposed algorithm, a genetic algorithm is utilized as well. A numerical illustration and sensitivity analysis are given at the end to show the applicability of the proposed methodology in real-world supply chain problems.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

On greedy algorithms for series parallel graphs

This note describes some sufficient conditions for the maximum or minimum of a weighted flow (the weights are on paths, and are derived from weights on the edges of the path), of given volume in a series parallel graph to be found by a greedy algorithm.     

Genetic algorithms for solving the discrete ordered median problem

In this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits.     

A possibilistic decision model for new product supply chain design

This paper models supply chain (SC) uncertainties by fuzzy sets and develops a possibilistic SC configuration model for new products with unreliable or unavailable SC statistical data. The supply chain is modeled as a network of stages. Each stage may have one or more options characterized by the cost and lead-time required to fulfill required functions and may hold safety stock to prevent an inventory shortage. The objective is to determine the option and inventory policy for each stage to minimize the total SC cost and maximize the possibility of fulfilling the target service level. A fuzzy SC model is developed to evaluate the performance of the entire SC and a genetic algorithm approach is applied to determine near-optimal solutions. The results obtained show that the proposed approach allows decision makers to perform trade-off analysis among customer service levels, product cost, and inventory investment depending on their risk attitude. It also provides an alternative tool to evaluate and improve SC configuration decisions in an uncertain SC environment.     

A multi-objective approach to supply chain visibility and risk

This paper investigates the twin effects of supply chain visibility (SCV) and supply chain risk (SCR) on supply chain performance. Operationally, SCV has been linked to the capability of sharing timely and accurate information on exogenous demand, quantity and location of inventory, transport related cost, and other logistics activities throughout an entire supply chain. Similarly, SCR can be viewed as the likelihood that an adverse event has occurred during a certain epoch within a supply chain and the associated consequences of that event which affects supply chain performance. Given the multi-faceted attributes of the decision making process which involves many stages, objectives, and stakeholders, it beckons research into this aspect of the supply chain to utilize a fuzzy multi-objective decision making approach to model SCV and SCR from an operational perspective. Hence, our model incorporates the objectives of SCV maximization, SCR minimization, and cost minimization under the constraints of budget, customer demand, production capacity, and supply availability. A numerical example is used to demonstrate the applicability of the model. Our results suggest that decision makers tend to mitigate SCR first then enhance SCV.     

Possibilistic linear-programming approach for supply chain networking decisions

Supply chain networking decisions are very important for the medium- and long-term planning success of manufacturing companies. The inputs to supply chain planning models are subject to environmental and system uncertainties. In this paper, a fuzzy set theory-based model is proposed to deal with those uncertainties. For this purpose, a possibilistic linear programming (PLP) model is used to make strategic resource-planning decisions using fuzzy demand forecasts and fuzzy yield rates as well as other inputs such as costs and capacities. The objective of the proposed PLP is to maximize the total profit of the enterprise. The model is applied to Mercedes–Benz Türk, one of the largest bus-manufacturing companies in the world, and conclusions and suggestions for further research are provided.     

Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem

The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.     

Modeling and optimizing a vendor managed replenishment system using machine learning and genetic algorithms

Using a supply chain network, we demonstrate the feasibility, viability, and robustness of applying machine learning and genetic algorithms to respectively model, understand, and optimize such data intensive environments. Deployment of these algorithms, which learn from and optimize data, can obviate the need to perform more complex, expensive, and time consuming design of experiments (DOE), which usually disrupt system operations. We apply and compare the behavior and performance of the proposed machine learning algorithms to that obtained via DOE in a simulated Vendor Managed Replenishment system, developed for an actual firm. The results show that the models resulting from the proposed algorithms had strong explanatory and predictive power, comparable to that of DOE. The optimal system settings and profit were also similar to that obtained from DOE. The virtues of using machine learning and evolutionary algorithms to model and optimize data rich environments thus seem promising because they are automatic, involving little human intervention and expertise. We believe and are exploring how they can be made adaptive to improve parameter estimates with increasing data, as well as seamlessly detecting system (and therefore model) changes, thus being capable of recursively updating and reoptimizing a modified or new model.     

Exact solution approaches for bilevel lot-sizing

In this paper we propose exact solution methods for a bilevel uncapacitated lot-sizing problem with backlogs. This is an extension of the classical uncapacitated lot-sizing problem with backlogs, in which two autonomous and self-interested decision makers constitute a two-echelon supply chain. The leader buys items from the follower in order to meet external demand at lowest cost. The follower also tries to minimize its costs. Both parties may backlog. We study the leader’s problem, i.e., how to determine supply requests over time to minimize its costs in view of the possible actions of the follower. We develop two mixed-integer linear programming reformulations, as well as cutting planes to cut off feasible, but suboptimal solutions. We compare the reformulations on a series of benchmark instances.     

On the machine scheduling problem with job delivery coordination

This paper examines two scheduling problems with job delivery coordination, in which each job demands different amount of storage space during transportation. For the first problem, in which jobs are processed on a single machine and delivered by one vehicle to a customer, we present a best possible approximation algorithm with a worst-case ratio arbitrarily close to 3/2. For the second problem, which differs from the first problem in that jobs are processed by two parallel machines, we give an improved algorithm with a worst-case ratio 5/3.     

A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge

This paper considers a two-stage distribution problem of a supply chain that is associated with a fixed charge. Two kinds of cost are involved in this problem: a continuous cost that linearly increases with the amount transported between a source and a destination, and secondly, a fixed charge, that incurs whenever there exists a transportation of a non-zero quantity between a source and a destination. The objective criterion is the minimisation of the total cost of distribution. A genetic algorithm (GA) that belongs to evolutionary search heuristics is proposed and illustrated. The proposed methodology is evaluated for its solution quality by comparing it with the approximate and lower bound solutions. Thus, the comparison reveals that the GA generates better solution than the approximation method and is capable of providing solution either equal or closer to the lower bound solution of the problem.     

Time-dependent optimization of a multi-item uncertain supply chain network: A hybrid approximation algorithm

We consider the uncertain least cost shipping problem. The input is a multi-item supply chain network with time-evolving uncertain costs and capacities. Exploiting the operational law of uncertainty theory, a mathematical model of the problem is established and the indeterminacy factors are tackled. We use the scaling idea together with transformation approach and uncertainty programming to develop a hybrid algorithm to optimize and obtain the uncertainty distribution of the total shipping cost. We analyze the practical performance of the algorithm and present an illustrative example.     

A solution method for a car fleet management problem with maintenance constraints

The problem retained for the ROADEF’99 international challenge was an inventory management problem for a car rental company. It consists in managing a given fleet of cars in order to satisfy requests from customers asking for some type of cars for a given time period. When requests exceed the stock of available cars, the company can either offer better cars than those requested, subcontract some requests to other providers, or buy new cars to enlarge the available stock. Moreover, the cars have to go through a maintenance process at a regular basis, and there is a limited number of workers that are available to perform these maintenances. The problem of satisfying all customer requests at minimum cost is known to be NP-hard. We propose a solution technique that combines two tabu search procedures with algorithms for the shortest path, the graph coloring and the maximum weighted independent set problems. Tests on benchmark instances used for the ROADEF’99 challenge give evidence that the proposed algorithm outperforms all other existing methods (thirteen competitors took part to this contest).     

Endogenous information acquisition in supply chain management

In this paper, we analyze an endogenous determination of efforts put into information acquisition and its impact on supply chain management. More specifically, we consider a supplier who sells a product to a buyer during a single selling season. Prior to placing an order with the supplier, the buyer has an option to acquire additional information about the demand by hiring experts (who are capable of providing forecasts). Because a commission fee must be paid to each hired expert, there exists a tradeoff between the cost and the value of the information, and the buyer needs to determine how much information to acquire. We derive the optimal information-acquisition level in an integrated setting and compare it with that determined in a decentralized setting. We also analyze several types of supply contracts to examine if they can coordinate the supply chain and allow an arbitrary division of system profit between the supplier and the buyer.     

Wholesale price rebate vs. capacity expansion: The optimal strategy for seasonal products in a supply chain

We consider a supply chain in which one manufacturer sells a seasonal product to the end market through a retailer. Faced with uncertain market demand and limited capacity, the manufacturer can maximize its profits by adopting one of two strategies, namely, wholesale price rebate or capacity expansion. In the former, the manufacturer provides the retailer with a discount for accepting early delivery in an earlier period. In the latter, the production capacity of the manufacturer in the second period can be raised so that production is delayed until in the period close to the selling season to avoid holding costs. Our research shows that the best strategy for the manufacturer is determined by three driving forces: the unit cost of holding inventory for the manufacturer, the unit cost of holding inventory for the retailer, and the unit cost of capacity expansion. When the single period capacity is low, adopting the capacity expansion strategy dominates as both parties can improve their profits compared to the wholesale price rebate strategy. When the single period capacity is high, on the other hand, the equilibrium outcome is the wholesale price rebate strategy.     

A continuous DC programming approach to the strategic supply chain design problem from qualified partner set

We present a new continuous approach based on the DC (difference of convex functions) programming and DC algorithms (DCA) to the problem of supply chain design at the strategic level when production of a new market opportunity has to be launched among a set of qualified partners. A well known formulation of this problem is the mixed integer linear program. In this paper, we reformulate this problem as a DC program by using an exact penalty technique. The proposed algorithm is a combination of DCA and Branch and Bound scheme. It works in a continuous domain but provides mixed integer solutions. Numerical simulations on many empirical data sets show the efficiency of our approach with respect to the standard Branch and Bound algorithm.