A Hybrid Genetic Algorithm for the Single Machine Scheduling Problem

A hybrid genetic algorithm (HGA) is proposed for the single machine, single stage, scheduling problem in a sequence dependent setup time environment within a fixed planning horizon (SSSDP). It incorporates the elitist ranking method, genetic operators, and a hill-climbing technique in each searching area. To improve the performance and efficiency, hill climbing is performed by uniting the Wagner-Whitin Algorithm with the problem-specific knowledge. The objective of the HGA is to minimize the sum of setup cost, inventory cost, and backlog cost. The HGA is able to obtain a superior solution, if it is not optimal, in a reasonable time. The computational results of this algorithm on real life SSSDP problems are promising. In our test cases, the HGA performed up to 50% better than the Just-In-Time heuristics and 30% better than the complete batching heuristics.     

Synchronization in supply chains: implications for design and management

Supply chain management literature calls for coordination between the different members of the chain. Materials should be moved from one supplier to the next according to a just-in-time schedule. In this paper, we show that for many supply chain configurations, complete synchronization will result in some members of the chain being ‘losers’ in terms of cost. We develop an algorithm for optimal synchronization of supply chains and provide some guidelines for incentive alignment along the supply chain. In developing the model, we use the economic delivery and scheduling problem model and analyze supply chains dealing with single and multiple components. For single-component supply chains, we derive a closed-form expression for the optimal synchronized cycle time. For multi-component supply chains, we develop an algorithm for finding the optimal synchronized cycle time. We test the performance of the algorithm and show that it provides optimal solutions for a wide range of problems. We illustrate the models with numerical examples.     

带有乘积型多目标权函数的调度谈判问题

在供应链环境下的生产活动中,各成员对所辖资源具有独立的支配权,因此需要合理的机制使得协同调度方案得以实施,以提高供应链整体的效率.研究由具备不同讨价还价能力的成员所组成的供应链,建立了以纳什讨价还价公理体系为基础的调度谈判模型.在装配系统中,讨论两供应商关于交付顺序的协商.为求取纳什谈判解,提出了一类新的以多目标乘积项作为目标函数的调度问题.对于单机型供应商,新问题的计算复杂性尚未确定,设计了一种多项式时间的启发式算法以求得近优解,并通过数值算例进行验证.该谈判模型为供应链中各成员提供了一种合理的调度协调机制.     

A Birnbaum-importance based genetic local search algorithm for component assignment problems

This paper considers the component assignment problem (CAP) of finding the optimal assignment of n available components to n positions in a system such that the system reliability is maximized. To solve the CAP, an important type of problems in reliability, we propose a Birnbaum-importance based genetic local search (BIGLS) algorithm in which a local search using the Birnbaum importance is embedded into the genetic algorithm. This paper presents comprehensive numerical tests to compare the performance of the BIGLS with a general genetic algorithm and a Birnbaum-importance based two-stage heuristic. The testing results show that the BIGLS is robust (with respect to its random operations) and effective, and outperforms two benchmark methods in terms of solution quality. It demonstrates the effectiveness of embedding the Birnbaum importance in the local search under the genetic evolutionary mechanism.     

Optimizing Multi-stage Production for an Assembly-Type Supply Chain with Unequal Sized Batch Shipments

This paper studies the multi-stage logistics and inventory problem in an?assembly-type supply chain where a uniform lot size is produced uninterruptedly with a single setup at each stage. Partial lots, or sub-batches, can be transported to next stage upon completion. Unequal sub-batch sizes at each stage follow geometric series and the numbers of sub-batches across stages are allowed to be different. Since the mainline and each branch line of an assembly-type supply chain are series-type supply chains, a model of the series-type supply chain is first established and a model of the assembly-type supply chain is subsequently developed. Optimization algorithms that determine the economic lot sizes, the optimal sub-batch sizes and the number of sub-batches for each stage are developed. The polynomial-time algorithms incorporate the optimality properties derived in the paper to find the lower and upper bounds of the solutions by constructing the solution ranges and then the optimal solutions accordingly.     

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.     

The economic lot scheduling problem under extended basic period and power-of-two policy

The economic lot scheduling problem schedules the production of several different products on a single machine over an infinite planning horizon. In this paper, a nonlinear integer programming model is used to determine the optimal solution under the extended basic period and power-of-two policy. A small-step search algorithm is presented to find a solution which approaches optimal when the step size approaches zero, where a divide-and-conquer procedure is introduced to speed up the search. Further a faster heuristic algorithm is proposed which finds the same solutions in almost all the randomly generated sample cases.     

A genetic algorithm for optimal operating parameters of VMI system in a two-echelon supply chain

This paper deals with the operational issues of a two-echelon single vendor–multiple buyers supply chain (TSVMBSC) model under vendor managed inventory (VMI) mode of operation. The operational parameters to the above model are: sales quantity and sales price that determine the channel profit of the supply chain, and contract price between the vendor and the buyer, which depends upon the understanding between the partners on their revenue sharing. In order to find out the optimal sales quantity for each buyer in TSVMBSC problem, a mathematical model is formulated. Optimal sales price and acceptable contract price at different revenue share are subsequently derived with the optimal sales quantity. A genetic algorithm (GA) based heuristic is proposed to solve this TSVMBSC problem, which belongs to nonlinear integer programming problem (NIP). The proposed methodology is evaluated for its solution quality. Furthermore, the robustness of the model with its parameters, which fluctuate frequently and are sensitive to operational features, is analysed.     

Optimal control of bioprocess systems using hybrid numerical optimization algorithms

In the paper, we consider the bioprocess system optimal control problem. Generally speaking, it is very difficult to solve this problem analytically. To obtain the numerical solution, the problem is transformed into a parameter optimization problem with some variable bounds, which can be efficiently solved using any conventional optimization algorithms, e.g. the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. However, in spite of the improved Broyden–Fletcher–Goldfarb–Shanno algorithm is very efficient for local search, the solution obtained is usually a local extremum for non-convex optimal control problems. In order to escape from the local extremum, we develop a novel stochastic search method. By performing a large amount of numerical experiments, we find that the novel stochastic search method is excellent in exploration, while bad in exploitation. In order to improve the exploitation, we propose a hybrid numerical optimization algorithm to solve the problem based on the novel stochastic search method and the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. Convergence results indicate that any global optimal solution of the approximate problem is also a global optimal solution of the original problem. Finally, two bioprocess system optimal control problems illustrate that the hybrid numerical optimization algorithm proposed by us is low time-consuming and obtains a better cost function value than the existing approaches.     

Scheduling and lot sizing models for the single-vendor multi-buyer problem under consignment stock partnership

We consider a centralized supply chain composed of a single vendor serving multiple buyers and operating under consignment stock arrangement. Solving the general problem is hard as it requires finding optimal delivery schedule to the buyers and optimal production lot sizes. We first provide a nonlinear mixed integer programming formulation for the general scheduling and lot sizing problem. We show that the problem is NP-hard in general. We reformulate the problem under the assumption of ‘zero-switch rule’. We also provide a simple sequence independent lower bound to the solution of the general model. We then propose a heuristic procedure to generate a near-optimal delivery schedule. We assess the cost performance of that heuristic by conducting sensitivity analysis on the key model parameters. The results show that the proposed heuristic promises substantial supply-chain cost savings that increase as the number of buyers increases.     

A discrete particle swarm optimization for lot-streaming flowshop scheduling problem

We consider an n-job, m-machine lot-streaming problem in a flowshop with equal-size sublots where the objective is to minimize the total weighted earliness and tardiness. To solve this problem, we first propose a so-called net benefit of movement (NBM) algorithm, which is much more efficient than the existing linear programming model for obtaining the optimal starting and completion times of sublots for a given job sequence. A new discrete particle swarm optimization (DPSO) algorithm incorporating the NBM algorithm is then developed to search for the best sequence. The new DPSO improves the existing DPSO by introducing an inheritance scheme, inspired by a genetic algorithm, into particles construction. To verify the proposed DPSO algorithm, comparisons with the existing DPSO algorithm and a hybrid genetic algorithm (HGA) are made. Computational results show that the proposed DPSO algorithm with a two-point inheritance scheme is very competitive for the lot-streaming flowshop scheduling problem.     

A new VRPPD model and a hybrid heuristic solution approach for e-tailing

We analyze a business model for e-supermarkets to enable multi-product sourcing capacity through co-opetition (collaborative competition). The logistics aspect of our approach is to design and execute a network system where “premium” goods are acquired from vendors at multiple locations in the supply network and delivered to customers. Our specific goals are to: (i) investigate the role of premium product offerings in creating critical mass and profit; (ii) develop a model for the multiple-pickup single-delivery vehicle routing problem in the presence of multiple vendors; and (iii) propose a hybrid solution approach. To solve the problem introduced in this paper, we develop a hybrid metaheuristic approach that uses a Genetic Algorithm for vendor selection and allocation, and a modified savings algorithm for the capacitated VRP with multiple pickup, single delivery and time windows (CVRPMPDTW). The proposed Genetic Algorithm guides the search for optimal vendor pickup location decisions, and for each generated solution in the genetic population, a corresponding CVRPMPDTW is solved using the savings algorithm. We validate our solution approach against published VRPTW solutions and also test our algorithm with Solomon instances modified for CVRPMPDTW.     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over

In this paper, the multi-item, single-level, capacitated, dynamic lot sizing problem with set-up carry-over and backlogging, abbreviated to CLSP⁺, is considered. The problem is formulated as a mixed integer programming problem. A heuristic method consisting of four elements: (1) a demand shifting rule, (2) lot size determination rules, (3) checking feasibility conditions and (4) set-up carry-over determination, provides us with an initial feasible solution. The resulting feasible solution is improved by adopting the corresponding set-up and set-up carry-over schedule and re-optimizing it by solving a minimum-cost network flow problem. Then the improved solution is used as a starting solution for a tabu search procedure, with the value of moves assessed using the same minimum-cost network problem. Computational results on randomly generated problems show that the algorithm, which is coded in C++, is able to provide optimal solutions or solutions extremely close to optimal. The computational efficiency makes it possible to solve reasonably large problem instances routinely on a personal computer.     

An exact algorithm for a cross-docking supply chain network design problem

This paper proposes a branch-and-price algorithm as an exact algorithm for the cross-docking supply chain network design problem introduced by one of the authors of this paper. The objective is to optimally locate cross-docking (CD) centres and allocate vehicles for direct transportation services from the associated origin node to the associated CD centre or from the associated CD centre to the associated destination node so as to satisfy a given set of freight demands at minimum cost subject to the associated service (delivery) time restriction. A set-partitioning-based formulation is derived for the problem for which some solution properties are characterized. Based on the properties, a branch-and-price algorithm is derived. The properties can also be used in deriving any efficient local search heuristics with the move operation (neighbourhood search operation) of modifying assignment of some freight demands from current CD centres to other CD centres. Computational experiments show that the branch-and-price algorithm is effective and efficient and also that the solution properties contribute to improve the efficiency of the local search heuristics.     

智能制造环境下的备件生产与运输协同调度问题研究

智能制造和即时配送环境下的备件生产与运输协同调度问题是目前国内研究的一大热点,这是因为备件供应链响应速度已成为当前备件制造企业赢得客户的关键因素。为了提高客户满意度,尽可能缩短从客户下达定制化生产订单到订单配送完成的时间,本文建立了以所有客户总等待时间最短为目标的混合整数规划模型和集合覆盖模型,推导了最优解性质,并设计改进的分支定价算法求得最优解。通过将小规模算例结果与CPLEX进行对比,验证了模型和算法的有效性。多组算例测试结果表明,所提出的模型和算法可以有效提升智能制造环境下的备件供应链运作效率。     

Progressive genetic algorithm for solution of optimization problems with nonlinear equality and inequality constraints

A new approach, identified as progressive genetic algorithm (PGA), is proposed for the solutions of optimization problems with nonlinear equality and inequality constraints. Based on genetic algorithms (GAs) and iteration method, PGA divides the optimization process into two steps; iteration and search steps. In the iteration step, the constraints of the original problem are linearized using truncated Taylor series expansion, yielding an approximate problem with linearized constraints. In the search step, GA is applied to the problem with linearized constraints for the local optimal solution. The final solution is obtained from a progressive iterative process. Application of the proposed method to two simple examples is given to demonstrate the algorithm.     

Heuristic approaches to determine base-stock levels in a serial supply chain with a single objective and with multiple objectives

This paper deals with the problem of determination of installation base-stock levels in a serial supply chain. The problem is treated first as a single-objective inventory-cost optimization problem, and subsequently as a multi-objective optimization problem by considering two cost components, namely, holding costs and shortage costs. Variants of genetic algorithms are proposed to determine the best base-stock levels in the single-objective case. All variants, especially random-key gene-wise genetic algorithm (RKGGA), show an excellent performance, in terms of convergence to the best base-stock levels across a variety of supply chain settings, with minimum computational effort. Heuristics to obtain base-stock levels are proposed, and heuristic solutions are introduced in the initial population of the RKGGA to expedite the convergence of the genetic search process. To deal with the multi-objective supply-chain inventory optimization problem, a simple multi-objective genetic algorithm is proposed to obtain a set of non-dominated solutions.     

Fair transfer price and inventory holding policies in two-enterprise supply chains

A key issue in supply chain optimisation involving multiple enterprises is the determination of policies that optimise the performance of the supply chain as a whole while ensuring adequate rewards for each participant.In this paper, we present a mathematical programming formulation for fair, optimised profit distribution between echelons in a general multi-enterprise supply chain. The proposed formulation is based on an approach applying the Nash bargaining solution for finding optimal multi-partner profit levels subject to given minimum echelon profit requirements.The overall problem is first formulated as a mixed integer non-linear programming (MINLP) model. A spatial and binary variable branch-and-bound algorithm is then applied to the above problem based on exact and approximate linearisations of the bilinear terms involved in the model, while at each node of the search tree, a mixed integer linear programming (MILP) problem is solved. The solution comprises inter-firm transfer prices, production and inventory levels, flows of products between echelons, and sales profiles.The applicability of the proposed approach is demonstrated by a number of illustrative examples based on industrial processes.     

The simplified partial digest problem: Approximation and a graph-theoretic model

The goal of the simplified partial digest problem (SPDP) is motivated by the reconstruction of the linear structure of a DNA chain with respect to a given nucleotide pattern, based on the multiset of distances between the adjacent patterns (interpoint distances) and the multiset of distances between each pattern and the two unlabeled endpoints of the DNA chain (end distances). We consider optimization versions of the problem, called SPDP-Min and SPDP-Max. The aim of SPDP-Min (SPDP-Max) is to find a DNA linear structure with the same multiset of end distances and the minimum (maximum) number of incorrect (correct) interpoint distances. Results are presented on the worst-case efficiency of approximation algorithms for these problems. We suggest a graph-theoretic model for SPDP-Min and SPDP-Max, which can be used to reduce the search space for an optimal solution in either of these problems. We also present heuristic polynomial time algorithms based on this model. In computational experiments with randomly generated and real-life input data, our best algorithm delivered an optimal solution in 100% of the instances for a number of restriction sites not greater than 50.