一种求解Job-shop调度问题的遗传局部搜索算法

利用遗传局部搜索算法求解了作业车间调度问题,遗传算法中的染色体编码采用基于工序的编码,并用插入式贪婪解码机制将染色体解码至主动调度。为了克服传统遗传算法易于早熟收敛的缺点,设计了一种改进的优先操作交叉IPOX操作和子代产生模式的遗传算法。对于遗传算法每个染色体个体,使用基于N6邻域结构的局部搜索进一步使它们得到改善。利用所提出的混合遗传算法求解基准问题,验证了算法的有效性。     

考虑工件移动和成本的多目标柔性作业车间调度问题优化研究

针对考虑工件移动时间约束的柔性作业车间调度问题,构建了以加工总成本和最大加工时间最小为目标的数学模型并用改进遗传算法求解。针对柔性作业车间调度问题(FJSP)特性,算法中采用基于工序的集成编码操作,实现工序排序和机器匹配的内在关联并由此产生可行的调度方案;根据编码结构设计了有效的交叉和变异操作,从而避免了非法调度解的出现;为克服遗传算法的早熟收敛和减少调度开销,用贪婪解码算法生成主动调度、设计了自适应变异规则并采用混合子代产生模式提高染色体适应值。最后通过测试问题的求解及数值分析,证明了算法和模型的有效性及鲁棒性。     

求解作业车间调度问题的一种改进遗传算法

为克服传统遗传算法解决车间作业调度问题的局限性,综合遗传算法和局部搜索的优点,提出一种改进的遗传算法。为基于工序的编码提出了一种新的POX交叉算子。同时,为克服传统遗传算法在求解车间作业调度问题时的早熟收敛,设计了一种子代交替模式的交叉方式,并运用局部搜索改善交叉和变异后得到的调度解,将提出的改进遗传算法应用于MuthandThompson基准问题的实验运行,显示了该算法的有效性。     

基于改进非支配排序遗传算法的多目标柔性作业车间调度

采用多目标进化算法解决具有工件释放时间、工件目标差异的柔性作业车间调度问题。依据实际制造系统中存在较多的最大完工时间、平均流经时间、总拖期时间、机器总负荷、瓶颈机器负荷和生产成本性能指标,建立多目标柔性作业车间调度模型。针对柔性作业车间调度问题的特点,设计一种扩展的基于工序的编码及其主动调度的解码机制,以及初始解产生机制和有效的交叉、变异操作;针对非支配排序遗传算法(Non-dominated sorting genetic algorithm II,NSGA-II)在非支配解排序和精英选择策略方面的不足,设计一种改进的非支配排序遗传算法,应用改进的算法求解柔性作业车间调度问题得到一组Pareto解集,并运用层次分析法选出最优妥协解。通过测试基准和模拟实际生产的实例,验证提出算法的可行性和有效性。     

改进元胞遗传算法求解柔性作业车间调度问题

针对柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)中的不同性能指标优化,提出一种改进的元胞遗传算法。结合柔性作业车间调度的特点,设计一种基于工序编码和设备分配的双层编码,在交叉变异时分别对两层编码进行操作,同时在变异时引入贪婪式变异以加快收敛速度。为了克服传统遗传算法早熟和收敛慢的特点,设计了根据邻居个体自适应的选择算子。将该改进的元胞遗传算法求解柔性作业车间调度问题并同其他遗传算法的测试结果进行比较,表明所提出的改进元胞遗传算法在求解柔性作业车间调度问题上的有效性。     

柔性作业车间调度问题的两级遗传算法

研究不同性能指标柔性作业车间调度问题的优化.针对柔性作业车间调度问题的特点,设计基于工序编码和基于机器分配编码的两种交叉和变异算子,并提出一种双层子代产生模式的改进遗传算法应用于该调度问题,以使子代更好地继承父代的优良特征.使用实例测试改进的遗传算法,并与其他遗传算法的测试结果进行比较,所提出算法的有效性得到证实.     

基于Plant Simulation的作业车间调度优化研究

针对某公司机械加工车间作业调度效率低、工件排序不合理问题,借助Plant Simulation软件仿真平台进行分析研究。首先建立作业车间调度问题的仿真模型,设计了基于改进工序编码的方式;然后采用遗传算法对该问题进行优化求解,优化最优解质量,得到调度问题的甘特图,提高了作业调度的效率;最后通过实例仿真,说明此方法解决JSSP的可行性和有效性。     

基于POX交叉的遗传算法求解Job-Shop调度问题

通过改进传统的遗传算法求解Job—Shop调度问题。为基于工序的编码提出了一种新的POX交叉算子，并与其他交叉算子进行了比较以显示其高效性。为了保留父代的优良特征和减少遗传算子的破坏性，设计了一种子代交替模式的交叉方式。将提出的改进遗传算法应用于muth and thompson‘s基准问题的实验运行，显示该算法的有效性。     

基于混合粒子群算法的汽车零件精冲车间调度研究

针对传统遗传算法在车间作业调度问题难以解决求解约束优化问题时存在难以同时兼顾求解质量和收敛效率这一问题,通过采用了基于工序编码的方式生成可行调度及借鉴遗传算法单点交叉方法,生成基于工件的交叉算子作为粒子的更新方式,将改进后的粒子群优化算法用于求解精冲零件车间调度问题,并在算法中通过利用局部搜索的方式提升粒子群中粒子收敛效率。通过对典型的调度测试问题进行模拟实验,证明了改进后的混合粒子群算法对于求解车间调度问题的适用性及具有不错的求解性能。     

双资源多工艺路线作业车间模糊调度问题研究

在研究双资源、多工艺路线作业车间调度的基础上,从实际作业车间调度系统存在大量不确定因素的情况出发,建立了模糊调度的数学模型。以最小完工时间和平均满意度最大为优化目标,基于遗传算法,对算法中初始种群的构造、适应度计算、遗传操作等方面进行了研究;应用改进的遗传算法,求解最优调度工序。最后给出了实例仿真和结论。     

An effective hybrid genetic algorithm for the job shop scheduling problem

From the computational point of view, the job shop scheduling problem (JSP) is one of the most notoriously intractable NP-hard optimization problems. This paper applies an effective hybrid genetic algorithm for the JSP. We proposed three novel features for this algorithm to solve the JSP. Firstly, a new full active schedule (FAS) procedure based on the operation-based representation is presented to construct a schedule. After a schedule is obtained, a local search heuristic is applied to improve the solution. Secondly, a new crossover operator, called the precedence operation crossover (POX), is proposed for the operation-based representation, which can preserve the meaningful characteristics of the previous generation. Thirdly, in order to reduce the disruptive effects of genetic operators, the approach of an improved generation alteration model is introduced. The proposed approaches are tested on some standard instances and compared with other approaches. The superior results validate the effectiveness of the proposed algorithm.     

基于粒子群优化和模拟退火的混合调度算法

提出了一种离散粒子群调度算法，采用基于工序的编码方式及相应的位置和速度更新方法，使具有连续本质的粒子群算法直接适用于调度问题。针对粒子群算法容易陷入局部最优的缺陷，将其与模拟退火算法结合，得到了粒子群-模拟退火算法、改进的粒子群算法、粒子群-模拟退火交替算法以及粒子群-模拟退火协同算法等4种混合调度算法。仿真结果表明，混合算法均具有较高的求解质量。     

基于遗传算法的服装生产流水调度研究

针对服装生产流水线调度问题,以最小化最大流程时间为目标,将具有全局优化特点遗传算法应用于服装生产流水线调度中.算法采用基于工序的编码方式和具有简单操作的单亲遗传算子,并在调度实例应用中取得满意的效果.仿真结果表明:该算法优化了调度方案,缩减了最小化完工时间,能够有效、高质量地解决服装生产流水线调度问题.     

基于混合禁忌搜索算法的供应链排序问题

分析非标准件加工企业供应链的特点,提出协同优化订单分配、生产调度和批量运输调度的多工厂多客户供应链排序问题。以工件的最长订货提前期与总成本加权之和最小化为目标,构建问题的数学模型。在分析解的最优性条件基础上,设计一种基于矢量组编码方法的混合禁忌搜索算法。算法对可行域进行分区,通过基于插入、交换两种邻域操作的禁忌搜索算法选择子区域,采用基于块结构邻域操作的禁忌搜索算法搜索子区域中的优良解。采用所提混合禁忌搜索算法对算例进行优化求解,并对采用不同编码方法、不同启发式算法的算例结果进行比较,结果表明所提出算法的有效性。     

Scheduling stochastic job shop subject to random breakdown to minimize makespan

The problem of scheduling stochastic job shop subject to breakdown is seldom considered. This paper proposes an efficient genetic algorithm (GA) for the problem with exponential processing time and non-resumable jobs. The objective is to minimize the stochastic makespan itself. In the proposed GA, a novel random key representation is suggested to represent the schedule of the problem and a discrete event-driven decoding method is applied to build the schedule and handle breakdown. Probability stochastic order and the addition operation of exponential random variables are also used to calculate the objective value. The proposed GA is applied to some test problems and compared with a simulated annealing and a particle swarm optimization. The computational results show the effectiveness of the GA and its promising advantage on stochastic scheduling.     

A Modified Genetic Algorithm for Job Shop Scheduling

As a class of typical production scheduling problems, job shop scheduling is one of the strongly NP-complete combinatorial optimisation problems, for which an enhanced genetic algorithm is proposed in this paper. An effective crossover operation for operation-based representation is used to guarantee the feasibility of the solutions, which are decoded into active schedules during the search process. The classical mutation operator is replaced by the metropolis sample process of simulated annealing with a probabilistic jumping property, to enhance the neighbourhood search and to avoid premature convergence with controllable deteriorating probability, as well as avoiding the difficulty of choosing the mutation rate. Multiple state generators are applied in a hybrid way to enhance the exploring potential and to enrich the diversity of neighbour-hoods. Simulation results demonstrate the effectiveness of the proposed algorithm, whose optimisation performance is markedly superior to that of a simple genetic algorithm and simulated annealing and is comparable to the best result reported in the literature.     

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

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