基于进化算法和模拟退火算法的混合调度算法

将进化算法与模拟退火算法相结合,提出四种有效的混合调度算法,即遗传退火算法、改进遗传算法、改进进化规划和并行模拟退火算法。两种算法搜索机制的互补增强了全局探索能力,基于关键路径的邻域函数运用提高了算法的效率。仿真结果表明:混合算法在求解质量和求解效率方面均有优势,优于国外同类研究成果;基于模拟退火的变异算子的搜索能力优于交叉算子;改进进化规划优于其他混合算法。     

Hybrid algorithms for the uncapacitated continuous location-allocation problem

In this paper, hybrid algorithms are developed for the multisource location-allocation problem in continuous space. Three hybrid algorithms are proposed to solve this problem that combine elements of several traditional metaheuristics (genetic algorithm and variable neighborhood search) and local searches to find near-optimal solutions. Many problems from the literature have been solved with these algorithms and the obtained results confirm the robustness of the proposed hybrid algorithms. Moreover, the results show that in comparison to the best methods in literature (GA and VNS), these algorithms provide some better solutions.     

Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics

Simulated annealing (SA), genetic algorithms (GA), and tabu search (TS) are the three well known meta-heuristics for combinatorial optimization problems. In this paper, single-machine total weighted tardiness problems with sequence-dependent setup times are solved by SA, GA, and TS approaches. A random swap and insertion search is applied in SA, and a mutation operator performed by a greedy local search is used in a GA. Similarly, a swap and an insertion tabu list are adopted in TS. To verify these proposed approaches, computational experiments were conducted on benchmark problem sets. The experimental results show that these approaches find new upper bound values for most benchmark problems within reasonable computational expenses.     

Heuristic search algorithms for lot streaming in a two-machine flowshop

The objective of this paper is to propose and evaluate heuristic search algorithms for a two-machine flowshop problem with multiple jobs requiring lot streaming that minimizes makespan. A job here implies many identical items. Lot streaming creates sublots to move the completed portion of a production lot to second machine. The three heuristic search algorithms evaluated in this paper are Baker’s approach (Baker), genetic algorithm (GA) and simulated annealing (SA) algorithm. To create neighborhoods for SA, three perturbation schemes, viz., pair-wise exchange, insertion and random insertion are used, and the performance of these on the final schedule is also compared. A wide variety of data sets is randomly generated for comparative evaluation. The parameters for GA and SA are obtained after conducting sensitivity analysis. The genetic algorithm is found to perform well for lot streaming in the two-machine flowshop scheduling.     

Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops

This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results.     

Optimization of process planning with various flexibilities using an imperialist competitive algorithm

In this paper, we investigate the optimization of process planning in which various flexibilities are considered. The objective is to minimize total weighted sum of manufacturing costs. Various flexibilities, including process flexibility, sequence flexibility, machine flexibility, tool flexibility, and tool access direction (TAD) flexibility, generally exist in process planning and consideration of these flexibilities is essential for improving production efficiency and system flexibility. However, process planning is strongly NP-hard due to the existence of various flexibilities as well as complex machining precedence constraints. To tackle this problem, an imperialist competitive algorithm (ICA) is employed to find promising solutions with reasonable computational cost. ICA is a novel socio-politically motivated metaheuristic algorithm inspired by imperialist competition. It starts with an initial population and proceeds through assimilation, position exchange, imperialistic competition, and elimination. Computational experiments on three sets of process planning problem taken from literature are carried out, and comparisons with some existing algorithms developed for process planning are presented. The results show that the algorithm performs significantly better than existing algorithms like genetic algorithm (GA), simulated annealing (SA), tabu search (TS), and particle swarm optimization (PSO).     

基于混合遗传算法的车间调度问题的研究

作业车间调度问题是最困难的组合优化问题之一，也是计算机集成制造系统中的一个关键环节，在实际生产中具有广泛应用。为此，提出了实现车间调度的混合遗传算法的设计方案，把遗传算法与模拟退火算法相结合，充分发挥遗传算法良好的全局搜索能力和模拟退火算法有效避免陷入局部极小的特性。通过实验验证了基于GASA混合算法的作业车间调度方法显著提高了搜索效率，改进了收敛性能。     

Sensitivity search for the rescheduling of semiconductor photolithography operations

This study deals with the rescheduling problem of the photolithography area in semiconductor wafer fabrications. The objective is to find a schedule that minimizes the weighted sum of makespan, maximum tardiness, and total setup time. Practical issues such as machine breakdowns, limited number of available masks, restrictions on photoresist, production notice, and machine setup are considered. Three popular search algorithms—simulated annealing (SA), genetic algorithm (GA), and tabu search (TS) — are tested to solve the scheduling problem. We also propose a new sensitivity search approach. A new event changes the scheduling problem. Thus, the problem needs to be re-solved to reflect such changes. In an actual production environment, we propose that, instead of searching for a solution from scratch, the search process can be restarted from the best solution of an original problem that is very similar to the new problem. Using an industrial data set, this study tests the proposed approach. The results show that TS performs the best among the algorithms tested, and the performance of the sensitivity TS significantly surpasses that of the traditional approach.     

一种基于改进遗传算法的车间调度问题研究

作业车间调度是一类求解较困难的组合优化问题,在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性,该特性最终使算法能够趋于全局最优。在此基础上,将遗传算法和模拟退火算法相结合,提出了一种基于遗传和模拟退火的混合算法,该算法将模拟退火算法赋予搜索过程一种时变性融入其中,具有明显的概率跳跃性。同时。通过选取Brandimarte基准问题和经典的Benchmarks基准问题进行分析,并应用实例对该算法进行了仿真研究。该结果表明,通过模拟退火算法与遗产算法相集合,可以使计算的收敛精度明显提高,是行之有效的,与传统的算法相比较,有较明显的优越性。     

Fixed-quantity dynamic lot sizing using simulated annealing

In this paper, simulated annealing (SA) is applied to the deterministic dynamic lot-sizing problem with batch ordering and backorders. Batch ordering requires orders that are integer multiples of a fixed quantity that is larger than 1. The performance of the developed SA heuristic is compared to that of a genetic algorithm (GA) and a modified silver-meal (MSM) heuristic developed in the literature, based on the frequency of obtaining the optimum solution and the percentage average deviation from the optimum solution. In addition, the effects of three factors on the performance of the SA, GA, and the MSM are investigated in a 2³ factorial experiment. The investigated factors are the demand pattern, the batch size, and the length of the planning horizon. Results indicate that the SA heuristic has the best performance, followed by GA, in terms of the frequency of obtaining the optimum solution and the average deviation from the optimum solution. SA is also the most robust of the investigated heuristics as its performance is only affected by the length of the planning horizon.     

An intelligent hybrid meta-heuristic for solving a case of no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machines

This paper addresses the problem of no-wait two-stage flexible flow shop scheduling problem (NWTSFFSSP) considering unrelated parallel machines, sequence-dependent setup times, probable reworks and different ready times to actualize the problem. The performance measure used in this study is minimizing maximum completion time (makespan). Because of the complexity of addressed problem, we propose a novel intelligent hybrid algorithm [called hybrid algorithm (HA)] based on imperialist competitive algorithm (ICA) which are combined with simulated annealing (SA), variable neighborhood search (VNS) and genetic algorithm (GA) for solving the mentioned problem. The hybridization is carried out to overcome some existing drawbacks of each of these three algorithms and also for increasing the capability of ICA. To achieve reliable results, Taguchi approach is used to define robust parameters' values for our proposed algorithm. A simulation model is developed to study the performance of our proposed algorithm against ICA, SA, VNS, GA and ant colony optimization (ACO). The results of the study reveal the relative superiority of HA studied. In addition, potential areas for further researches are highlighted.     

A hybrid genetic algorithm for integrated process planning and scheduling problem with precedence constraints

Process planning and scheduling are two important functions in a modern manufacturing system. Although integrating decisions related to these functions gives rise to a hard combinatorial problem, due to the impressive improvement in system performance which is resulted through this integration, developing effective methods to solve this problem is of great theoretical and practical importance. In this research, after formulating the integrated process planning and scheduling problem as a mathematical program, we propose a hybrid genetic algorithm (GA) for the problem. In the proposed algorithm, problem-specific genetic operators are designed to enhance the global search power of GA. Also, a local search procedure has been incorporated into the GA to improve the performance of the algorithm. The model considers precedence relations among job operations, based on which feasible process plans for each job can be represented implicitly. A novel neighborhood function, considering the constraints of a flexible job shop environment and nonlinear precedence relations among operations, is presented to speed up the local search process. In experimental study, the performance of the proposed algorithm has been evaluated based on a number of problems adopted from the literature. The experimental results demonstrate the efficiency of the proposed algorithm to find optimal or near-optimal solutions.     

CAPACITATED LOT SIZING AND SCHEDULING PROBLEMS USING HYBRID GA／TS APPROACHES

The capacitated lot sizing and scheduling probbm that involves in determining the production amounts and release dates for several items over a given planning horizon are given to meet dynamic order demand without incurring backloggings. Thi: problem considering overtime capacity is studied. The mathematical model is presented, and a genelic algorithm (GA) approach is developed to solve the problem. The initial solutions are generated after using heuristic method. Capacity balancing procedure is employed to stipulate the feasibility of the solutions. In addition, a technique based on Tabu search (TS) is inserted into the genetic algorithm to d;al with the scheduled overtime and help the convergence of algorithm. Computational simulation is conducted to test the efficiency of the proposed hybrid approach, which turns out to improve both the solution quality and execution speed.     

Machine-Cell Grouping in Cellular Manufacturing Systems Using Non-traditional Optimisation Techniques - A Comparative Study

In this paper, the machine-cell grouping problem is considered with the objective of minimising the total moves and minimising the cell load variation. We first review the literature on machine-cell grouping involving meta-heuristics. Then we integrate the most powerful non-traditional algorithms, genetic algorithm (GA) and simulated annealing (SA) with the most robust computer programming language "C", for cell grouping. The computational results obtained by applying the genetic algorithm and simulated annealing are compared for their efficiency in solving the machine-cell grouping problems.     

基于混合遗传算法的混流混合车间协同调度问题

为解决一类具有多品种混流生产特征和作业车间与流水车间集成的混流混合车间协同调度问题,给出了以在制品成本最小为目标的混流混合车间调度问题模型;采用零件加工、部件装配、产品总装的三段协同编码方法,给出了一种集成模拟退火算法的混合遗传算法,并在模拟退火算法中引入变温度参数来平衡算法效率。最后,通过某冰箱混流装配企业典型实例验证了模型和算法的有效性。     

基于混合遗传算法的桥梁颤振导数识别

提出一种基于混合遗传算法识别桥梁颤振导数的方法,该混合遗传算法将模拟退火算法与遗传算法相结合,充分利用遗传算法的并行运算机制以及模拟退火算法的强局部搜索机制,具有较强的鲁棒性和全局收敛性,从而保证识别的精度。该方法通过对自由振动时程曲线进行时域拟合,识别出自由振动表达式中的各参数,进而确定系统的等效刚度矩阵和等效阻尼矩阵,并同时得到8个颤振导数。数值仿真算例表明该方法的可靠性,风洞试验表明该方法有效、可行。     

求解车间调度问题的一种新遗传退火混合策略

综合了遗传算法和模拟退火算法的优点,提出了一种新的遗传退火混合优化策略。该算法引入模拟退火算法作为遗传算法种群的变异算子,增强和补充了遗传算法的进化能力,同时将机器学习原理引入混合算法中,增加了种群的平均适值,有效地避免了最优解的丢失,加快了进化速度,使系统能够在很短的时间内得到最优解。针对车间调度的典型问题进行了仿真,结果证明了新算法的有效性。     

Scheduling optimisation of flexible manufacturing systems using particle swarm optimisation algorithm

The increased use of flexible manufacturing systems (FMS) to efficiently provide customers with diversified products has created a significant set of operational challenges. Although extensive research has been conducted on design and operational problems of automated manufacturing systems, many problems remain unsolved. In particular, the scheduling task, the control problem during the operation, is of importance owing to the dynamic nature of the FMS such as flexible parts, tools and automated guided vehicle (AGV) routings. The FMS scheduling problem has been tackled by various traditional optimisation techniques. While these methods can give an optimal solution to small-scale problems, they are often inefficient when applied to larger-scale problems. In this work, different scheduling mechanisms are designed to generate optimum scheduling; these include non-traditional approaches such as genetic algorithm (GA), simulated annealing (SA) algorithm, memetic algorithm (MA) and particle swarm algorithm (PSA) by considering multiple objectives, i.e., minimising the idle time of the machine and minimising the total penalty cost for not meeting the deadline concurrently. The memetic algorithm presented here is essentially a genetic algorithm with an element of simulated annealing. The results of the different optimisation algorithms (memetic algorithm, genetic algorithm, simulated annealing, and particle swarm algorithm) are compared and conclusions are presented .     

Optimization of cutting conditions during continuous finished profile machining using non-traditional techniques

Optimum machining parameters are of great concern in manufacturing environments, where economy of machining operation plays a key role in competitiveness in the market. Many researchers have dealt with the optimization of machining parameters for turning operations with constant diameters only. All Computer Numerical Control (CNC) machines produce the finished components from the bar stock. Finished profiles consist of straight turning, facing, taper and circular machining.This research work concentrates on optimizing the machining parameters for turning cylindrical stocks into continuous finished profiles. The machining parameters in multi-pass turning are depth of cut, cutting speed and feed. The machining performance is measured by the production cost.In this paper the optimal machining parameters for continuous profile machining are determined with respect to the minimum production cost subject to a set of practical constraints. The constraints considered in this problem are cutting force, power constraint, tool tip temperature, etc. Due to high complexity of this machining optimization problem, six non-traditional algorithms, the genetic algorithm (GA), simulated annealing algorithm (SA), Tabu search algorithm (TS), memetic algorithm (MA), ants colony algorithm (ACO) and the particle swarm optimization (PSO) have been employed to resolve this problem. The results obtained from GA, SA,TS, ACO, MA and PSO are compared for various profiles. Also, a comprehensive user-friendly software package has been developed to input the profile interactively and to obtain the optimal parameters using all six algorithms. New evolutionary PSO is explained with an illustration .     

Application of an efficient modified particle swarm optimization algorithm for process planning

In the modern manufacturing system, many flexible manufacturing system and NC machines are introduced to improve the production efficiency. Therefore, most parts have a large number of flexible process plans. However, a part can use only one process plan in the manufacturing process. So, the process planning problem has become a crucial problem in the manufacturing environment. It is a combinatorial optimization problem to conduct operations selection and operations sequencing simultaneously with various constraints deriving from the practical workshop environment as well as the parts to be processed. It is a NP-hard problem. In order to solve this problem effectively, this paper proposes a novel modified particle swarm optimization (PSO) algorithm to optimize the process planning problem. To improve the performance of the approach, efficient encoding, updating, and random search methods have been developed. To verify the feasibility and effectiveness of the proposed approach, seven cases have been conducted. The proposed algorithm has also been compared with the genetic algorithm and simulated annealing algorithm. The results show that the proposed modified PSO algorithm can generate satisfactory solutions and outperform other algorithms.