Two-sided assembly line balancing: A genetic algorithm approach

A two-sided assembly line balancing problem is typically found in plants producing large-sized high-volume products, e.g. buses and trucks. The features specific to the assembly line are described in this paper, which are associated with those of: (i) two-sided assembly lines; (ii) positional constraints; and (iii) balancing at the operational time. There exists a large amount of literature in the area of line balancing, whereby it has mostly dealt with one-sided assembly lines. A new genetic algorithm is developed to solve the problem, and its applicability and extensibility are discussed. A genetic encoding and decoding scheme, and genetic operators suitable for the problem are devised. This is particularly emphasized using problem-specific information to enhance the performance of the genetic algorithm (GA). The proposed GA has a strength that it is flexible in solving various types of assembly line balancing problems. An experiment is carried out to verify the performance of the GA, and the results are reported.     

Mixed integer (0–1) fractional programming for decision support in paper production industry

This paper presents an effective and efficient method for solving a special class of mixed integer fractional programming (FP) problems. We take a classical reformulation approach for continuous FP as a starting point and extend it for solving a more general class of mixed integer (0–1) fractional programming problems.To stress the practical relevance of the research we focus on a real-life application in paper production industry. The constantly advancing physical knowledge of large scale pulp and paper production did have a substantial impact on an existing DSS in which mixed integer (0–1) fractional programming is introduced. We show that the motivation to solve a real-life fractional programming problem can provide the basis for a new approach in a new context that has an added value of its own, even outside the given application area. We describe the main characteristics of the DSS, the necessity to develop a non-iterative solution procedure and demonstrate both the effectiveness and efficiency of the proposed approach from practical data sets.     

面向专家的知识库优化

知识库的质量是影响智能系统性能的主要因素 ,而知识获取一直是设计智能系统的瓶颈问题 ,这是由于目前人类认识的局限性 ,导致知识工程师和专家之间的不协调关系造成的 .为克服上述不利局面 ,本文利用粗糙集等理论 ,得到含有噪声的初始知识库 ,然后采用遗传算法、可视化技术和知识校验等技术对规则库和案例库进行了优化 .从而在知识获取过程中建立了知识工程师和专家之间的新型的关系 ,其中专家处于中心地位 ,知识工程师只是起辅助作用 ,即整个知识获取过程是面向专家的     

分布决策环境下生产-分销协同计划研究

针对分布决策环境下因信息不对称使得供应链协同计划求解困难及难以达到全局最优的问题,本文利用多层规划理论和方法构建一个供应链生产-分销协同计划模型,采用模糊交互式协商和遗传算法的优化求解方法对协同计划模型进行求解。该方法求解的结果是一组满足约束条件的满意解,各节点企业根据自身偏好和约束信息决定是否接受该满意解,或者修正各自目标满意度隶属函数重新求解。决策过程具有一定的柔性。最后通过算例给出供应链生产-分销协同计划满意解的求解过程,对文中所建立的模型和算法进行了有效地说明和验证。求解结果说明该模型和协商方法能够有效地解决非对称信息条件下供应链生产-分销协同计划的求解和冲突问题。     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.     

Interactive fuzzy goal programming for multi-objective transportation problems

This paper presents an interactive fuzzy goal programming approach to determine the preferred compromise solution for the multi-objective transportation problem. The proposed approach considers the imprecise nature of the input data by implementing the minimum operator and also assumes that each objective function has a fuzzy goal. The approach focuses on minimizing the worst upper bound to obtain an efficient solution which is close to the best lower bound of each objective function. The solution procedure controls the search direction via updating both the membership values and the aspiration levels. An important characteristic of the approach is that the decision maker's role is concentrated only in evaluating the efficient solution to limit the influences of his/her incomplete knowledge about the problem domain. In addition, the proposed approach can be applied to solve other multi-objective decision making problems. The performance of this solution approach is evaluated by comparing its results with that of the two existing methods in the literature.     

A simulated annealing algorithm for designing cellular manufacturing systems with productivity consideration

In this paper, we propose a productivity model for solving the machine-part grouping problem in cellular manufacturing (CM) systems. First, a non-linear 0-1 integer programming model is developed to identify machine groups and part families simultaneously. This model aims to maximize the system productivity defined as the ratio of total output to the total material handling cost. Second, an efficient simulated annealing (SA) algorithm is developed to solve large-scale problems. This algorithm provides several advantages over the existing algorithms. It forms part families and machine cells simultaneously. It also considers production volume, sales price, and maximum number of machines in each cell and total material handling cost. The proposed SA also has the ability to determine the optimum number of manufacturing cells. The performance of the developed models is tested on eight problems of different size and complexity selected from the literature. The results show the superiority of the SA algorithm over the mathematical programming model in both productivity and computational time.     

Multi-time scale Markov decision process approach to strategic network growth of reverse supply chains

This paper addresses a complex set of decisions that surround the growth over time of reverse supply chain networks that collect used products for reuse, refurbishment, and/or recycling by processors. The collection network growth problem is decomposed into strategic, tactical and operational problems. This paper focuses on the strategic problem which is to determine how to allocate capital budget resource effectively to grow the network to meet long term collection targets and collection cost constraints. We model the strategic problem as a Markov decision process which can also be posed as multi-time scale Markov decision problem. The recruitment problem in a tactical level appears as a sub-problem for the strategic model. Using dynamic programming, linear programming and Q-Learning approaches, an heuristic is implemented to solve realistically sized problems. A numerical study demonstrates that the heuristic can obtain a good solution for the large-scale problem in reasonable time which is not possible when trying to obtain the optimal solution with the exact DP approach.     

基于粗糙集条件信息熵的权重确定方法

权重确定是管理决策和评价的重要环节,现有的权重确定方法基本依赖于专家的先验知识。粗糙集权重确定方法由于其不需要所处理数据集合的先验信息、充分体现数据客观性的特点在管理决策中得到日益广泛应用。但是,原有的粗糙集权重确定方法无法确定冗余属性的权重。本文针对粗糙集的信息表示比代数表示更全面的特点,通过粗糙集条件信息熵属性重要度的分析,提出了新的基于粗糙集条件信息熵的权重确定方法,并分析了其合理性。通过算例证明,新的条件信息熵权重确定方法可以解决原有粗糙集权重确定方法无法解决的问题,从而提高了方法的普适性和可解释性。     

A mathematical model and genetic algorithm-based approach for parallel two-sided assembly line balancing problem

Assembly lines are usually constructed as the last stage of the entire production system and efficiency of an assembly line is one of the most important factors which affect the performance of a complex production system. The main purpose of this paper is to mathematically formulate and to provide an insight for modelling the parallel two-sided assembly line balancing problem, where two or more two-sided assembly lines are constructed in parallel to each other. We also propose a new genetic algorithm (GA)-based approach in alternatively to the existing only solution approach in the literature, which is a tabu search algorithm. To the best of our knowledge, this is the first formal presentation of the problem as well as the proposed algorithm is the first attempt to solve the problem with a GA-based approach in the literature. The proposed approach is illustrated with an example to explain the procedures of the algorithm. Test problems are solved and promising results are obtained. Statistical tests are designed to analyse the advantage of line parallelisation in two-sided assembly lines through obtained test results. The response of the overall system to the changes in the cycle times of the parallel lines is also analysed through test problems for the first time in the literature.     

随机网络瓶颈容量扩张相关机会规划模型

文章研究的问题为,在不确定环境中,怎样去增加网络中一组边的容量到一个指定的容量,以至于网络瓶颈扩张的费用不超过给定的总费用上限的概率尽可能的大.本文假定每一条边的单位扩张费用Wi是一个随机的变量,它服从一定的概率分布.带有随机单位扩张费用W的网络瓶颈容量扩张问题可以根据一些规则,列出它的相关机会规划模型的通用表达式.随后,本文将网络瓶颈容量算法、随机模拟方法和遗传算法合成在一起,设计出该问题的混合智能通用算法.最后,给出数值算例.     

基于电商承诺送达机制的多目标低碳MDVRP优化研究

针对存在多配送站的电商物流配送问题,首先,考虑实际装载量对物流配送过程中车辆燃料消耗量的影响,建立燃料消耗量模型,并结合电商平台的承诺送达机制,构建配送延迟时间函数。随后,提出了以最小化物流成本和延迟收货时间的多目标多配送站车辆路径规划问题,建立该问题的混合整数规划模型。再次,采用基于分解的多目标遗传求解算法对问题进行求解。该算法采用矩阵编码的方式,设计了基于贪婪搜索策略的启发式初始化方法,考虑到贪婪搜索策略容易陷入局部最优的劣势,在算法迭代过程中,允许部分不可行解存在以扩大解空间的搜索范围,并进一步设计了遗传算法的交叉和变异算子。最后,以具体物流配送案例进行数值实验,实验结果表明所设计的算法对求解本文模型是有效的。     

An Arborescent Network Formulation and Dual Ascent Based Procedure for the Two-Stage Multi-Item Dynamic Demand Lotsize Problem

Traditional approaches for modeling and solving dynamic demand lotsize problems are based on Zangwill's single-source network and dynamic programming algorithms. In this paper, we propose an arborescent fixed-charge network (ARBNET) programming model and dual ascent based branch-and-bound procedure for the two-stage multi-item dynamic demand lotsize problem. Computational results show that the new approach is significantly more efficient than earlier solution strategies. The largest set of problems that could be solved using dynamic programming contained 4 end items and 12 time periods, and required 475.38 CPU seconds per problem. The dual ascent algorithms averaged .06 CPU seconds for this problem set, and problems with 30 end items and 24 time periods were solved in 85.65 CPU seconds. Similar results verify the superiority of the new approach for handling backlogged demand. An additional advantage of the algorithm is the availability of a feasible solution, with a known worst-case optimality gap, throughout the problem-solving process.     

Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs

Disassembling complex products is formally approached via network representation and subsequent mathematical modeling, aimed at selecting a good or optimum sequence of disassembly operations. This is done via heuristics, metaheuristics or mathematical programming. In contrast with heuristics and metaheuristics, which select a near-optimum solution, mathematical programming guarantees the selection of the global optimum. This problem is relatively simple if the disassembly costs can be assumed sequence independent. In practice, however, sequence dependent disassembly costs are frequently encountered, which causes NP-completeness of the problem. Although methods, e.g., based on the two-commodity network flow approach, are available to solve this constrained asymmetric Traveling Salesperson problem rigorously, this requires the introduction of integer variables. In this paper, a modification of the two-commodity network flow approach is proposed, which reduces the number of integer variables. This is applied to product structures that can be represented by a disassembly precedence graph. It is demonstrated that use of integer variables is completely avoided by iteratively solving a binary integer linear programming problem. This appears to be more efficient than solving the corresponding integer linear programming problem. It is demonstrated, on the basis of some cases, that this method might provide the exact solution of problems with increased complexity compared to those discussed so far in the literature. This appears particularly useful for evaluating heuristic and metaheuristic approaches.     

A genetic algorithm-based decomposition approach to solve an integrated equipment-workforce-service planning problem

We develop a new genetic algorithm to solve an integrated Equipment-Workforce-Service Planning problem, which features extremely large scales and complex constraints. Compared with the canonical genetic algorithm, the new algorithm is innovative in four respects: (1) The new algorithm addresses epistasis of genes by decomposing the problem variables into evolutionary variables, which evolve with the genetic operators, and the optimization variables, which are derived by solving corresponding optimization problems. (2) The new algorithm introduces the concept of Capacity Threshold and calculates the Set of Efficient and Valid Equipment Assignments to preclude unpromising solution spaces, which allows the algorithm to search much narrowed but promising solution spaces in a more efficient way. (3) The new algorithm modifies the traditional genetic crossover and mutation operators to incorporate the gene dependency in the evolutionary procedure. (4) The new algorithm proposes a new genetic operator, self-evolution, to simulate the growth procedure of an individual in nature and use it for guided improvements of individuals. The new genetic algorithm design is proven very effective and robust in various numerical tests, compared to the integer programming algorithm and the canonical genetic algorithm. When the integer programming algorithm is unable to solve the large-scale problem instances or cannot provide good solutions in acceptable times, and the canonical genetic algorithm is incapable of handling the complex constraints of these instances, the new genetic algorithm obtains the optimal or close-to-optimal solutions within seconds for instances as large as 84 million integer variables and 82 thousand constraints.     

Point‐of‐Dispensing Location and Capacity Optimization via a Decision Support System

Dispensing of mass prophylaxis can be critical to public health during emergency situations and involves complex decisions that must be made in a short period of time. This study presents a model and solution approach for optimizing point‐of‐dispensing (POD) location and capacity decisions. This approach is part of a decision support system designed to help officials prepare for and respond to public health emergencies. The model selects PODs from a candidate set and suggests how to staff each POD so that average travel and waiting times are minimized. A genetic algorithm (GA) quickly solves the problem based on travel and queuing approximations (QAs) and it has the ability to relax soft constraints when the dispensing goals cannot be met. We show that the proposed approach returns solutions comparable with other systems and it is able to evaluate alternative courses of action when the resources are not sufficient to meet the performance targets.     

A hybrid biased random key genetic algorithm approach for the unit commitment problem

This work proposes a hybrid genetic algorithm (GA) to address the unit commitment (UC) problem. In the UC problem, the goal is to schedule a subset of a given group of electrical power generating units and also to determine their production output in order to meet energy demands at minimum cost. In addition, the solution must satisfy a set of technological and operational constraints. The algorithm developed is a hybrid biased random key genetic algorithm (HBRKGA). It uses random keys to encode the solutions and introduces bias both in the parent selection procedure and in the crossover strategy. To intensify the search close to good solutions, the GA is hybridized with local search. Tests have been performed on benchmark large-scale power systems. The computational results demonstrate that the HBRKGA is effective and efficient. In addition, it is also shown that it improves the solutions obtained by current state-of-the-art methodologies.     

Managing stochastic demand in an Inventory Routing Problem with transportation procurement

We study an Inventory Routing Problem in which the supplier has a limited production capacity and the stochastic demand of the retailers is satisfied with procurement of transportation services. The aim is to minimize the total expected cost over a planning horizon, given by the sum of the inventory cost at the supplier, the inventory cost at the retailers, the penalty cost for stock-out at the retailers and the transportation cost. First, we show that a policy based just on the average demand can have a total expected cost infinitely worse than the one obtained by taking into account the overall probability distribution of the demand in the decision process. Therefore, we introduce a stochastic dynamic programming formulation of the problem that allows us to find an optimal policy in small size instances. Finally, we design and implement a matheuristic approach, integrating a rollout algorithm and an optimal solution of mixed-integer linear programming models, which is able to solve realistic size problem instances. Computational results allow us to provide managerial insights concerning the management of stochastic demand.     

A heuristic approximation algorithm of minimum dominating set based on rough set theory

The minimum dominating set of graph has been widely used in many fields, but its solution is NP-hard. The complexity and approximation accuracy of existing algorithms need to be improved. In this paper, we introduce rough set theory to solve the dominating set of undirected graph. First, the adjacency matrix of undirected graph is used to establish an induced decision table, and the minimum dominating set of undirected graph is equivalent to the minimum attribute reduction of its induced decision table. Second, based on rough set theory, the significance of attributes (i.e., vertices) based on the approximate quality is defined in induced decision table, and a heuristic approximation algorithm of minimum dominating set is designed by using the significance of attributes (i.e., vertices) as heuristic information. This algorithm uses forward and backward search mechanism, which not only ensures to find a minimal dominating set, but also improves the approximation accuracy of minimum dominating set. In addition, a cumulative strategy is used to calculate the positive region of induced decision table, which effectively reduces the computational complexity. Finally, the experimental results on public datasets show that our algorithm has obvious advantages in running time and approximation accuracy of the minimum dominating set.

     

A sustainable second-generation biodiesel supply chain network design problem under risk

This paper presents a multi-objective possibilistic programming model to design a second-generation biodiesel supply chain network under risk. The proposed model minimizes the total costs of biodiesel supply chain from feedstock supply centers to customer centers besides minimizing the environmental impact (EI) of all involved processes under a well-to-wheel perspective. Non-edible feedstocks are considered for biodiesel production. Variable cultivation cost of non-edible feedstock is assumed to be non-linear and dependent upon the amount of cultivated area. New formulation of possibilistic programming method is developed which is able to minimize the total mean and risk values of problems with possibilistic-based uncertainty. To solve the proposed multi-objective model, a hybrid solution approach based on flexible lexicographic and augmented ɛ-constraint methods is proposed which is capable to find appropriate efficient solutions from the Pareto-optimal set. The performance of the proposed possibilistic programming method as well as the developed solution approach are evaluated and validated through conducting a real case study in Iran. The outcome of this study demonstrates that high investment cost is required for improving the environmental impact and risk of sustainable biodiesel supply chain network design under risk. Decision maker preferences are required for suitable trade-off among total costs, risk values and environmental impact.