A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness

This study considers the problem of scheduling independent jobs on unrelated parallel machines with machine- and sequence-dependent setup times for the objective of minimizing the total tardiness, i.e., R _m │S _ijk │∑T _j . Since the parallel machines are unrelated, sequence-dependent setup times must depend on machines. To the best of the authors’ knowledge, the simulated annealing and the iterated greedy algorithms are two existing ones for the new class of scheduling problem with an additional constraint of strict due date constraints for some jobs, i.e., deadlines. In this study, we suggest a tabu search algorithm that incorporates various neighborhood generation methods. A computational experiment was done on the instances generated by the method used in the two previous research articles, and the results show that the tabu search algorithm outperforms the simulated annealing algorithm significantly. In particular, it gave optimal solutions for more than 50 % of small-sized test instances. Also, an additional test was done to compare the performances of the tabu search and the existing iterated greedy algorithms, and the result shows that the tabu search algorithm gives quicker solutions than the iterated greedy algorithm although it gives less quality solutions.     

[供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法

为了同时实现总配送成本最低、车辆行驶距离最短、车辆数最小等目标,综合考虑车辆指派成本及运输路径成本,建立了装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种自适应并行遗传算法。算法以C-W节约法为基础,设计了三种基于双重需求的启发式种群初始化方法,缩小搜索空间并优化初始解;引入多样性种群和高质量种群的双种群并行策略,实现深度与广度的同步搜索;设计自适应交叉变异操作,改善高质量种群个体搜索停滞,并针对全局最优个体采用特殊变异的后优化操作以进一步提高全局优化性能。采用标准数据集作为算例进行寻优测试,验证了所提算法的可行性和有效性。     

A two-criteria objective function flexible flowshop scheduling problem with machine eligibility constraint

This research deals with a flexible flowshop scheduling problem with the arrival and delivery of jobs in groups and processing them individually. Each group of jobs has a specific release time. Due to the special characteristics of each job, only a specific group of machines in each stage are eligible to process that job. All jobs in a group should be delivered at the same time after processing. The objectives of the problem are the minimization of the sum of the completion time of groups on one hand and the minimization of sum of the differences between the completion time of jobs and the delivery time of the group containing that job (waiting period) on the other hand. The problem can be stated as FF_c /r _j , M _j /irreg based on existing scheduling notations. This problem has many applications in the production and service industries such as ceramic tile manufacturing companies and restaurants. A mathematical model has been proposed to solve the problem. Since the research problem is shown to be NP-complete, a particle swarm optimization (PSO) algorithm is applied to solve the problem approximately. Based on the frequency of using local search procedure, four scenarios of PSO have been developed. The algorithms are compared by applying experimental design techniques on random test problems with different sizes. The results show that the PSO algorithm enhanced with local search for all particles has a weaker performance than the other scenarios in solving large-sized problems.     

Knowledge-based substep deterministic optimization of large diameter thin-walled Al-alloy tube bending

Regarding increasing applications with mass quantities, diverse specifications, and close quality tolerance, the precision bending of large diameter thin-walled (LDTW) Al-alloy tube should be efficiently achieved. However, bending of LDTW Al-alloy tube is a highly tri-nonlinear process with possible multi-defect, needing strict coordination of various bending tools and processing parameters. Considering the coupling effects of various forming parameters on multiple defects, this study developed a knowledge-based substep methodology to solve the deterministic optimization of LDTW Al-alloy tube bending with multi-objective and multi-variable under multiple factor constraints. Considering narrow forming window under small bending radii (R _b?<?2D, R _b—bending radius, D—initial tube diameter), a finite element (FE)-based stepwise iterative search method is proposed to optimize key forming parameters of LDTW Al-alloy tube under small R _b, and the search direction is based on bending knowledge. While for large R _b bending with wide optional ranges of forming parameters, a hybrid optimization approach is used by combining virtual design of experiment, FE simulation, approximate response surface model, sequential quadratic programming algorithm, or genetic algorithm. Using orthogonal experimental method, three-dimensional (3D)-FE simulation, experiential data, and analytical formulae, knowledge on key forming parameters, coupling effects on multiple defects, effect significance, and design rules are obtained as well as initial values and design ranges. By several practical bending scenarios with D up to 100 mm, the proposed substep deterministic optimization methodology for LDTW Al-alloy tube bending is evaluated.     

新型混合改进遗传算法求解零等待流水车间调度问题

具有零等待约束条件的流水车间调度问题是一类典型的NP难问题,针对该问题提出一种新型混合改进遗传算法进行优化求解.首先,采用改进NEH算法强化初始种群质量,提高种群的多样性.结合关联规则理论挖掘种群中的优势块,借助优势块进行人工染色体组合,以降低问题复杂度.交叉操作采用单段交叉、双段交叉和三段交叉3种交叉机制,改善算法全...     

An optimization strategy for die design in the low-density polyethylene annular extrusion process based on FES/BPNN/NSGA-II

An optimization strategy for die design in the polymer extrusion process is proposed in the study based on the finite element simulation, the back-propagation neural network, and the non-dominated sorting genetic algorithm II (NSGA-II). The three-dimensional simulation of polymer melts flow in the extrusion process is conducted using the penalty finite element method. The model for predicting the flow patterns in the extrusion process is established with the artificial neural network based on the simulated results. The non-dominated sorting genetic algorithm II is performed for the search of globally optimal design variables with its objective functions evaluated by the established neural network model. The proposed optimization strategy is successfully applied to the die design in low-density polyethylene (LDPE) annular extrusion process. A constrained multi-objective optimization model is established according to the characteristics of annular extrusion process. The minimum of velocity relative difference, δu, and the minimum of swell ratio, S _w, that, respectively, ensure the extrinsic feature, mechanical property, and dimensional precision of the final products are taken as optimization objectives with a constrained condition on the maximum shear stress. Three important die structure parameters, including the die contraction angle α, the ratio of parallel length to inner radius L/R _i, and the ratio of outer to inner radius R _o /R _i, are taken as design variables. The Phan-Thien–Tanner constitutive model is adopted to describe the viscoelastic rheological characteristics of LDPE whose parameters are fitted by the distributions of material functions detected on the strain-controlled rheometer. The penalty finite element model of polymer melts flowing through out of the extrusion die is derived. A decoupled method is employed to solve the viscoelastic flow problem with the discrete elastic-viscous split-stress algorithm. The simulated results are selected and extracted to constitute the learning samples according to the orthogonal experimental design method. The back propagation algorithm is adopted for the training and the establishment of the predicting model for the optimization objective. A Pareto-optimal set for the constrained multi-objective optimization is obtained using the constrained NSGA-II, and the optimal solution is extracted based on the fuzzy set theory. The optimization for die parameters in the annular extrusion process of low-density polyethylene is performed and the optimization objective is successfully achieved.     

Solving a new mathematical model for a hybrid flow shop scheduling problem with a processor assignment by a genetic algorithm

This paper presents a new mathematical model for a hybrid flow shop scheduling problem with a processor assignment that minimizes makespan (i.e., C _max) and cost of assigning a number of processors to stages. In this problem, it is assumed that there are a number of parallel identical processors which are assigned to all of the stages with an unlimited intermediate storage between any two successive stages. To solve such a hard problem, first a new heuristic algorithm is proposed to compute the makespan that is embedded in the proposed genetic algorithm in order to find the best sequence of jobs, and then processors are assigned to the stages simultaneously. A number of test problems have been solved and related results are illustrated and analyzed.     

Performance evaluation of the scatter search method for permutation flowshop sequencing problems

Many optimization problems from the industrial engineering world, in particular manufacturing systems, are very complex in nature and are quite hard to solve by conventional optimization techniques. There has been increasing interest to apply metaheuristic methods to solve such kinds of hard optimization problems. In this work, a novel metaheuristic approach called scatter search (SS) is applied for the n/m/P/C _max problem, an NP-hard sequencing problem, which is used to find a processing order of n different jobs to be processed on m machines in the same sequence with minimizing the makespan. SS contrasts with other evolutionary procedures by providing a wide exploration of the search space through intensification and diversification. In addition, it has a unifying principle for joining solutions and they exploit the adaptive memory principle to avoid generating or incorporating duplicate solutions at various stages of the problem. In this paper, various metaheuristic methods and best heuristics from the literature are used for solving the well-known benchmark problem set of Taillard (Eur J Oper Res 64:278–285, 1993). The results available for the various existing metaheuristic and heuristic methods are compared with the results obtained by the SS method. The proposed framework achieves better results for 4 of 12 benchmark problems and also achieves an average deviation of 1.003% from the benchmark problem set of Taillard (Eur J Oper Res 64:278–285, 1993). The computational results show that SS is a more effective metaheuristic for the n/m/P/C _max problem.     

Optimal design of four-bar mechanisms using a hybrid multi-objective GA with adaptive local search

Responding to an increasing demand for mechanism synthesis tools that are both efficient and accurate, this paper presents a novel approach to the multi-objective optimal design of four-bar linkages for path-generation purposes. Three, often conflicting criteria including the mechanism's tracking error, deviation of its transmission angle from 90° and its maximum angular velocity ratio are considered as objectives of the optimization problem. To accelerate the search in the highly multimodal solution space, a hybrid Pareto genetic algorithm with a built-in adaptive local search is employed which extends its exploration to an adaptively adjusted neighborhood of promising points. The efficiency of the proposed algorithm is demonstrated by applying it to a classical design problem for one, two and three objective functions and comparing the results with those reported in the literature. The comparison shows that the proposed algorithm distinctly outperforms other algorithms both quantitatively and qualitatively (from a practical point of view).     

Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms

The concept of parallel machines has been widely used in manufacturing. This article proposes a genetic algorithm (GA) approach to minimize total tardiness of a set of tasks for identical parallel machines and worker assignment to machines. A spreadsheet-based GA approach is presented to solve the problem. A domain-independent general purpose GA is used, which is an add-in to the spreadsheet software. The paper demonstrates an adaptation of the proprietary GA software to the problem of minimizing total tardiness for the worker assignment scheduling problem for identical parallel machine models. Two 100 I/P/n/m/W problems taken from Hu (Int J Adv Manuf Technol 23:383–388, 2004, Int J Adv Manuf Technol 29:165–169, 2006) for a similar study are simulated. The performance of GA is superior to SES-A/LMC approach used by Hu and very close to the Exhaustive search procedure. It is shown that the spreadsheet GA implementation makes it very easy to adapt the problem for any set of objective measures without changing the actual model. Empirical analysis has been carried out to study the effect of GA parameters, namely, crossover rate, mutation rate, and the population size.     

Prediction of contraction scour using ANN and GA

This paper emphasizes on the application of soft computing tools such as artificial neural network (ANN) and genetic algorithm (GA) in the prediction of scour depth within channel contractions. The experimental data of earlier investigators are used in developing the models and ANN and GA Toolboxes of MATLAB software are utilized for the purpose. The multilayered perceptron (MLP) neural networks with feed-forward back-propagation training algorithms were designed to predict the scour depth. The mean squared error and correlation coefficient are used to check the performance of networks. It is found that the ANN architecture 4-16-1 having trained with Levenberg-Marquardt ‘trainlm’ function had best performance having mean squared error of 0.001 and correlation coefficient of 0.998. In addition, the suitability of ‘trainlm’ method over other training methods is also discussed. The scour depths predicted by ANN model were compared with those computed by the two analytical models (with and without sidewall correction for contracted zone) and an empirical model proposed by Dey and Raikar [1]. In addition, heuristic search technique called genetic algorithm is used to develop the predictor for maximum scour depth within channel contraction. The population size for GA was 500 members with total generations of 1000, crossover fraction of 0.8 and Gaussian operator for mutation. It is promising to observe that the GA model predicts the maximum scour depth equally well as that of empirical model of Dey and Raikar [1]. Hence, both ANN and GA models can be satisfactorily used to predict the scour depth within channel contractions.     

Genetic ordinal optimisation for stochastic flow shop scheduling

Stochastic flow shop scheduling is a typical and widely studied NP-hard stochastic optimisation problem with strong industrial roots. However, due to inaccurate estimation of objective values, NP-hardness and a limited computing budget, it is generally hard to solve such stochastic optimisation problems effectively and efficiently. Based on the idea of order comparison and goal softening, ordinal optimisation (OO) has been widely applied for stochastic optimisation. In this paper, OO and optimal computing budget allocation (OCBA) as well as a genetic algorithm (GA) are reasonably hybridised to propose an effective genetic ordinal optimisation (GOO) approach for flow shop scheduling with stochastic processing times. In GOO, limited computing effort can be intelligently allocated by OCBA to provide reliable and robust evaluation and identification of good solutions in a population, and the solution space can be well explored by an order-based evolutionary genetic search with the good solutions identified by OCBA. Simulation results based on benchmarks demonstrate the effectiveness of the GOO by comparison with traditional methods. Moreover, the effects of some parameters on the optimisation performance are discussed.     

遗传算法中适应度函数的改进术

遗传算法引导搜索的主要依据就是个体的适应度值,因此适应度函数的设计显得尤为重要。本文兼顾保持种群的多样性和算法的收敛性,提出了一种基于指数变换的、指数系数可随进化代数动态调整的非线性适应度函数。以两个典型的测试函数为例,在相同的遗传操作和参数下,分别采用本文提出的适应度函数、线性拉伸变换及一般的指数变换适应度函数进行优化计算,计算结果表明采用提出的新适应度函数能极大地提高算法的优化精度、收敛速度和收敛概率。     

基于免疫遗传算法的不规则件排样优化问题求解

基于遗传算法难以保持群体的多样性及存在易早熟、效率低的缺陷,提出免疫遗传算法应用于不规则零件排样的优化方法。该算法在遗传算法的全局随机搜索基础上,借鉴了人工免疫系统中的免疫记忆和浓度机制。通过疫苗接种实现种群个体中基因位的局部调整优化,并将其优良个体保存于免疫记忆库中,提高了算法的搜索速度。同时浓度机制保证了遗传交叉和变异过程中生成下代种群个体的多样性,扩大了搜索空间,更利于最优解的获取。该方法在开发的不规则件排样系统中进行了实算求解,通过与标准遗传算法的实验结果比对,板材的利用效率得到显著提高。     

一种基于改进遗传算法的神经网络优化算法研究

遗传算法是目前优化搜索算法中应用比较广泛的一种,但基本遗传算法存在收敛速度慢、易于陷入局部最优等缺点。针对上述问题对遗传算法(GA)的选择算子进行改进,在最优保存策略的基础上将每代种群按照适应度由小到大排序,平均分成前中后3段,按照0.6、0.8、1的比例进行选择;从尾段中随机抽取个体来补足种群由于选择操作而损失的个体;既利用了最优保存策略的全局收敛特性同时也保持了种群的多样性;用改进的遗传算法调整神经网络的权值形成了新的改进遗传算法优化BP神经网络(IGA-BP);通过与选择算子为适应度比例选择算子的GA-BP网络进行比较,结果表明算法改进后缩短了收敛时间同时减少了运行误差;最后将该改进算法应用于水泥回转窑的故障诊断中,验证了算法的可行性。     

A novel optimal support vector machine ensemble model for NOX emissions prediction of a diesel engine

A novel ensemble method based on principal component analysis (PCA), genetic algorithm (GA) and support vector machine (SVM) implemented in MATLAB® is presented for establishing the NO_X emissions prediction model for a diesel engine for both steady and transient operating states. The different stages of data preprocessing, modeling, optimization and prediction were discussed in detail. Normalization and PCA were used to reduce differences and redundancy of the datasets respectively. Subsequently, the SVM model was trained with 1/3 of the equi-spaced data samples (a simple DoE) selected after preprocessing. A grid search and GA were then applied as the combination strategy with the fitness function being the cross-validated root mean square error (RMSE) for optimizing the model parameters to improve the prediction accuracy. The optimal model was finally tested using the rest 2/3 data samples. Compared with other three methods, the proposed model exhibited superior accuracy both on training and testing datasets.     

Soft computing models and intelligent optimization system in electro-discharge machining of SiC/Al composites

In this paper, a multi-variable regression model, a back propagation neural network (BPNN) and a radial basis neural network (RBNN) have been utilized to correlate the cutting parameters and the performance while electro-discharge machining (EDM) of SiC/Al composites. The four cutting parameters are peak current (I_p), pulse-on time (T_on), pulse-off time (T_off), and servo voltage (S_v); the performance measures are material remove rate (MRR) and surface roughness (Ra). By testing a large number of BPNN architectures, 4-5-1 and 4-7-1 have been found to be the optimal one for MRR and Ra, respectively; and it can predict them with 10.61 % overall mean prediction error. As for RBNN architectures, it can predict them with 12.77 % overall mean prediction error. The multivariable regression model yields an overall mean prediction error of 13.93 %. All of these three models have been used to study the effect of input parameters on the material remove rate and surface roughness, and finally to optimize them with genetic algorithm (GA) and desirability function. Then, an intelligent optimization system with graphical user interface (GUI) has been built based on these multi-optimization techniques, in which users can obtain the optimized cutting parameters under the desired surface roughness (Ra).     

Makespan minimization of a flowshop sequence-dependent group scheduling problem

The flowshop sequence dependent group scheduling problem with minimization of makespan as the objective (F _m |fmls, S _plk, prmu|C _max ) is considered in this paper. It is assumed that several groups with different number of jobs are assigned to a flow shop cell that has m machines. The goal is to find the best sequence of processing the jobs in each group and the groups themselves with minimization of makespan as the objective. A mathematical model for the research problem is developed in this paper. As the research problem is shown to be NP-hard, a hybrid ant colony optimization (HACO) algorithm is developed to solve the problem. A lower bounding technique based on relaxing a few constraints of the mathematical model developed for the original problem is proposed to evaluate the quality of the HACO algorithm. Three different problem structures, with two, three, and six machines, are used in the generation of the test problems to test the performance of the algorithm and the lower bounding technique developed. The results obtained from the HACO algorithm and those that have appeared in the published literature are also compared. The comparative results show that the HACO algorithm has a superior performance compared to the best available algorithm based on memetic algorithm with an average percentage deviation of around 1.0% from the lower bound.     

一类解决车间调度问题的遗传退火算法

将遗传算法与模拟退火算法相结合,提出了一种混合调度算法。该算法采用3种提高效率的策略:(1)采用基于机器的分段编码方式,使编码简单直观,并且编码空间小。(2)采用4-2选择代替常用的转轮选择方式,既保留了优秀个体又维持了群体多样性;(3)采用基于关键路径的邻域产生函数和变异算子,缩小了搜索邻域。实验表明该算法具有较高的求解质量和效率。     

Integrating production and transportation scheduling in a two-stage supply chain considering order assignment

This study is concerned with the integration of production and transportation scheduling in a two-stage supply chain environment while considering the assignment of orders to the suppliers. The first stage contains m suppliers distributed in various geographic zones, and the second stage is composed of l vehicles with different speeds and transportation capacities that transport n jobs from the supplier to a manufacturing company. In addition, it is assumed that each job occupies a different vehicle size and could be processed by some permissible suppliers. After modeling the problem as a mixed integer programming problem, a genetic algorithm named dynamic genetic algorithm (DGA) is proposed to solve it. Since this problem has not been mentioned in the literature, DGA performance was evaluated by comparing its outputs with optimum solutions for small-sized problems and to the random search approach for larger problems. Additionally, the performance of the DGA was compared with that of a similar problem from the literature. The results of these comparisons show that the DGA is an excellent approach. In addition, the impact of grouping technology initialization is examined, showing that the quality of the solution was not improved and that there was an increase in the CPU time.