任建锋[1]2003年在《两种新型排序问题的近似算法》文中研究说明论文主要内容包括两部分。第一部分针对m台同型机，工件具有到达时间的情况，研究了分批排序问P_m|r_j,B|∑C_j．由于1|r_j,B|∑C_j为NP—hard的，因而P_m|r_j,B|∑C_j也是NP—hard的．给出了当机器台数m及批容量B均为常数情况下的PTAS算法．第二部分研究了具有可用时间限制的两道工序的柔性流水车间排序问题F_2(p)，h_(11.1)|m_1,M_2=μ2|C_(max)，论文提出了几种近似算法，给出了算法的相应性能比，改进了一些已有的结果。 第一部分 P_m|r_j,B|∑C_j的PTAS算法 论文首次提出并研究了工件具有到达时间的分批排序问题P_m|r_j,B|∑C_j．在以下两方面发展了Brucker，Foto等人的成果，一是工件具有了到达时间和分批加工的复杂状况，二是机器环境有单台机器变为同型机，并给出了它的一个PTAS算法。 一．基本概念及假设 基本概念 修正费用不超过1+O(ε)：在算法的设计中，要对实例作若干修正，以使实例具有更好的结构性质。若每次修正后，实例的目标函数值不超过原来的1+O(ε)倍，我们称修正费用不超过1+O(ε)。 PTAS算法：若算法列{A_ε}对于问题的任一个例子都是1+ε近似算法，计算次数是问题大小的多项式(将ε视为常数)，称它为PTAS算法。 基本假设h 曲阜师范大学硕士学位毕业论文 1．当工件被分批加工时，每一批的工时为该批中所有工件的加工时间的最大值，到达时间是其中的工件最晚的到达时间． 2．一批工件只能在一台机器上加工，而且开工以后不能被打断或转移到别的机器上，一直到该批被加工完．明显地，同一批工件的完工时间是相同的．二．PTAS算法． 下面将FOtO等［13］在单机排序问题1卜】Cj中给出的两个引理推广到同型机的分批排序问题 P叫rj；BI Cj中．这两个引理将原实例的加工时间和到达时间转化成具有较好性质的新实例，且费用不超过 1＋O＊）． 引理1 在修正费用不超过1＋。的情况下，可以将原实例的加工时间和到达时间修改为1＋。的整数次幂． 引理2 在修正费用不超过1＋。的情况下，可以对所有工件j的到达时间进行修正，使其满足 r。叁。Pj。 引理2表明我们可以假定没有工件在零时刻到达，且没有工件的加工时间超过？． 定义1若工件j相对于其到达时间的区间几有马＜。人；则称工件J为小工件，否则称为大工件。 设工件有L个至达日间，R工；，R工＊，…；R工＊．人1王＝12；…工表示在凡t时刻到达的工件集。下面，我们先讨论只有小工件存在时的情形． 将工件集人左分成批：丑，＊；Bi，l；…，凤力；；l＝16…；L．满足2 瞩 以＊卜B， i＝12，…？L·j＝1人·回·，k吐· 仰 P（B二，＊一l） 5 q（二，j），i＝ l，2；…，L·j二 1人…，k蓉·I’ L。。曲阜师范大学硕士学位毕业论文 ＊ 仰0＜旧 ＊I＜B，柱＝1百2，…量L．其中P（B；；＊表示批B；，。中最长工件的处理时间，q（B。，＊表示批Bt，。中最短工件的处理时间．B；，山 i＝1，2，…上为非满批． hi 引理3 对1S65人有二（＊凤j）一叭＊，＊叁＊人）＜。人·其中 J＝lP（人。）为工件集人；中的最大工件的加工时间。 由批 s。，。中最短工件复制旧。，。l（，而构成新的批凤。i＝fi；…，z．j＝l；2，…；k3，Bz，口中所有工件长度均取为零而构成批BZ，＊；l＝1；2，…，L．用P；表示x件 j新的加r时间，则有 川 旧乙D二＊1用口D＝旧 丞，＊】，d＝1】2，…，L．J二1；2，…，七 （＊ 八BJ二q凤＊）＝＊凤，人l＝1人一；L．J＝1；2；·巴·百＊． （3） P（B主0）二q ＊）＝ 0；i＝ l；2；…；L． 用I表示原分批排序实例，OPT厂）表示实例I的最优目标函数值， I；表示一个新的分批排序实例｛P7；r，，j二 1；2，…，。＊用 OPT（11）表示实例人的最优目标函数值． 对于u，BIZCj这一问题，我们假设批已经分好，不妨设为 BI，BZ；…，B。·则使目标函数二 Cj达到最小，也就相当于将批 B；看成一个工件，其达 ＆到时间为八B入 旧；I看成权时的一个凡卜j 二。；C问题．对于该问题 FOto i＝l等【13］在1999年给出了一计算时间为O（（m＋l厂p‘Je个＋n los…的PTAS算法（其中Pd）表示 Z的多项式），记为凡，该算法为一动态规划算法．其规划方程为 Ok＋二，F U）＝min（O（i，F’，V）＋W（i ＋1，厂’，F U—V））。 F’6F，V
黄敏镁[2]2007年在《具有柔性资源约束的优化调度问题研究》文中认为柔性资源客观地存在于企业经营运作的各个环节。产品开发和生产是制造型企业运营的两个关键环节，产品开发项目调度和车间调度问题是这两个关键环节中的核心问题。本文主要对具有柔性资源约束的产品开发项目调度和流水车间调度相关问题展开研究。具有柔性资源约束的调度问题比经典调度问题更为复杂，都是强NP-hard问题。解决问题的核心是模型和算法，有效的调度算法，可以大大提高资源的利用率和生产效益。因此，研究具有柔性资源约束的调度问题不仅具有较大的理论意义，而且具有相当高的实用价值。本文的研究以国内外已有的关于项目调度和车间调度等问题的最新研究成果为基础，采取系统建模方法、优化理论、人工智能和Matlab6.5编程与仿真等手段进行研究，提出问题的数学表示方法、构建有效的求解算法，得出有利于企业生产发展的参考性建议。本文主要围绕下述几个方面展开研究工作并取得了以下成果：(1)分析柔性的基本概念，给出了柔性资源的定义，并提出采用资源—能力矩阵对资源柔性分布进行表示的方法和资源柔性程度的度量方法。(2)讨论了经典资源约束项目调度问题和流水车间调度问题的基本理论和研究现状，通过对经典调度问题基本假设的分析，提出了突破这些假设的本文所要研究的3个主要问题：具有柔性资源约束的产品开发项目调度问题，具有柔性资源约束的流水车间调度问题和具有学习效应的柔性资源约束流水车间调度问题。(3)对具有柔性资源约束的产品开发项目调度问题进行深入研究：提出了具有柔性资源约束项目调度问题(FRCPSP)的数学表示方法；设计了问题求解的改进遗传算法，采用基于优先权的自然数编码方法，提出了采用拓扑排序和最大流理论相结合的解码方法，并设计了适用于该问题的遗传算子；通过计算机数据实验验证了算法求解问题的性能，说明了不同资源柔性程度和资源的技能分布对项目总工期的影响，指出合理的柔性资源调度方案对提高产品开发系统效率的作用。(4)对最小化调度时间表长为目标函数的具有柔性资源约束的流水车间调度(FRCFSS)问题进行了研究：阐述了问题的假设条件，建立了整数规划模型；分析了问题的强NP-hard特性；提出了有机结合启发式算法、遗传算法和禁忌搜索算法的问题求解的改进算法(MA)，该算法由3个模块构成，分别用于求解作业排序、柔性资源分配和工序开始时间3个子问题；大量的计算机数据实验说明该算法具有较好的鲁棒性和收敛性；通过比较经典流水车间调度问题和FRCFSS问题的求解结果，说明了对柔性资源合理调度，改进了流水车间的生产绩效。(5)对具有学习效应的柔性资源约束流水车间调度(FRCFSSLE)问题进行了探讨：对问题进行了描述，分析了问题的复杂性；提出了求解FRCFSSLE问题的启发式算法，该算法由作业排序和资源配置与开工时间计算2个模块组成；经过小规模数据实验和大规模数据实验说明了最优柔性资源配置的原则，证明了该启发式算法的有效性，并说明了考虑柔性资源的学习效应对流水车间进行优化调度可以更有效地利用柔性资源、提高车间的生产效率。
李修琳[3]2012年在《混流加工—装配生产调度集成优化研究》文中指出混流加工-装配生产系统是由加工生产车间和混流装配车间组成的混合生产系统。该系统以混流装配为核心组织生产,不同品种在装配线上同时进行混合装配,需要生产系统中同时配套提供更多品种的零部件,使生产过程中约束因素增多,子系统间的关联性增强。如何对各生产子系统进行有效的统一集成优化调度,成为生产系统优化的关键问题。论文以混流加工-装配生产系统为研究对象,通过建立混流加工-装配各级优化调度模型,并分别提出有效的调度算法,为混流加工-装配生产系统优化提供理论支持。论文主要研究工作如下:(1)作业加工生产调度算法研究。针对混流加工-装配生产系统中作业加工车间,研究以柔性作业车间调度为代表的作业加工车间调度问题,提出一种基于蜂群模型的混合群智能优化算法,并通过柔性作业车间标准算例和加工生产实例验证算法的有效性,为后续装配作业集成优化研究奠定基础;(2)混流装配生产排序算法研究。针对混流加工-装配生产系统中的单条混流装配线,研究以置换流水车间调度和混流装配线排序为代表的装配流水车间调度问题;提出一种改进人工蜂群优化算法,并通过流水车间调度问题标准算例和混流装配生产实例验证算法的有效性,为后续混流装配集成优化研究奠定基础;(3)混流装配关联排序集成优化研究。针对混流加工-装配生产系统中由多条混流装配线组成,具有串并行关联结构的混流装配车间进行集成优化研究;提出混流装配集成排序优化架构;以总装线消耗均衡化、生产系统完工周期最短、串行序列和并行序列差异度最小等优化目标建立混流装配关联生产集成排序模型;提出一种基于瓶颈的集成排序群智能优化算法;通过关联装配生产实例对提出的问题和算法进行分析和验证;(4)混流加工-装配分批调度集成优化研究。针对混流加工-装配生产系统中由作业加工车间和混流装配车间组成的关联生产结构,研究由柔性装配作业分批调度和混流装配排序问题组成的混流加工-装配分批调度集成优化问题,并提出分批调度集成优化架构;以混流装配线物料消耗均衡、生产过程总转运费用最小、缓冲区库存惩罚费用最小、作业车间完工成本费用最小和流程时间成本费用最小等优化目标建立分批调度集成优化模型;提出一种基于协同进化的蜂群智能优化算法;通过加工-装配生产实例对提出的问题和算法进行分析和验证。(5)总结全文的研究工作与成果,指出论文研究不足,并展望混流加工-装配生产调度集成优化的研究前景和下一步研究工作。
崔路军[4]2010年在《交货期确定条件下的准时制流水车间作业调度问题研究》文中研究说明现代供应链的发展,使企业间的联系越来越密切,小批量,多批次的生产模式以及对集送一体化的要求的提高,迫切需要新的流水线生产系统。因此,基于准时化生产技术的流水车间作业调度问题的研究也就有重要的意义,根据产品制造需求合理分配产品制造资源,进而达到合理利用产品制造资源、提高企业经济效益的目的。因此本文主要进行了以下几个方面的研究：(1)基于准时制生产的流水车间作业调度问题的概述。论文内容首先分别从车间调度问题的分类、车间调度问题的研究方法、流水车间作业调度问题的分类、流水车间作业调度问题现有的解决方法、单机条件下流水车间作业调度问题等方面对流水车间作业调度问题进行了阐述。其中单机条件下流水车间作业调度问题,构建了新的惩罚系数模型,并用模拟退火算法解决了该类问题。(2)本文第叁章的内容研究了准时制条件下交货期确定的流水车间作业调度问题,该问题不含有并行机。论文研究由简单到复杂,第一节先研究了产品品种单一模式下的流水车间作业调度问题,提出了一种基于启发式的关键工序算法,较好的解决了该问题。第二节研究了可生产多品种产品的流水车间作业调度问题,解决该问题,论文首次提出利用动态规划思想来解决准时制条件下的流水车间作业调度问题,解决该问题的思路是以启发式的关键工序算法为基础,把准时制条件下的流水车间作业调度问题转化成网络图,然后利用数学规划的方法求出该网络图的最长路。从本文所列举算例可以看出,数学规划方法很好的解决了该问题。(3)对于准时制下混合流水车间调度问题。论文的第四章寻求了一种混合算法。该方法的思想是先利用关键工序启发式算法求得一个优化解,然后结合传统的模拟退火算法对问题模型进行求解,该算法克服了模拟退火算法收敛速度慢的缺点,更具有柔性,能解决传统流水车间与其他生产限制下流水车间的模型。为企业减少物流、存储费用提供了一种简单可行的解决办法。
黎展滔[5]2012年在《具有成组约束的柔性流水车间作业计划制定的启发式算法》文中认为具有成组约束的柔性流水车间调度问题普遍存在于离散制造业,对其进行研究具有重要理论意义和工程实用价值,因此吸引着越来越多研究人员对其进行研究。具有成组约束的柔性流水车间调度问题是传统调度问题的一种扩展,根据出现成组位置的不同可分为叁类子问题：前、中、后成组约束的柔性流水车间调度问题。该类问题是柔性流水车间调度问题和成组问题相结合的混合车间调度问题,因此属于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.开发了一套《基于成组约束的柔性流水车间调度问题的仿真平台》,通过该平台可以方便地产生不同问题的仿真实例,以及配置不同算法参数下得到每个算法的仿真结果,从而对相关调度算法的性能进行分析和比较。最后,基于上述步骤所获得的理论研究成果,并结合合作企业的实际运作特点,设计和开发了车间调度系统并成功应用在企业中。
刘锋[6]2014年在《生产调度干扰管理模型和算法研究》文中指出生产调度问题作为经典组合优化问题,具有高度的计算复杂性和广阔的应用前景。经典生产调度问题假设加工环境稳定,初始最优加工时间表制定后可以顺利执行。然而现实生产过程中充满不确定性,机器维护、机器故障、工件优先级变化和新工件到达等事件单独或者组合发生,使得初始计划无法按计划执行。这些事件统称为干扰事件,在干扰事件发生后,如何以尽量小的代价恢复加工系统正常运行是干扰管理(Disruption Management)致力于解决的问题。对应于加工系统基本构成要素,干扰事件可以大致分为资源相关和任务相关,对初始计划造成不同的影响。针对不同类型干扰事件,准确量化干扰事件的扰动,基于此构建同时考虑初始优化目标和扰动目标的模型,并设计高效算法求得问题有效解集供决策者选择,是生产调度干扰管理问题的核心和难点问题。本论文的主要研究内容包括：(1)资源相关扰动的干扰管理研究。选择资源相关扰动中最具代表性的机器维护作为研究对象：在单机环境中针对机器维护,研究初始最优加工时间表是基于加权折扣最短加工时间优先规则的问题,使用相对于初始计划工件完工时间的延迟来度量扰动,建立同时考虑原目标和与扰动目标的模型,结合量子算法和非支配排序遗传算法优势设计混合算法进行模型的求解。在并行机环境中面对干扰事件为改变加工效率的机器维护,使用机器-工件重新分配来度量扰动,构建干扰管理模型。设计求解问题有效前沿的穷举算法,以及在此基础上更高效率地优化某特定指标函数的分支定界算法。(2)任务相关扰动的干扰管理研究。选择工件相关干扰事件中最具代表性的工件优先级变化和新工件到达作为研究对象：针对单机环境下存在安装时间的最优化工作流时间问题,研究工件优先级突发提高的应对,设计最近邻域和插入混合算法为非支配排序遗传算法提供较优初始解,最终求得高质量有效前沿。针对单机环境下工件加工时间可通过非线性资源消耗进行压缩的问题,研究单个新工件到达和处理依概率发生时的应对,基于工件吸收干扰影响的能力制定初始加工时间表,使得干扰发生后新时间表能尽快和初始计划完全匹配。针对单机环境下计划外多个新工件抵达,研究通过外包手段为加工服务承接商制定生产配送的集成优化方案,在运营成本和服务水平之间进行有效权衡。(3)资源相关扰动和任务相关扰动并发的干扰管理研究。以上述内容为基础,研究了机器维护和新工件达到同时发生时的干扰管理问题。将客户对于完工时间延迟的非对称感知考虑在扰动度量中,从而使新的解决方案更具现实意义。提出一种基于有效解的元启发式算法,其中部分初始种群是通过动态规划方式求得。为了检验该方法的性能,设计了计算机仿真实验,比较了重调度干扰策略和局部修复策略,分析了不同启发式算法和分派规则的性能。通过对数值仿真结果进行统计分析,并根据现有度量有效前沿质量指标进行计算,验证了重调度策略和设计方法的有效性。本研究属于排序理论、运筹学优化理论和智能优化算法的交叉渗透,对生产调度干扰管理这一难题进行了有益探索。为加工制造企业面对突发干扰事件在生产成本和系统扰动之间权衡决策提供理论支持,对企业提高服务质量具有重要现实意义,对丰富拓展生产排序理论和多目标智能优化算法研究领域具有重要理论意义。
裴明丽[7]2018年在《蚁群优化算法在带有拒绝的多目标批调度问题中的应用研究》文中指出调度问题是一类极其特别且多元化的组合优化问题,广泛应用于生活中的各个方面,如物流、加工制造业等。研究调度问题的主要目的是合理分配有限的资源,使得资源在分配过程中井井有条,提高生产效率,为企业带来更多的利益。然而随着生产规模的不断扩大,调度问题变得越来越复杂,为了改善企业的经营状况,出现了一种新型的调度问题——批处理机调度,简称批调度。批调度问题与传统的经典调度问题主要区别是在同一时刻上,多个工件可以被同一台机器同时加工,即多个工件以批的形式在机器上加工,其加工时间等于批中所有工件的最大加工时间。由于受工件属性、机器属性以及目标函数的影响,使得批调度的问题是非常复杂的,即使在单机环境下,也被证明为是一类NP难问题。为了解决这样的难题,很多国内外的专家和学者开始寻找效率更高的求解方法。另外,企业为了减少生产时间,必须拒绝加工某些工件,因此需要付出一定的代价,即产生了拒绝成本,本文的研究目标是最小化制造跨度和总的拒绝成本。首先,介绍了批调度问题的研究背景,描述了叁参数表示法中的相关内容,再介绍了批调度问题的研究现状,包括单机、多机以及考虑拒绝成本的批调度问题。第二,介绍了求解批调度问题的叁大类算法,分别是确定性算法,启发式算法与元启发式算法。第叁,基于蚁群优化(ACO)算法,提出了 LACO与PACO两种算法分别解决线性组合和基于Pareto的非支配解两个多目标优化问题。另外,详细介绍了LACO算法与PACO的共同部分,如双信息素矩阵的定义,双启发式信息的定义等,也介绍了其不同部分。第四,描述了实验中参数的设置,测试实例的生成,然后统计实验数据,并将本文提出的算法得到的实验结果与其它对比算法进行比较和分析,进而得出相关结论。最后,总结本文的研究内容,并进行展望。
宫华[8]2008年在《钢铁企业一类考虑恶化和运输的新型生产调度问题的理论研究》文中提出钢铁工业是国民经济的重要支柱产业之一。近年来,随着建筑业、汽车制造业、造船业和家电业的大力发展,对钢材的需求数量和质量提出了更高的要求。由于钢铁生产具有多阶段、物件带有高温连续运作、物流呈交叉网状结构等特点,这就决定了物件在工序上的生产调度、连接工序之间的运输物流调度以及生产和物流调度的衔接都有严格的要求。合理进行生产和物流调度,有利于钢铁工业工序之间的物料紧凑衔接、减少中间等待时间,从而降低能耗、提高大型装置的设备利用率,达到降低生产和物流的综合成本、提高产品质量、提高钢铁工业竞争力的目的。本文以钢铁企业的高能耗的炼钢和初轧为背景,分别从这两个工序中提炼出具有热链物流特征的生产和运输调度问题,进行理论研究。基于复杂性分析、算法最坏情况分析、多项式时间算法、近似策略、动态规划等多种技术手段,主要研究叁个方面的问题：具有恶化特征的生产调度问题、生产和运输协调调度问题、考虑恶化特征的生产运输协调调度问题。具体内容概括如下：1)具有恶化特征的生产调度问题研究(1)从钢锭在均热炉中加热的过程中提炼出工件带有释放时间和恶化特征的批处理机调度问题,其中工件在批处理机上的加工时间是工件在批处理机前的等待时间的一个分段函数,目标函数为最大完成时间的最小化。证明了该问题是NP-难问题。分别从相同的释放时间、批处理机能力无限以及工件具有优先次序叁个方面,研究了叁种特殊情况的多项式时间算法。(2)从模铸到均热的生产过程提炼出了并行机和批处理机两阶段生产的恶化调度问题,其中工件的恶化是指工件在批处理机上的加工时间与工件在两阶段之间的等待时间有关。目标函数既考虑了两阶段生产的机器利用率,又考虑了批处理机的空载惩罚,即为最大完成时间和批处理机空余的惩罚费用之和的最小化。对于这个问题,证明了强NP-难性,提出了一个启发式算法,理论上分析了算法的最坏情况性能,并通过数值仿真实验,验证了算法性能的有效性。2)生产和运输协调调度问题研究(1)从钢锭的运输以及均热的过程受到启发,提炼出了多个台车生产前运输与批处理机生产的协调调度问题。目标函数为工件总完成时间与批处理机启动费用之和的最小化。首先利用划分问题证明了该问题是NP-难的,通过动态规划提出的伪多项式时间算法证明了该问题是一般意义NP-难问题。最后提出了解决问题的全多项式时间近似策略。而当工件在台车上的分配给定时,通过动态规划给出了多项式时间的最优算法。(2)从模铸到均热的生产和运输中提炼出了二机之间带有运输考虑的二机流水调度问题,其中在运输的过程中考虑工件是否占有不同的物理空间两种情况。目标函数为最大完成时间的最小化。对于工件体积相同的情况,给出了最坏情况性能比为2的启发式算法。对于工件体积不相同的情况,给出了最坏情况性能比为7/3的启发式算法。(3)从均热到初轧的生产过程提炼出了带有阻滞和运输时间考虑的两阶段生产调度问题,工件先在第一阶段批处理机上进行生产,当第二阶段的单机有空闲时才可以运输到第二阶段进行生产,如果单机不可利用,则批处理机上形成了阻滞。目标函数既考虑了工件的最大完成时间,又考虑了工件在批处理机上的总阻滞时间。对于总的阻滞时间的最小化问题,给出了多项式时间的最优算法。对于最大完成时间最小化问题,给出了强NP-难的证明,提出最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于最大完成时间和总阻滞时间的线性组合最小化问题,提出了混合整数规划模型,给出了强NP-难的证明,提出了启发式算法,并且从理论分析与实验结果两个方面验证了算法的有效性。(4)从初轧生产到成品运输的过程提炼出了并行机生产与成品运输的协调调度问题。目标函数为工件总完成时间与运输费用之和的最小化。根据问题所满足的性质,通过过程划分及动态规划给出了解决问题的伪多项式时间算法,并且证明该问题是一般意义NP-难问题。对于工件在并行机上的分配给定的特殊情况,提出了多项式时间的最优算法。(5)从钢锭在均热炉加热的前后生产过程提炼出了批处理机上生产与生产前后两阶段运输的协调调度问题。目标函数为工件的最大完成时间与批处理机启动费用之和的最小化。提出了问题的混合整数规划模型,给出了强NP-难证明。并且提出了最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于工件的加工次序确定的情况,给出了多项式时间的最优算法。3)考虑恶化特征的生产运输协调调度问题研究从均热车间中提炼出了工件生产前的运输以及批处理机生产的协调调度问题,其中也考虑了工件在批处理机的生产的恶化特征,这里的恶化是指工件在批处理机上的加工时间是关于工件的暴露时间的分段函数。目标函数为最大完成时间和批处理机的启动费用之和的最小化。证明了问题的一般情况以及批的数量受限的情况都是强NP-难问题,给出了启发式算法,并且进行了最坏情况性能比分析,实验结果也验证的算法的有效性。对于工件的完成时间受限的情况,证明了该问题也是强NP-难问题。对于工件的加工顺序给定的情况,给出了多项式时间最优算法。
周盛超[9]2016年在《差异工件机器批调度若干问题研究》文中认为不同于传统加工机器,批处理机器一次能够加工一批多个工件(或作业)。批处理机在生产企业中具有广泛的应用,包括电子芯片厂、钢铁企业、航空工业等。合理地调度批处理机的加工任务,能够有效地提高企业的生产效率,降低生产成本。因此,研究批处理机调度(简称批调度)问题不但具有重要的理论价值,还具有迫切的现实意义。不同尺寸的工件(简称差异工件)是一个常见于制造车间的现实约束。而早期的研究大都假设上件具有相同的尺寸(即单位尺寸)。本论文研究不同尺-寸工件机器批调度问题。相比相同尺寸的情形,本文问题是更一般也更为复杂的调度问题,它兼具排序问题和装箱问题的双重性质。本文的主要研究上作和创新点如下：(1)研究了工件具有不同尺寸和任意到达时间的单机批调度问题。问题的目标函数为最小化制造跨度。该问题属于NP-hard问题。首先,我们提出了本问题的两个下界,并证明了下界的有效性。其次,我们从一种新的角度提出了若干种启发式构造型算法。在制定分批的决策中,工件的加工时间和到达时间常常是两个相互矛盾的因素。这也正是研究本问题的一个难点。因此,现有的算法在分批过程中往往只考虑了某一个因素的影响。然而,我们提出的算法在分批时试图兼顾加工时间和到达时间两个因素的作用。第一,我们提出了距离矩阵的概念：第二,我们设计了若干种基于距离矩阵的构造型算法,用于将工件分批；然后,我们采用已有的批排序算法ERT规则,用于安排批在机器上的加工。大量的仿真实验比较了我们的算法和现有的求解方法。实验结果证明了本文下界以及启发式算法的有效性。(2)研究了一类两阶段流水车间批调度问题,考虑不同的工件尺寸、任意到达时间、以及阻塞约束。优化目标为最小化制造跨度。首先,我们对这一问题建立了混合整数规划模型。然后,提出了一种混合的离散差分进化算法。在提出的算法中,个体采用离散的工件序列编码。然后,基于该编码方式,设计新颖的变异和交叉算子。接着,我们使用first-fit规则将工件分批；并提出一种新的最小闲置/阻塞时间算法,用来安排批在车间里的加工次序。为了进一步改进求解质量,一种局部搜索算法被集成到差分进化算法当中。仿真实验证实了所提出算法在解质量、鲁棒性以及计算时间方面的优异性。(3)考察了差异工件两类批处理机的流水车间调度问题。两阶段各包含一台批处理机。第一台机器为并行批处理机,第二台为串行批处理机。优化口标为最小化制造跨度。我们对该问题建立了混合整数规划模型。然后,我们提出了一种基于种群的进化算法-分布估计算法。在该分布估计算法中,个体被编码成工件序列。接着,构造一种概率模型以抽样产生新个体,并提出一种增量学习型方法以更新概率模型。我们采用best-fit规则对工件分批,并提出一种最小闲置/等待时间算法,以排列批的加工次序。为了进一步改进算法的求解质量,两种局部搜索算法被嵌入到该分布估计算法当中。计算机实验表明了该分布估计算法在解质量与鲁棒性方面的有效性。
张立萍[10]2013年在《面向节能的流水车间调度建模与优化》文中研究指明随着能源日益衰竭,能源问题对于社会发展的制约日益凸显。企业直接能耗与间接能耗是制约其发展的核心竞争力之一。而车间生产能耗占企业用能的大部分,为此研究和解决车间生产节能问题是提高能源利用率与提升企业效益的核心问题之一。因此,本文深入分析了流水车间生产节能问题的研究现状,分别研究面向节能的加工装配流水车间调度问题、并行机流水车间调度问题和单机批处理流水车间调度问题,针对不同问题建立对应的节能调度模型,利用混合差分算法求解出最低能耗下的节能调度方案。论文主要研究内容如下：(1)阐述了课题的研究背景和意义。综述流水车间生产调度问题的研究现状,特别是面向节能的流水车间生产调度问题,分析和总结了改进差分进化算法在生产调度领域研究和应用。并给出研究问题及采用的方法,建立本文各章节的内容安排。(2)研究车间生产能耗统计方法。分析影响生产车间能耗的因素,依据车间生产工作状态的能耗进行分类,构建各部分能耗统计模型,并集成给出车间生产系统能耗统计模型。该能耗统计模型的研究是为具体流水车间节能调度模型提供理论参考。(3)研究加工装配流水车间中的节能调度问题。以车间能耗统计模型为基础,结合加工装配流水车间具体调度问题,建立以机器加工能耗、空载能耗、开关机能耗之和最小为优化目标,以加工装配作业的装配约束、工艺约束、资源约束等为约束条件的流水车间节能调度数学模型。以小家电生产车间和转向器生产车间的调度问题为例,采用混合差分进化算法求解最优能耗下车间生产节能调度方案。(4)研究并行机流水车间节能调度问题。以车间能耗统计模型为基础,分析并行机流水车间中资源分配问题,建立以机器能耗最小化为优化指标,以并行机调度作业中工艺约束、资源约束等为约束条件的节能调度模型。以发动机厂金加工车间为例,采用混合差分进化算法求解该车间某零件生产过程中最佳节能调度方案。(5)研究单机批处理流水车间节能调度问题。采用先划分批量再求解最低能耗下调度方案原理,建立以车间中机器加工、空载和开关机能耗之和为优化目标,以子批量的划分与处理机流水调度问题中存在的机器约束、工艺约束等为约束条件的节能调度数学模型。以工厂流水加工车间生产为例,采用混合差分算法求解出最优节能调度方案。
参考文献：
[1]. 两种新型排序问题的近似算法[D]. 任建锋. 曲阜师范大学. 2003
[2]. 具有柔性资源约束的优化调度问题研究[D]. 黄敏镁. 武汉理工大学. 2007
[3]. 混流加工—装配生产调度集成优化研究[D]. 李修琳. 浙江工业大学. 2012
[4]. 交货期确定条件下的准时制流水车间作业调度问题研究[D]. 崔路军. 青岛大学. 2010
[5]. 具有成组约束的柔性流水车间作业计划制定的启发式算法[D]. 黎展滔. 广东工业大学. 2012
[6]. 生产调度干扰管理模型和算法研究[D]. 刘锋. 大连理工大学. 2014
[7]. 蚁群优化算法在带有拒绝的多目标批调度问题中的应用研究[D]. 裴明丽. 安徽大学. 2018
[8]. 钢铁企业一类考虑恶化和运输的新型生产调度问题的理论研究[D]. 宫华. 东北大学. 2008
[9]. 差异工件机器批调度若干问题研究[D]. 周盛超. 中国科学技术大学. 2016
[10]. 面向节能的流水车间调度建模与优化[D]. 张立萍. 浙江工业大学. 2013