具有成组约束的柔性流水车间作业计划制定的启发式算法

发布时间：2020-03-19 20:49

【摘要】：具有成组约束的柔性流水车间调度问题普遍存在于离散制造业,对其进行研究具有重要理论意义和工程实用价值,因此吸引着越来越多研究人员对其进行研究。具有成组约束的柔性流水车间调度问题是传统调度问题的一种扩展,根据出现成组位置的不同可分为三类子问题：前、中、后成组约束的柔性流水车间调度问题。该类问题是柔性流水车间调度问题和成组问题相结合的混合车间调度问题,因此属于NP难问题。对于NP难问题,由于目标解的搜索涉及解空间的组合爆炸,所以通常不能有效地求出问题的最优解。线性规划、分支定界等传统方法对于稍大规模的车间调度问题的求解无能为力,因此,通常使用启发式算法求解该类问题。所以,本文研究了启发式算法在具有成组约束的柔性流水车间调度中的应用,取得的主要研究成果如下： 1.针对以最少化最大完工时间为目标的具有前成组约束的两阶段柔性流水车间调度问题,建立了其数学模型；通过对问题的结构进行分析,提出了一种启发式算法H,；对H’算法分析后,给出了H’算法的时间复杂度和最坏情况值；为了验证H’算法的效果,通过设计大量仿真算例和与其它三种改进后的经典启发式算法进行比较,结果表明H,算法对于求解具有前成组约束的两阶段柔性流水车间调度问题的优越性；最后,基于H,算法,提出一种启发式算法MH’求解具有前成组约束的多阶段柔性流水车间调度问题。 2.针对以总拖期量最少为目标的具有后成组约束的两阶段柔性流水车间调度问题,建立了其数学模型；通过对问题的分析,给出一条调度优势准则；基于该调度优势准则,提出了一种启发式算法EL；通过对EL算法进行分析,给出其时间复杂度和最坏情况值；为了验证EL算法的有效性,设计了该类问题的仿真算例,通过对算例的仿真及结果分析表明了算法的有效性和EL调度规则在求解该类问题时的优越性；最后,基于EL算法,提出一种启发式算法MEL求解具有后成组约束的多阶段柔性流水车间调度问题。 3.研究了求解目标为最少化最大完工时间的具有中成组约束的三阶段柔性流水车间调度问题,建立了该问题的数学模型；通过对问题的结构分析,提出了10种启发式算法,并给出了该10种启发式算法的时间复杂度；通过对问题进行分析,给出了该问题的四个下界；通过对该10种启发式算法进行分析,给出了其中9个启发式算法的最坏情况值；为了验证该10种启发式算法的求解效果,设计了仿真实验,仿真结果表明SP.JH-MJ算法对于求解具有中成组约束的三阶段柔性流水车间调度问题的优越性；最后基于SP.JH-MJ算法,提出了一种启发式算法MJL求解具有中成组约束的多阶段柔性流水车间调度问题。 4.开发了一套《基于成组约束的柔性流水车间调度问题的仿真平台》,通过该平台可以方便地产生不同问题的仿真实例,以及配置不同算法参数下得到每个算法的仿真结果,从而对相关调度算法的性能进行分析和比较。最后,基于上述步骤所获得的理论研究成果,并结合合作企业的实际运作特点,设计和开发了车间调度系统并成功应用在企业中。
【学位授予单位】：广东工业大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP301.6;F406.2

【参考文献】