An imperialist competitive algorithm for a mixed-model assembly line sequencing problem

This paper presents a novel imperialist competitive algorithm (ICA) to a just-in-time (JIT) sequencing problem where variations of production rate are to be minimized. This type of problem is NP-hard. Up to now, some heuristic and meta-heuristic approaches are proposed to minimize the production rates variation. This paper presents a novel algorithm for optimization which inspired by imperialistic competition in real world. Sequences of products where minimize the production rates variation is desired. Performance of the proposed ICA was compared against a genetic algorithm (GA) in small, medium and large problems. Experimental results show the ICA performance against GA.     

Developing model-based software to optimise wheat storage and transportation: A real-world application

This paper investigates a real-world case of a logistical management problem. We determine the optimal amounts of wheat to be transported from each producing province to each consuming province per month across the year. The problem was formulated as a linear integer programming (LIP) model, which could then be solved using LINGO optimisation software. As the LIP model needs to be run each month, a genetic algorithm (GA) was developed to solve the real-size problems in a reasonable time period. The solutions obtained by LINGO are compared with those obtained from the GA and the results show that the developed GA is efficient in terms of computational time and the quality of the solutions obtained.     

An approximate solution to a jit-based ordering system

In this paper we consider a multi-stage multi-product production, inventory and transportation system including lot production processes and develop a goal programming model for a pull type ordering system based on the concept of a Just-In-Time(JIT) production system. We also present a pragmatic approach which reduces the required computational time for the formulated mixed integer goal programming problem using a mathematical programming modeling language. The proposed solution procedure is realized utilizing the post-optimal analysis which can be performed by the modeling language.     

Parallel machine scheduling with flexible resources

Parallel machine flexible resource scheduling (PMFRS) problems consider an additional flexible resource (e.g. operators), which can be freely allocated to any jobs and/or any machines and may speed-up the process in proportion to its amount. If job–machine assignment is unspecified, the problem is referred to as unspecified PMFRS (UPMFRS). This paper reviews the mathematical models of both PMFRS and UPMFRS problems in the literature and not only gives some extensions to the model of dynamic PMFRS problem but also presents integer programming (IP) models for static and dynamic UPMFRS problems with the objective of minimizing makespan. To solve large-sized dynamic PMFRS and UPMFRS problems, a relaxed IP based constraint programming (CP) approach is also proposed. All IP models and the proposed IP/CP approach are tested with an extensive computational study. The results of the computational experiments are discussed with respect to the major parameters of the problem and conclusions are drawn.     

A case study of scheduling storage tanks using a hybrid geneticalgorithm

This paper proposes the application of a hybrid genetic algorithm (GA) for scheduling storage tanks. The proposed approach integrates GAs and heuristic rule-based techniques, decomposing the complex mixed-integer optimization problem into integer and real-number subproblems. The GA string considers the integer problem and the heuristic approach solves the real-number problems within the GA framework. The algorithm is demonstrated for three test scenarios of a water treatment facility at a port and has been found to be robust and to give a significantly better schedule than those generated using a random search and a heuristic-based approach     

A genetic algorithm based heuristic to the multi-period fixed charge distribution problem

This paper proposes a genetic algorithm (GA) based heuristic to the multi-period fixed charge distribution problem associated with backorder and inventories. The objective is to determine the size of the shipments, backorder and inventories at each period, so that, the total cost incurred during the entire period towards transportation, backorder and inventories is minimum. The model is formulated as pure integer nonlinear programming and 0-1 mixed integer linear programming problems, and proposes a GA based heuristic to provide solution to the above problem. The proposed GA based heuristic is evaluated by comparing their solutions with lower bound, LINGO solver and approximate solutions. The comparisons reveal that the GA generates better solutions than the approximate solutions, and is capable of providing solutions equal to LINGO solutions and closer to the lower bound value of the problems.     

A parallel multistart algorithm for the closest string problem

In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics to solve large instances. Several approximation algorithms have been designed for the CSP, but all of them have a poor performance guarantee. Recently some researchers have shown empirically that integer programming techniques can be successfully used to solve moderate-size instances (10–30 strings each of which is 300–800 characters long) of the CSP. However, real-world instances are larger than those tested. In this paper we show how a simple heuristic can be used to find near-optimal solutions to that problem. We implemented a parallel version of this heuristic and report computational experiments on large-scale instances. These results show the effectiveness of our approach.     

基于JIT-RVC算法的软测量的研究及其应用

针对传统JIT(Just-in-time)算法单纯以距离为数据选择的缺陷,以及局部模型鲁棒性差,稳定性不强的特点,文中一方面提出了与Jolliffe参数相结合的鲁棒最近相关算法,使得JIT算法能够在离群点出现的情况下正确的选择建模数据,另一方面,还将合成随机变系数概率模型算法(Ensemble RVC)作为JIT算法的局部模型构成了JIT-RVC算法,于此强化了传统JIT算法的非线性逼近能力和鲁棒性。最后,通过强烈干扰情况下的污水生化处理的BOD_5软测量预测仿真结果证明了算法的有效性,特别要指出的是相较于JIT-PLS算法,JIT-RVC算法的RMSE指标减少了55%,而相关系数提高了53%。     

A hybrid genetic algorithm for the electric vehicle routing problem with time windows

Driven by the newlegislation on greenhouse gas emissions, carriers began to use electric vehicles (EVs) for logistics transportation. This paper addresses an electric vehicle routing problem with time windows (EVRPTW). The electricity consumption of EVs is expressed by the battery state-of-charge (SoC). To make it more realistic, we take into account the terrain grades of roads, which affect the travel process of EVs. Within our work, the battery SoC dynamics of EVs are used to describe this situation. We aim to minimize the total electricity consumption while serving a set of customers. To tackle this problem, we formulate the problem as a mixed integer programming model. Furthermore, we develop a hybrid genetic algorithm (GA) that combines the 2-opt algorithm with GA. In simulation results, by the comparison of the simulated annealing (SA) algorithm and GA, the proposed approach indicates that it can provide better solutions in a short time.     

The determination of the optimal number of kanbans in a Just-In-Time production system

Just-In-Time (JIT) production is supported by the kanban inventory control and product scheduling system. It is important for production managers to determine the optimal number of kanbans in order to successfully operate a multi-line, multi-stage kanban production system. All relevant factors and costs must be considered before arriving at the optimal number of kanbans. In this paper, some JIT production factors such as demand, in process inventory, inventory and labor costs, subcontractor's supply capacity, and workload are discussed. And then, a model formulation using mixed integer goal programming is presented. Finally, a numerical example is presented in order to verify our model.     

Vehicle routing problem with time windows considering overtime and outsourcing vehicles

The vehicle routing problem with time windows (VRPTW) is an important problem in third-party logistics and supply chain management. We extend the VRPTW to the VRPTW with overtime and outsourcing vehicles (VRPTWOV), which allows overtime for drivers and the possibility of using outsourced vehicles. This problem can be applied to third-party logistics companies for managing central distributor-local distributors, local distributor-retailers (or customers), and manufacturers. We developed a mixed integer programming model, a genetic algorithm (GA), and a hybrid algorithm based on simulated annealing. The computational results demonstrate the efficiency of the developed algorithms. We also develop a decision support system for the VRPTWOV that is equipped with a vehicle route rescheduling function for realistic situations based on the GA.     

Locating input and output points in facilities design - acomparison of constructive, evolutionary, and exact methods

This paper formulates and compares four new approaches to optimally locate the input and output station for each department within a facility design such that material handling costs are minimized. This problem is an NP-hard combinatorial problem with many real-life applications of considerable economic consequence. A genetic algorithm (GA) is shown to be an effective and efficient optimization method when compared to integer programming, simulated annealing, and three versions of a greedy constructive heuristic on a suite of test problems of varying size. Seeding versus random initialization of GA populations are compared     

Local search heuristics for the mobile facility location problem

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large-scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.     

求解资源受限项目调度问题的约束规划/数学规划混合算法

利用约束规划（constraintprogramming,CP）与数学规划（mathematicalprogramming,MP）结合的方法求解调度问题已经获得了一些较好的研究成果,正成为调度问题研究领域的一个新的热点研究方向．本文针对求解资源受限项目调度问题（RCPSP）的整数规划模型,设计了基于CP技术的问题和模型预处理方法,证明了整数规划模型的有效不等式定理,提出了通过将项目子网络图转化为加权最大团问题求解后获得有效不等式的方法．引用标准问题库PSPLIB中的一组典型问题进行求解实验,结果表明本文提出的有效不等式可以明显改进模型的求解质量和时间性能．论文最后对实验结果进行了深入讨论,讨论了未来的研究方向．     

JIT-transportation problem and its algorithm

This article introduces the (just-in-time) JIT-transportation problem, which requires that all demanded goods be shipped to their destinations on schedule, at a zero or minimal destination-storage cost. The JIT-transportation problem is a special goal programming problem with discrete constraints. This article provides a mathematical model for such a transportation problem and introduces the JIT solution, the deviation solution, the JIT deviation, etc. By introducing the B(λ)-problem, this article establishes the equivalence between the optimal solutions of the B(λ)-problem and the optimal solutions of the JIT-transportation problem, and then provides an algorithm for the JIT-transportation problems. This algorithm is proven mathematically and is also illustrated by an example.     

遗传算法在系统可靠性优化中的应用

研究性等价、体积和重量约束条件下，多级串联系统和桥式网络系统可靠性优化问题.使用遗传算法对该问题进行求解，利用基于排名的选择方法和最优保存策略，改善了遗传算法的收敛性能。计算机仿真实验结果表明，用遗传算法求解该问题是有效的。     

Determination of number of kanbans in a supply chain system via Memetic algorithm

In this research multi-stage supply chain system which is controlled by kanban system, is evaluated. In kanban system, decision making is based on determination of the number of kanbans as well as batch sizes. This paper attempts to model supply chain system with regard to costs under just-in-time (JIT) production philosophy. Since adopted model is of mixed integer non-linear programming (MINLP) type and solving it by exact algorithm such as branch and bound (B&B) takes a lot of time, a heuristic method via Memetic algorithm (MA) is presented. Some problems are solved by our proposed MA to illustrate its performance.     

A heuristic for the skiving and cutting stock problem in paper and plastic film industries

This paper investigates the skiving and cutting stock problem (SCSP) encountered in the paper and plastic film industries, in which a set of nonstandard reels generated from previous cutting processes are used to produce finished rolls through the skiving and cutting process. First, reels are skived together lengthwise to form a reel‐pyramid (a polygon), and then the reel‐pyramid is cut into finished rolls of small widths. Depending on if a reel can be divided lengthwise into subreels to form the reel‐pyramid, the problem can be classified into divisible SCSP (DSCSP) and indivisible SCSP (ISCSP). In this paper, two integer programming (IP) models are proposed for DSCSP and ISCSP, respectively. A sequential value correction procedure combined with the two IP models (SVCTIP) is developed to solve the two SCSPs. The effectiveness of the SVCTIP is demonstrated through extensive computational tests.     

Genotype–phenotype heuristic approaches for a cutting stock problem with circular patterns

The cutting stock problem has been studied in the context of different industrial applications inducing NP-hard problems in most instances. However, the application in sawmill has not received the same attention. In this paper, we deal with the problem of determining the number of logs to cut over a period of several days and the geometry of sawmill patterns in order to satisfy the demand while minimizing the loss of material. First, the problem is formulated as an integer programming problem of the form of a constrained set covering problem where the knowledge of a priori cutting patterns is necessary to generate its columns. In our implementation, these patterns are obtained using a genetic algorithm (GA) or a simulated annealing method (SA). Then, two different approaches are introduced to solve the problem. The first approach includes two methods that combine a metaheuristic to generate the number of logs and a constructive heuristic to generate the cutting patterns for each of the logs. In the second approach, we use an exact procedure CPLEX to solve the integer programming model where the cutting patterns are generated with the GA method (GA+CPLEX) or the SA method (SA+CPLEX). These four methods are compared numerically on 11 semi-randomly generated problems similar to those found in real life. The best results for the loss are obtained with the two-stage GA+CPLEX approach that finds the best values for 7 problems.     

Sensor deployment optimization methods to achieve both coverage and connectivity in wireless sensor networks

In this study, we aim to cover a sensing area by deploying a minimum number of wireless sensors while maintaining the connectivity between the deployed sensors. The problem may be reduced to a two-dimensional critical coverage problem which is an NP-Complete problem. We develop an integer linear programming model to solve the problem optimally. We also propose a local search (LS) algorithm and a genetic algorithm (GA) as approximate methods. We verify by computational experiments that the integer linear model, using Cplex, is able to provide an optimal solution of all our small and medium size problems. We also show that the proposed methods outperform some regular sensor deployment patterns.