Pareto-Based Complete Local Search and Combined Timetabling for Multi-objective Job Shop Scheduling Problem with No-Wait Constraint

Job shop scheduling has become the basis and core of advanced manufacturing technology. Various differences exist between academic research and practical production. The majority of previous researches on job shop scheduling problem (JSSP)describe the basic production environment, which have a single objective and limited constraints. However,a practical process of production is characterized by having multiple objectives,no-wait constraint,and limited storage. Thus this research focused on multiobjective,no-wait JSSP. To analyze the problem,it was further divided into two sub-problems, namely, sequencing and timetabling. Hybrid non-order strategy and modified complete local search with memory were used to solve each problem individually. A Pareto-based strategy for performing fitness assessment was presented in this study. Various experiments on benchmark problems proved the feasibility and effectiveness of the proposed algorithm.     

耦合约束柔性作业车间调度优化研究

为扩展工艺约束的存在形式,对耦合约束柔性作业车间调度模型构建与调度优化算法设计进行探讨。在沿用链式约束调度的形式化与图形化描述构建耦合约束模型的基础上,对耦合约束邻域结构进行设计,选取禁忌搜索算法为设计框架,围绕算法执行步骤进行设计,并采用耦合约束案例与Brandimarte测试数据验证调度优化算法的适用性与优化性。耦合约束模型构建与调度算法的探讨为多部件系统作业的调度优化提供解决方案,也为调度相关邻域的深入研究拓宽思路。     

基于遗传算法的高校排课数学模型

排课问题是一个有约束、多目标的组合优化问题,并且已经被证明是一个NP完全问题。针对高校排课过程中存在诸多约束因素的问题,提出将遗传算法与约束条件算法相结合的排课算法,由约束条件算法确定排课任务的优先次序,遗传算法解决单个排课任务时间片分配的优化问题。实验结果表明,该算法能够改进算法性能,提高排课效率。     

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

将遗传算法与模拟退火相结合,提出了一种新调度算法,算法分成两步,首先利用遗传算法快速搜索一组较好解,然后利用模拟退火进行群体寻优,这样,既能克服遗传算法过早收敛的弱点,又能加快模拟退火的收敛速度,实验表明,该算法具有较高的求解质量和效率。     

基于粒子群优化的多目标作业车间调度

为了利用粒子群优化算法解决作业车间调度问题,提出了将调度问题转化为连续优化问题的有效策略;设计了Pareto档案粒子群算法(PAPSO),该算法将档案维护和全局最好位置选取结合在一起,在档案维护过程中为每个粒子选取全局最好位置;给出了变异与PAPSO的结合新策略.将PAPSO和带变异的PAPSO应用于15个调度实例,以最小化总拖后时间和最大完成时间,与强度Pareto进化算法2等进行比较,结果验证了PAPSO在作业车间调度方面的良好性能.     

Job Shop类型柔性制造系统调度问题的研究

研究了 Job Shop类型柔性制造系统的调度问题 ,其中每个工件都有多个可替代的工艺计划 ,并且每个操作均可在多个机器上选择加工 .建立了多目标混合整数规划模型 ,并设计了一种启发式算法进行求解 .实践表明 ,该算法具有较好的实用性和可行性     

考虑排班的人力资源投入问题的建模与优化

结合实际生产或项目中的排班情况,提出考虑排班的人力资源投入问题。针对该问题建立了以最小化人力资源投入为目标的数学模型。根据资源投入量与排班约束的性质,将原问题数学模型简化,证明简化后问题的数学模型与原问题最优解一致,并通过CPLEX软件求解过程,说明简化后的数学模型在求解速度上表现出很大的优越性。对于大规模问题,由于排班约束会导致班次间资源占用,使用传统任务列表编码方式难以获得较优的解。为此,提出了一种新型编码方式的遗传算法。该算法采用对作业延迟时间进行编码的方式,对作业开始时间进行搜索。为了提升算法的局部搜索能力,对作业延迟时间和开始时间进行局部优化。最后,通过数值实验与CPLEX和文献的算法比较,表明该算法的有效性。     

面向作业车间调度问题的遗传算法改进

为了获得遗传算法在作业车间调度问题上的最优化解,提高算法的迭代速度,研究了遗传算法的改进方法,以工件的加工时间最短为目标建立调度模型。在算法上提出了基于概率改进的具有自适应能力的交叉与变异算子,以求作业车间调度问题的最优解。在遗传算法上采用精英保留策略方法,并结合改进的自适应算子对问题进行求解。以基准案例LA01和FT06作为实验仿真对象,获得了相应的甘特图以及搜索过程曲线。仿真结果表明,与未改进的算法相比,该算法能够更加快速地获得最优解。改进后的算法在搜索上更加快速有效,在求解作业车间调度问题上具有一定的可行性,更加适合工业加工生产。     

改进遗传算法求解柔性job-shop调度问题

本文提出了一种改进遗传算法用于求解柔性作业调度问题(FJSP).针对工序在不同的机器上加工的差异性,我们提出了用能力系数来表征机器的加工能力,不仅可以简化处理而且也较为符合实际情况.该改进算法通过轮换的方法,将加工任务分配到不同的并行机器上去执行,有利于机器的负载平衡.同时,在方法的实现过程中,利用面向对象的思想,将问题进行抽象,用不同的类封装车间,机器和工序信息,这不仅符合现代编程风格,简化编程,也有利于系统的扩展和重构.仿真结果表明,不仅整个加工过程的执行时间得到了优化,而且各类机器完成的操作数相同,使用的时间也较为平均,达到了设计目标.同时该方法的计算速度也较快,适用于较大规模作业车间调度问题的求解.     

柔性流水作业排序问题的贪心算法求解

柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题,给出了求解柔性流水作业排序问题近似解的贪心算法,并对其性能进行了分析测试。结果表明,虽然该贪心算法求出的近似解与最优解相比有一定误差,但由于其时间复杂度较小,因此对求解车间作业调度问题仍有一定的现实意义。     

退化工件2台机器异序车间作业排序问题

：文章讨论退化工件2台机器异序车间作业排序问题。在异序车间作业环境中,每个工件由一些工序组成,工序的个数未必与机器数相同。此外,每个工件有各自的工序加工顺序。工件可能多次在某些机器上加工,也可能根本不在某些机器上加工。假设工件的实际加工时间是其开始时间的比例函数,目标函数是极小化最大完工时间。首先证明了具有任意工序的问题是强意义下NP-难的;然后对每个工件最多只有2个工序的问题给出了多项式算法;最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的。     

车间多载自动导引车绿色物流调度

随着现代制造业的飞速发展,企业在生产效率和生产能耗方面有越来越高的要求,智能生产车间的自动化程度逐渐提高。主要研究作业车间自动导引车(automated guided vehicle,AGV)的智能绿色物流调度问题。首先,建立以降低AGV能耗和最优AGV路径为目标的AGV物流调度优化模型;然后,提出一种以任务排序为约束的改进遗传粒子群算法;最后,以某针织车间的实际物流调度为例对文中方法进行验证。计算结果表明,文中提出的AGV物流调度模型能够较好地模拟AGV绿色调度耗能问题,提出的改进遗传粒子群算法具有较快的收敛速度和较好的寻优能力。     

基于INSGA-II高维目标柔性作业车间调度的优化

高维目标柔性作业车间调度问题(many-objective flexible job shop scheduling problem,MaOFJSP)是指在实际生产中根据企业不同部门的要求,对车间生产寄予不同的期望,使各个部门利益最大化的调度决策。针对完工时间、拖期时长、机器负荷、能耗4个优化目标,提出了改进非支配解遗传算法(improved non-dominated sorting genetic algorithm,INSGA-II)来求解MaOFJSP,同时对算法的编码解码、Pareto排序、选择策略、交叉变异操作进行了研究。采用工序排序和机器选择的双层个体编码方式,在精英选择过程中计算个体的斜率,斜率小的进入到父代,使得优秀个体得以保存;在变异环节中基于关键工序块邻域结构,采用插入法让工序小的工件优先加工,使得最大完工时间明显变小。通过该算法对不同算例进行的Matlab模拟仿真,验证了该模型的可行性和算法的优越性。     

考虑多种时间因素的作业车间调度优化

为了简化模型和研究的需要,在大部分作业车间调度研究中,加工时间是主要考虑对象,但是统计表明非加工过程时间在生产制造过程中的占比超过90%。车间生产过程的调整时间、运输时间和故障时间等辅助时间在调度中有着重要作用,时间因素的忽略导致很多调度结果不能在实践中得到良好的应用。针对这个问题,根据作业车间生产实际过程,从调度的应用出发,综合分析了运输时间、调整时间、等待时间、故障时间、加工时间等多种作业车间时间,研究了多种辅助时间条件下的作业车间调度问题,建立其调度模型并设计了改进遗传算法进行求解。最后验证和比较了作业车间经典调度用例,结果显示,考虑时间因素对作业车间调度优化性有较好的改进。     

A New Local Search Algorithm for the Job Shop Scheduling Problem

0　IntroductionThejobshopschedulingproblemwithwhichwearecon cernedconsistsinschedulingasetofjobsonasetofma chinesfortheobjectiveofminimizingthemake span ,i.e .themaximumoftimeneededforfinishingalljobs,whichissubjecttotheconstrainsthateachjobhasafixedprocessingorderthroughthemachinesandeachmachinecanprocessatmostonejobatatime .ThisproblemisNP hardandevenisoneofthehardestcom binationaloptimizationproblems.Itiswellknownthatonlysmallsizeprobleminstancescanbesolvedwithinareasonablecomputa tionalti…     

基于Backbone的空间收缩与划分算法

搜索空间的规模和复杂程度是决定问题求解难度的重要因素,而解空间的信息往往可以引导搜索找到最优解。在已知JSP空间结构的基础上,提出一种空间收缩与划分算法。算法利用搜索算法获得的较优解,结合组合优化问题解的backbone的概念,将搜索空间收缩并划分为一个或多个优解域,在优解域内再进行小规模问题的优化。该算法不必在求解前或求解过程中进行大量的统计分析工作,可以利用求解信息对解空间的地形进行估计,提高求解速度和解的质量。实验结果也证明了算法的有效性。     

基于混合变邻域遗传算法的柔性车间调度研究

针对柔性作业车间调度的问题，以最大完工时间为目标建立数学模型，提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量，用遗传算法进行初步搜索，将搜索的结果通过迭代贪婪策略进一步搜索，以提高解的质量，再对关键路径进行邻域搜索，设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构，加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试，实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。     

基于熵的混合粒子群算法在柔性调度中的应用

为了更好地求解大规模柔性车间调度问题,提高柔性车间调度算法的寻优性能,提出一种基于熵的混合粒子群算法.该算法把粒子群算法、遗传算法和模拟退火算法相结合,同时用种群熵自适应调节惯性系数和变异概率,以增强算法的寻优能力和克服算法的过早收敛.典型实例仿真结果表明,该算法能更好地求解柔性车间调度问题,与传统的优化算法相比,在优化精度上具有明显的优越性.     

基于具有自适应与自学习能力的粒子群优化算法的车间调度算法

针对车间调度问题, 提出一种新的基于粒子群优化和模拟退火的混合算法. 该算法将问题规模作为启发式信息, 通过对模拟退火算法引入新的邻域搜索机制--多粒度搜索, 并加入选择优化和淘汰更新机制, 提高了算法的自适应性和自学习能力, 降低了粒子群算法陷入局部最优的可能性. 实验结果表明, 该算法在最优解的求解能力上优于其他算法.     

JSSP基本约束特点分析及调度算法

车间作业调度问题(JSSP)具有两类基本约束,即工件工艺路径约束和资源(机台)独占性约束;如何解决"死锁"是以工件加工次序为决策变量的JSSP调度算法需要研究的重要问题之一。该文研究了JSSP基本约束的特点,在此基础上,提出了一种基于操作顺序的可行解生成方法,以及基于此方法的遗传算法(GA),并进行了数值计算;针对不同实例,该GA可以稳定地得到满意解,并具有较好的动态性能。该文所提出的方法易于实现,运算量小,与其他搜索算法结合后,可用于求解许多更一般的JSSP。