An adaptive tabu search approach for buffer allocation problem in unreliable non-homogenous production lines

The buffer allocation problem, i.e. how much buffer storage to allow and where to place it within the line, is an important research issue in designing production lines. In this study, a novel adaptive tabu search approach is proposed for solving buffer allocation problem in unreliable and non-homogeneous production lines. The objective is to maximize the throughput of the line, which is constrained by the capacity of each buffer space and also the total buffer capacity to allocate to these spaces. Besides proposing a new strategy to tune the parameters of tabu search adaptively during the search, an experimental study is carried out to select an intelligent initial solution scheme among three alternatives so as to decrease the search effort to obtain the best solutions. The performance of the proposed approach is evaluated by computational tests and very promising results are obtained.     

Two approaches for solving the buffer allocation problem in unreliable production lines

This paper presents an integrated approach to solve the buffer allocation problem in unreliable production lines so as to maximize the throughput rate of the line with minimum total buffer size. The proposed integrated approach has two control loops; the inner loop and the outer loop. While the inner loop control includes an adaptive tabu search algorithm proposed by Demir et al. [8], binary search and tabu search are proposed for the outer loop. These nested loops aim at minimizing the total buffer size to achieve the desired throughput level. To improve the efficiency of the proposed tabu search, alternative neighborhood generation mechanisms are developed. The performances of the proposed algorithms are evaluated by extensive computational experimentation, and the results are reported.     

Optimal buffer allocation in short μ-balanced unreliable production lines

In this work, we investigate the optimal buffer allocation in short μ-balanced production lines consisting of machines that are subject to breakdown. Repair times and times to failure are assumed exponential, whereas service times are allowed to follow the Erlang-k distribution (with k=1, 2, 4 and 8). By an improved enumeration procedure and applying the evaluative algorithm of Heavey et al. (European Journal of Operational Research 1993;68:69–89) for the calculation of throughput, we have examined in a systematic way several systems with 3, 4, 5, 6 and 7 stations and with a different total number of buffer slots. We have been able to give answers to some critical questions. These include the effect of the distribution of the service and repair times, the availability of the stations and the repair rates on the optimal buffer allocation and the throughput of the lines.     

Guided Local Search for Solving SAT and Weighted MAX-SAT Problems

In this paper, we show how Guided Local Search (GLS) can be applied to the SAT problem and show how the resulting algorithm can be naturally extended to solve the weighted MAX-SAT problem. GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms to help guide them out of local minima. GLS has been shown to be successful in solving a number of practical real-life problems, such as the traveling salesman problem, BT"s workforce scheduling problem, the radio link frequency assignment problem, and the vehicle routing problem. We present empirical results of applying GLS to instances of the SAT problem from the DIMACS archive and also a small set of weighted MAX-SAT problem instances and compare them with the results of other local search algorithms for the SAT problem.     

Evolutionary Optimization: Pitfalls and Booby Traps

Evolutionary computation (EC), a collective name for a range of metaheuristic black-box optimization algorithms, is one of the fastest-growing areas in computer science. Many manuals and "how-to"s on the use of different EC methods as well as a variety of free or commercial software libraries are widely available nowadays. However, when one of these methods is applied to a real-world task, there can be many pitfalls and booby traps lurking - certain aspects of the optimization problem that may lead to unsatisfactory results even if the algorithm appears to be correctly implemented and executed. These include the convergence issues, ruggedness, deceptiveness, and neutrality in the fitness landscape, epistasis, non-separability, noise leading to the need for robustness, as well as dimensionality and scalability issues, among others. In this article, we systematically discuss these related hindrances and present some possible remedies. The goal is to equip practitioners and researchers alike with a clear picture and understanding of what kind of problems can render EC applications unsuccessful and how to avoid them from the start.     

HBBA: hybrid algorithm for buffer allocation in tandem production lines

In this paper, we consider the problem of buffer space allocation for a tandem production line with unreliable machines. This problem has various formulations all aiming to answer the question: how much buffer storage to allocate between the processing stations? Many authors use the knapsack-type formulation of this problem. We investigate the problem with a broader statement. The criterion depends on the average steady-state production rate of the line and the buffer equipment acquisition cost. We evaluate black-box complexity of this problem and propose a hybrid optimization algorithm (HBBA), combining the genetic and branch-and-bound approaches. HBBA is excellent in computational time. HBBA uses a Markov model aggregation technique for goal function evaluation. Nevertheless, HBBA is more general and can be used with other production rate evaluation techniques.     

An artificial neural network based decision support system for solving the buffer allocation problem in reliable production lines

One of the major design problems in the context of manufacturing systems is the well-known Buffer Allocation Problem (BAP). This problem arises from the cost involved in terms of space requirements on the production floor and the need to keep in mind the decoupling impact of buffers in increasing the throughput of the line. Production line designers often need to solve the Buffer Allocation Problem (BAP), but this can be difficult, especially for large production lines, because the task is currently highly time consuming. Designers would be interested in a tool that would rapidly provide the solution to the BAP, even if only a near optimal solution is found, especially when they have to make their decisions at an operational level (e.g. hours). For decisions at a strategic level (e.g. years), such a tool would provide preliminary results that would be useful, before attempting to find the optimal solution with a specific search algorithm.     

遗传算法的工程应用

分析了排课问题的各种约束条件,并研究了用遗传算法解决排课问题,给出了一个基于该算法的排课模型,并对涉及的各种问题进行探讨。     

民航旅客个体和社交偏好建模及航班座位分配优化

在民航领域,提升旅客满意度的关键之一是了解旅客的个性化需求并提供定制化的旅行服务,尤其是在航班座位分配上。然而,实现这一目标面临两个主要挑战:如何准确建模旅客的偏好以及如何合理分配座位。传统方法往往要求对旅客的真实偏好有明确了解,但当前的收费座位选择和先到先得的策略难以全面满足旅客需求。为了解决这一问题,需要考虑座位的可用性、空间相关性以及旅客之间的社交关系。文中提出了一种新的解决方案,通过从个体和社交两个维度建模旅客偏好,并将座位分配视为一个组合优化问题,以尽可能满足旅客的个体和社交偏好,同时遵循业务规则和旅客价值。该方案利用迭代局部搜索算法来优化座位分配。实验结果表明,该方法能够有效建模旅客的座位偏好,并显著提升航班的整体满意度。     

Using a greedy random adaptative search procedure to solve the cover printing problem

In this paper, the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost, is discussed. As the considered problem is hard, we discuss and propose a greedy random adaptative search procedure (GRASP) to solve the problem. The quality of the proposed procedure is tested on a set of reference instances, comparing the obtained results with those found in the literature. Our procedure improves the best known solutions for some of these instances. Results are also presented for larger, randomly generated problems.     

一种规模化混杂生产线缓冲区容量优化分配技术

针对传统技术难以解决规模化混杂生产线缓冲区容量分配问题(Buffer allocation problem, BAP), 提出了一种规模化生产线递阶分解建模并行寻优技术(Hierarchical decomposition modeling parallel optimizing technique of large-scale production lines, HDMPOT). 该技术结合混杂生产线系统综合方法与分解方法的技术思想, 兼顾生产线平衡性与系统规模, 将原系统递阶分解为包含虚拟生产线在内的n + 1个子生产线系统, 通过求解子系统的最优解构造原系统的渐近最优解, 并在系统递阶建模阶段, 提出了一种设备模糊聚类的辅助方式; 同时, 基于混杂生产线系统综合方法, 提出了一种系统渐次综合的初解改进确定方法; 并提出了一种通过构造动态步长来设计领域结构的改进型禁忌搜索算法(Simple tabu search, STS), 对子系统进行并行寻优. 最后, 对技术算法的收敛性进行了证明. 提出的生产线递阶分解建模并行寻优技术具有一般性, 对受设备随机故障等随机事件影响的生产线, 尤其是规模化生产线系统其他优化、控制问题也具有借鉴和参考价值.     

Two hybrid differential evolution algorithms for optimal inbound and outbound truck sequencing in cross docking operations

This paper studies inbound and outbound truck sequencing for cross docking operations with the objective to minimize total operation time (a.k.a. makespan) or equivalently to maximize the throughput of a cross docking system. Specifically, two major contributions are made: (i) designing two new hybrid differential evolution algorithms with better performance than the pure differential evolution algorithm that was reported to have the best performance in a recent comparative study of several metaheuristic algorithms, i.e., Arabani et al., and (ii) proposing a more realistic and efficient operational policy that leads to shorter makespan than that developed by Yu and Egbelu. The effectiveness of the proposed algorithms and policy are shown based on the results of testing 30 problems and several other related issues are also investigated and discussed.     

New heuristics for packing unequal circles into a circular container

We propose two new heuristics to pack unequal circles into a two-dimensional circular container. The first one, denoted by A1.0, is a basic heuristic which selects the next circle to place according to the maximal hole degree rule. The second one, denoted by A1.5, uses a self look-ahead strategy to improve A1.0. We evaluate A1.0 and A1.5 on a series of instances up to 100 circles from the literature and compare them with existing approaches. We also study the behaviour of our approach for packing equal circles comparing with a specified approach in the literature. Experimental results show that our approach has a good performance in terms of solution quality and computational time for packing unequal circles.     

Variable neighborhood search for the linear ordering problem

Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is coupled with a short-term tabu search for improved outcomes. Our extensive experimentation with both real and random instances shows that the proposed procedure competes with the best-known algorithms in terms of solution quality, and has reasonable computing-time requirements.Variable neighborhood search (VNS) is a metaheuristic method that has recently been shown to yield promising outcomes for solving combinatorial optimization problems. Based on a systematic change of neighborhood in a local search procedure, VNS uses both deterministic and random strategies in search for the global optimum.In this paper, we present a VNS implementation designed to find high quality solutions for the NP-hard LOP, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input–output tables in economics. Our implementation incorporates innovative mechanisms to include memory structures within the VNS methodology. Moreover we study the hybridization with other methodologies such as tabu search.     

柔性车间生产排产调度优化方法

为满足柔性制造企业在车间生产中合理安排生产排产调度的需要,提出柔性车间生产排产调度优化方法。首先,通过分析车间生产排产问题的特点,制定满足车间应用需求和各种资源限制的生产排产总体流程,从而设计基于约束条件的生产对象关系模型;其次,提出一种动态策略差分进化算法,根据个体之间的拥挤度动态选择变异策略,设计基于工序位置的编解码方案,其能快速有效地进行求解,从而得到最佳调度方案,提高设备运行效率,实现资源利用的最大化;最后,通过6个标准测试函数、FT6-6测试问题及生产调度应用实例验证了算法的有效性。     

基于格局变换策略的不等圆Packing问题求解算法*

采用基于格局变换策略的算法ACP-Solver求解不等圆Packing问题。ACP-Solver由连续优化方法、格局变换算子和接收准则组成。连续优化方法可从任一初始格局收敛至对应的局部最优格局。格局变换算子将当前格局变换为新格局。接收准则决定是否接收变换所得格局。基于24个国际公开算例的计算实验表明,ACP-Solver能在可接受的计算时间内改进或持平绝大多数算例的当前最优记录。实验结果表明了ACP-Solver的高效性能。     

混合蚁群算法求解分布式系统任务分配问题

任务分配问题是被公认的NP-hard问题,应用广泛。在对分布式系统任务分配问题进行分析的基础上,将蚂蚁寻求任务分配方案的过程用一种新的图形表示方式来实现。针对蚁群优化算法易陷入局部最优的固有缺陷,提出了一种新的混合算法,该算法将蚁群优化算法与简单禁忌搜索算法相结合,增强了算法的局部搜索能力,提高了任务分配问题解的质量。实验结果表明混合算法的求解性能较优。     

Efficient Algorithm for the Constrained Two-dimensional Cutting Stock Problem

This paper considers the constrained two-dimensional cutting stock problem. Some properties of the problem are derived leading to the development of a new algorithm, which uses a very efficient branching strategy for the solution of this problem. This strategy enables the early rejection of partial solutions that cannot lead to optimality. Computational results are given and compared with those produced by a leading alternative method. These results show that the new algorithm is far superior in terms of the computer time needed to solve such problems.