基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

Clustering and combinatorial optimization in recursive supervised learning

The use of combinations of weak learners to learn a dataset has been shown to be better than the use of a single strong learner. In fact, the idea is so successful that boosting, an algorithm combining several weak learners for supervised learning, has been considered to be the best off the shelf classifier. However, some problems still exist, including determining the optimal number of weak learners and the over fitting of data. In an earlier work, we developed the RPHP algorithm which solves both these problems by using a combination of global search, weak learning and pattern distribution. In this chapter, we revise the global search component by replacing it with a cluster based combinatorial optimization. Patterns are clustered according to the output space of the problem, i.e., natural clusters are formed based on patterns belonging to each class. A combinatorial optimization problem is therefore created, which is solved using evolutionary algorithms. The evolutionary algorithms identify the “easy” and the “difficult” clusters in the system. The removal of the easy patterns then gives way to the focused learning of the more complicated patterns. The problem therefore becomes recursively simpler. Over fitting is overcome by using a set of validation patterns along with a pattern distributor. An algorithm is also proposed to use the pattern distributor to determine the optimal number of recursions and hence the optimal number of weak learners for the problem. Empirical studies show generally good performance when compared to other state of the art methods.     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

A multi-objective particle swarm for a flow shop scheduling problem

Flow shop problems as a typical manufacturing challenge have gained wide attention in academic fields. In this paper, we consider a bi-criteria permutation flow shop scheduling problem, where weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a flow shop scheduling problem has been proved to be NP-hard in strong sense, an effective multi-objective particle swarm (MOPS), exploiting a new concept of the Ideal Point and a new approach to specify the superior particle's position vector in the swarm, is designed and used for finding locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm, i.e. SPEA-II. The computational results show that the proposed MOPS performs better than the genetic algorithm, especially for the large-sized problems.     

An efficient tabu search algorithm for the single- machine mean tardiness problem

In this paper, an efficient tabu search algorithm is prepared for solving the single-machine mean tardiness problem. The proposed implementation of the tabu search approach suggests simple techniques for generating neighbourhoods of a given sequence and a combined scheme for intensification and diversification. The tabu search method is shown to produce results very close to the optimal solution using randomly generated problems with varying degrees of difficulty.     

基于随机p-鲁棒优化的国家血液战略储备库选址-库存模型

以往的救灾实践对建立国家血液战略储备体系提出了迫切要求。国家血液战略储备库的建设问题亟待解决。由于血液产品特性以及应急血液保障特性的存在,使得国家血液战略储备库的选址决策具有一定的复杂性。本文将问题定位为选址-库存问题。首先,以应急条件下血液保障及时度最高为目标,构建了一个不确定环境下考虑多情景、多血型、多阶段、带提前期、有容量限制、日常随机需求、有预算约束及协同定位的国家血液战略储备库选址-库存模型。同时,为了规避应急条件下的不确定风险,进一步构建了国家血液战略储备库选址-库存问题的随机p-鲁棒优化模型。该模型为离散非线性混合整数规划模型,难以快速精确求解。故基于模型性质,设计了相应的遗传算法。最后,设计了两组算例验证模型与算法的有效性。其中,第1组算例基于我国大陆地区31个省级血液中心与省级行政区的数据,并根据不同预算值给出6个算例,得到了国家血液战略储备库的选址-库存决策方案。第2组算例为6个不同规模的模拟算例,用来测试不同规模下的算法性能。算例结果表明：遗传算法的性能更好;鲁棒解与确定性模型最优值相差不大（最大差距≤1.08%）,可降低不确定性导致的风险。实践中,可对本文所建模型稍作改进,应用于具有类似特征的易腐品（药品、粮食等）应急物资储备库选址-库存决策。     

Modified differential evolution with self-adaptive parameters method

The differential evolution algorithm (DE) is a simple and effective global optimization algorithm. It has been successfully applied to solve a wide range of real-world optimization problem. In this paper, the proposed algorithm uses two mutation rules based on the rand and best individuals among the entire population. In order to balance the exploitation and exploration of the algorithm, two new rules are combined through a probability rule. Then, self-adaptive parameter setting is introduced as uniformly random numbers to enhance the diversity of the population based on the relative success number of the proposed two new parameters in a previous period. In other aspects, our algorithm has a very simple structure and thus it is easy to implement. To verify the performance of MDE, 16 benchmark functions chosen from literature are employed. The results show that the proposed MDE algorithm clearly outperforms the standard differential evolution algorithm with six different parameter settings. Compared with some evolution algorithms (ODE, OXDE, SaDE, JADE, jDE, CoDE, CLPSO, CMA-ES, GL-25, AFEP, MSAEP and ENAEP) from literature, experimental results indicate that the proposed algorithm performs better than, or at least comparable to state-of-the-art approaches from literature when considering the quality of the solution obtained.     

基于求解TSP问题的双向扩展差额算法

旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.     

有限缓冲区的多节点订单接受模型与算法

订单接受问题广泛存在于生产管理中,而现有多节点订单接受问题中大多不考虑缓冲区约束对订单接受的影响。针对这一问题,以缓冲区约束的多节点生产为背景,建立了订单接受模型。利用改进NEH算法、离散和声搜索算法和变邻域搜索的混合算法对模型进行求解。实验结果显示,当问题规模较小时,算法取得较好的计算效果。问题规模较大时,求解效果一般。缓冲区的大小对订单完工时间影响较小,与无限缓冲区的计算结果相似。混合算法具有较好的求解速度,能够有效求解问题模型。     

A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation

The hybrid flowshop scheduling (HFS) problem with the objective of minimising the makespan has important applications in a variety of industrial systems. This paper presents an effective discrete artificial bee colony (DABC) algorithm that has a hybrid representation and a combination of forward decoding and backward decoding methods for solving the problem. Based on the dispatching rules, the well-known NEH heuristic, and the two decoding methods, we first provide a total of 24 heuristics. Next, an initial population is generated with a high level of quality and diversity based on the presented heuristics. A new control parameter is introduced to conduct the search of employed bees and onlooker bees with the intention of balancing the global exploration and local exploitation, and an enhanced strategy is proposed for the scout bee phase to prevent the algorithm from searching in poor regions of the solution space. A problem-specific local refinement procedure is developed to search for solution space that is unexplored by the honey bees. Afterward, the parameters and operators of the proposed DABC are calibrated by means of a design of experiments approach. Finally, a comparative evaluation is conducted, with the best performing algorithms presented for the HFS problem under consideration, and with adaptations of some state-of-the-art metaheuristics that were originally designed for other HFS problems. The results show that the proposed DABC performs much better than the other algorithms in solving the HFS problem with the makespan criterion.     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

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.     

A sustainable supply chain network considering lot sizing with quantity discounts under disruption risks: centralized and decentralized models

This study proposes a framework for the main parties of a sustainable supply chain network considering lot-sizing impact with quantity discounts under disruption risk among the first studies. The proposed problem differs from most studies considering supplier selection and order allocation in this area. First, regarding the concept of the triple bottom line, total cost, environmental emissions, and job opportunities are considered to cover the criteria of sustainability. Second, the application of this supply chain network is transformer production. Third, applying an economic order quantity model lets our model have a smart inventory plan to control the uncertainties. Most significantly, we present both centralized and decentralized optimization models to cope with the considered problem. The proposed centralized model focuses on pricing and inventory decisions of a supply chain network with a focus on supplier selection and order allocation parts. This model is formulated by a scenario-based stochastic mixed-integer non-linear programming approach. Our second model focuses on the competition of suppliers based on the price of products with regard to sustainability. In this regard, a Stackelberg game model is developed. Based on this comparison, we can see that the sum of the costs for both levels is lower than the cost without the bi-level approach. However, the computational time for the bi-level approach is more than for the centralized model. This means that the proposed optimization model can better solve our problem to achieve a better solution than the centralized optimization model. However, obtaining this better answer also requires more processing time. To address both optimization models, a hybrid bio-inspired metaheuristic as the hybrid of imperialist competitive algorithm (ICA) and particle swarm optimization (PSO) is utilized. The proposed algorithm is compared with its individuals. All employed optimizers have been tuned by the Taguchi method and validated by an exact solver in small sizes. Numerical results show that striking similarities are observed between the results of the algorithms, but the standard deviations of PSO and ICA–PSO show better behavior. Furthermore, while PSO consumes less time among the metaheuristics, the proposed hybrid metaheuristic named ICA–PSO shows more time computations in all small instances. Finally, the provided results confirm the efficiency and the performance of the proposed framework and the proposed hybrid metaheuristic algorithm.

     

Exact and heuristic algorithms for the circle cutting problem in the manufacturing industry of electric motors

Circular blanks are often cut from silicon steel plates to make stators and rotors of electric motors. The shearing and punching processes are often used to cut the blanks. First a guillotine shear cuts the plate into strips, and then a stamping press cuts the blanks from the strips. The unconstrained circle cutting problem discussed is the problem of cutting from a rectangular plate a number of circular blanks of given diameters and values, so as to maximize the value of blanks cut, where the shearing and punching processes are applied. Two algorithms based on dynamic programming are presented for generating cutting patterns, one is an exact algorithm and the other is a heuristic one. The computational results indicate that the exact algorithm is adequate for small and middle scale problems, the heuristic algorithm is much more time efficient, and can generate cutting patterns close to optimal.     

Pareto mimic algorithm: An approach to the team orienteering problem

The team orienteering problem is an important variant of the vehicle routing problem. In this paper, a new algorithm, called Pareto mimic algorithm, is proposed to deal with it. This algorithm maintains a population of incumbent solutions which are updated using Pareto dominance. It uses a new operator, called mimic operator, to generate a new solution by imitating an incumbent solution. Furthermore, to improve the quality of a solution, it employs an operator, called swallow operator which attempts to swallow (or insert) an infeasible node and then repair the resulting infeasible solution. A comparative study supports the effectiveness of the proposed algorithm, especially, our algorithm can quickly find new better results for several large-scale instances. We also demonstrate that Pareto mimic algorithm can be generalized to solve other routing problems, e.g., the capacitated vehicle routing problem.     

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.     

基于复杂网络和语言信息的交互式大规模群体评价方法

针对现有基于语言信息的交互式群体评价方法大多仅适用于中小规模群体的情况,提出一种新的基于复杂网络和语言信息的交互式大规模群体评价方法。首先,将评价者视为网络节点,并依据节点之间的距离构建复杂网络;其次,设计节点紧密度和子群紧密度,并确定节点权重和子群权重;再次,定义群体稳定性指标和群体满意度指标,并以此来判断交互终止和确定阶段权重;最后,在节点密度算子和节点加权算子的基础上,分别对单轮群体意见和多轮评价结果进行集结。文末通过一个实际例子验证了所提方法的有效性与合理性。实例分析表明,该方法能够较为全面、准确地集结交互式大规模群体评价意见,且其结果的满意度亦较为理想。     

Multimode time-cost-robustness trade-off project scheduling problem under uncertainty

The time/cost trade-off problem is a well-known project scheduling problem that has been extensively studied. In recent years, many researchers have begun to focus on project scheduling problems under uncertainty to cope with uncertain factors, such as resource idleness, high inventory, and missing deadlines. To reduce the disturbance from uncertain factors, the aim of robust scheduling is to generate schedules with time buffers or resource buffers, which are capped by project makespan and project cost. This paper addresses a time-cost-robustness trade-off project scheduling problem with multiple activity execution modes under uncertainty. A multiobjective optimization model with three objectives (makespan minimization, cost minimization, and robustness maximization) is constructed and three propositions are proposed. An epsilon-constraint method-based genetic algorithm along with three improvement measures is designed to solve this NP-hard problem and to develop Pareto schedule sets, and a large-scale computational experiment on a randomly generated dataset is performed to validate the effectiveness of the proposed algorithm and the improvement measures. The final sensitivity analysis of three key parameters shows their distinctive influences on the three objectives, according to which several suggestions are given to project managers on the effective measures to improve the three objectives.

     

多车场带时间窗车辆路径问题的变邻域搜索算法

多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。     

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.