混合遗传算法在桥式起重机结构优化中的应用

针对工程中的变量离散化问题，提出了一种将遗传算法和模拟退火算法相结合的混合算法。该算法发挥了遗传算法和模拟退火算法的优越性，避免了遗传算法的早熟收敛问题，增强了算法的全局收敛性，并提高了算法的收敛速度。通过对桥式起重机金属结构进行优化，其结果与MDOD和改进遗传算法2种的结果进行比较，表明此算法能够很好处理工程离散化问题。     

基于混合遗传算法的MTSP问题研究

为了得到多旅行商问题的优化路线，提出一种基于实数编码的混合遗传算法。即先建立数学模型，将多旅行商问题转化为单旅行商问题，然后详细介绍了混合遗传算法设计过程，同时对该算法进行了收敛性分析与仿真试验。结果表明基于实数编码的混合遗传算法是一种有效的多旅行商问题求解方法，该算法能以较大的概率获得全局最优解。     

含作业到达时间的单机调度问题的改进算法

研究了以作业完成时间之和最小化为目标函数的单机调度问题，该问题中各作业到达时间可能不同。在对传统启发式算法进行分析的基础上，提出一种改进算法，并给出了算例及其计算结果。大量的随机数据实验的结果表明，该改进算法的性能比传统启发式算法的性能更优。     

一种适于复杂零件排样的改进算法研究

在对排样问题进行了深入分析的基础上，对传统的平移算法进行了必要的改进，提出了一种新的优化算法并进行了验证，以该算法为核心的排样系统除可完成一般的卷料，条料，板料上的单排，双排和对头排外，还可求解嵌套排样问题，具有计算速度快，优化效果明显，优化结果可靠等优点。     

Hermite五坐标数控加工刀位算法研究

复杂自由曲面五坐标刀位优化问题一直是数控加工领域的一个热点问题，该问题的解决对于显著提高国防和民用工业中重要零件的加工质量和加工效率具有重要意义。Hermite27位算法和MPM算法是国际上最近提出的2种最先进的五坐标27位优化算法。作者给出了2种算法的完整数学模型，将Hermite算法与MPM算法进行了比较研究，从理论上对2种算法解的一致性进行了证明，对2种算法求解过程的重要差别进行了比较，对Hermite算法的求解过程进行了改进，并通过2个实例验证了所提出的改进算法的可行性。     

基于改进粒子群算法的开放式定位-运输路线问题研究

将开放式车辆路径问题和定位-分配问题集成考虑，建立了该问题的数学模型；运用基于遗传算法、模拟退火算法的改进粒子群算法，对一个开放式定位-运输路线问题进行了求解。历次迭代产生的全局历史最优解的良好收敛，验证了模型的正确性和算法的有效性。     

半导体制造批量计划调度问题的量子粒子群算法研究

对半导体制造批量计划调度问题进行研究,提出了一种收敛速度快、全局性能好、不易陷入局部最优的智能迭代算法一量子粒子群算法来实现对该问题的求解.该算法采用0-1编码方式,来实现对lot的分批和分配,并以最小完工时间为目标函数值进行寻优.最后通过具体算例,对该算法进行了仿真验证,结果表明,在求解半导体制造批量计划调度问题时,量子粒子群算法要优于二级蚂蚁算法、DSH算法,从而验证了该算法的可行性和有效性.     

考虑工件释放时间和柔性维护的单机调度问题

针对晶圆制造过程中考虑清洗维护的生产调度联合优化问题，以最小化最大完工时间为求解目标，优化工件加工顺序及维护活动执行时间。证明了该问题为NP难的，建立了问题的整数规划模型并进行线性化。结合机器役龄约束下的成批调度问题特征，证明了解的性质，并设计ERD-LPT-BFLD启发式算法对问题进行求解。构建了考虑工件释放时间及清洁活动约束的下界算法。通过不同规模算例仿真实验，将所提启发式算法与CPLEX及下界算法求解结果进行比较，验证了所提算法的有效性。     

解空间编码遗传算法在三维布局中的应用

采用改进遗传算法——解空间编码的遗传算法求解带性能约束的复杂三维布局设计问题。算法对三维空间布局问题进行了预处理，直接将问题的求解变量作为染色体基因进行编码，降低了算法的编码和解码难度。在求解过程中，对不同变量类型采用不同的交叉和变异算子进行计算，并且在变异前对复制或交叉所得个体的某些变量随机加一个扰动量，以控制其搜索范围，算法以计算结果满足设计要求为算法终止准则。通过对二维和三维带性能约束布局算例的求解，验证了该算法的可行性和有效性。     

二维不规则多边形自动布局系统的研究与设计

布局问题来源于现代生产的许多领域，并且表现为多种形式，但由于该问题在理论上属于NP完备问题，很难用传统的优化算法求解。讨论了二维不规则多边形自动布局系统的思想和设计技术，对模拟退火算法的搜索方法进行了分析，给出其一般搜索模型。针对不规则多边形的具体情况，对它的相交判断以及其它约束条件进行了论述。     

并行多机提前/拖期调度的启发式算法

准时制生产模式要求生产任务必须在交货期内完成.实际生产中这一问题受很多约束的影响变得非常复杂.文章针对任务动态到达、任务转换存在的调整时间和交货期、提前/拖期单位成本各不相同的并行多机上任务排序问题进行了分析,设计了一种解决并行多机提前/拖期调度的启发式近似求解算法.大量实验数据和应用实例充分表明文章所提的启发式算法是有效的.     

Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

A genetic-algorithm-based optimization model for scheduling flexible assembly lines

In this paper, a scheduling problem in the flexible assembly line (FAL) is investigated. The mathematical model for this problem is presented with the objectives of minimizing the weighted sum of tardiness and earliness penalties and balancing the production flow of the FAL, which considers flexible operation assignments. A bi-level genetic algorithm is developed to solve the scheduling problem. In this algorithm, a new chromosome representation is presented to tackle the operation assignment by assigning one operation to multiple machines as well as assigning multiple operations to one machine. Furthermore, a heuristic initialization process and modified genetic operators are proposed. The proposed optimization algorithm is validated using two sets of real production data. Experimental results demonstrate that the proposed optimization model can solve the scheduling problem effectively.     

流水车间作业提前/拖期调度问题研究

在非正规性能指标提前／拖期调度问题中,工件的加工顺序和每个加工活动的开始时刻都属于需要优化的变量,增加了求解的难度。针对这一问题,提出了采用分层调度模式求解流水车间提前／拖期调度问题的联合算法。首先,采用遗传算法对加工顺序进行寻优;其次,在给定调度序列的情况下采用启发式算法对加工开始时刻进行优化,制定插入机器空闲时段的策略,确定何时插入空闲时段和空闲时段的大小,即在给定顺序下确定工件加工活动的开始时刻,以满足在加工完所有工件后,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该联合算法的有效性。     

Due window scheduling with sequence-dependent setup on parallel machines using three hybrid metaheuristic algorithms

Due-date determination problems have gained significant attention in recent years due to the industrial focus in the just-in-time philosophy. This paper considers a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence, both earliness and tardiness should be penalized. It is assumed that earliness and tardiness (ET) penalties will not occur if a job is completed within the due window. However, ET penalties will occur if a job is completed outside the due window. The objective is to determine a schedule that minimizes sum of the earliness and tardiness of jobs. To achieve this objective, three hybrid metaheuristics are proposed. The first metaheuristic is a hybrid algorithm which combines elements from both simulated annealing (SA) as constructive heuristic search and a variable neighborhood search (VNS) as local search improvement technique. The second one presents a hybrid metaheuristic algorithm which composed of a population generation method based on an ant colony optimization (ACO) and a VNS to improve the population. Finally, a hybrid metaheuristic approach is proposed which integrates several features from ACO, SA, and VNS in a new configurable scheduling algorithm. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. Computational experiments conducting on 252 randomly generated problems compare the results with the VNS algorithm proposed previously and show that the procedure is capable of producing consistently good results.     

Due windows group scheduling using an effective hybrid optimization approach

This paper considers the problem of scheduling part families (groups) and jobs within each part family in a hybrid flow shop manufacturing cell with sequence-dependent family setups times where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized while processing parts (jobs) in each family together. It is assumed that earliness and tardiness penalties will not occur if a job is completed within the due window. The objective is to determine a schedule that minimizes sum of the earliness and tardiness of jobs. To this problem, the hybrid metaheuristic algorithm combined elements from particle swarm optimization; simulated annealing and variable neighborhood search are developed. The aim of using a hybrid metaheuristic is to raise the level of generality so as to be able to apply the same solution method to several problems. Problem sizes ranging in size from small, medium, to large are considered along with three levels of flexibility. The higher the number of stages and the number of parallel machines in each stage, the higher is the flexibility introduced into the problem. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. We present computational experiments on 126 problems and compare the results with the simulated annealing and genetic algorithms that presented recently. The computational results show that our proposed algorithm is more efficient than the other methods.     

一种求解作业车间JIT调度问题的混合TS/MP算法

作业车间JIT调度属于一类典型的非正规性能指标调度问题,该类问题为每道工序设置了交货期约束,工序的提前或拖期完工均会产生相应的惩罚成本。采用禁忌搜索和数学规划相结合的混合调度方法进行求解。在算法的迭代搜索过程中,首先,由每个个体产生各机器上的工件加工序列,由此松弛了调度模型中的机器能力析取约束,然后,调用数学规划方法来优化各机器的空闲时间和各工序的开工时间。为提高禁忌搜索算法的计算效率,设计了一种包含交换和插入操作的邻域结构产生方案。最后,用JIT调度领域的32个标准测试算例验证了该调度算法的有效性。     

A new parallel genetic algorithm for solving multiobjective scheduling problems subjected to special process constraint

This study presents a multiobjective scheduling model on parallel machines (MOSP). Compared with other scheduling problems on parallel machines, the MOSP is distinct for the following characteristics: (1) parallel machines are nonidentical, (2) the type of jobs processed on each machine can be restricted, and (3) the multiobjective scheduling problem includes minimizing the maximum completion time among all the machines (makespan) and minimizing the total earliness/tardiness penalty of all the jobs. To solve the MOSP, a new parallel genetic algorithm (PIGA) based on the vector group encoding method and the immune method is proposed. For PIGA, its three distinct characteristics are as follows: Firstly, individuals are represented by a vector group, which can effectively reflect the virtual scheduling policy. Secondly, an immune operator is adopted and studied in order to guarantee diversity of the population. Finally, a local search algorithm is applied to improve the quality of the population. Numerical results show that it is efficient, can better overcome drawbacks of the general genetic algorithm, and has better parallelism.     

一类带有deadline约束的作业车间提前/拖期调度问题研究

针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。     

A GRASP heuristic for the multi-objective permutation flowshop scheduling problem

This paper presents a multi-objective greedy randomized adaptive search procedure (GRASP)-based heuristic for solving the permutation flowshop scheduling problem in order to minimize two and three objectives simultaneously: (1) makespan and maximum tardiness; (2) makespan, maximum tardiness, and total flowtime. GRASP is a competitive metaheuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a multi-objective problem and a new algorithm named multi-objective GRASP algorithm is proposed. In order to find a variety of non-dominated solutions, the heuristic blends two typical approaches used in multi-objective optimization: scalarizing functions and Pareto dominance. For instances involving two machines, the heuristic is compared with a bi-objective branch-and-bound algorithm proposed in the literature. For instances involving up to 80 jobs and 20 machines, the non-dominated solutions obtained by the heuristic are compared with solutions obtained by multi-objective genetic algorithms from the literature. Computational results indicate that GRASP is a promising approach for multi-objective optimization.