英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
具有灰色区间处理时间的柔性作业车间调度问题
摘要：在一个生产系统中，工作处理时间并不总是准确地作为一个时间定额给出，特别是在复杂的产品制造过程中。研究基于不确定性处理时间的新模型和算法，对解决不确定性车间调度问题具有重要意义。本文将不准确的时间定额定义为灰色区间处理时间，并以此为目标，提出了一种新的不确定性作业车间调度模型。通过定义灰色区间处理时间的算术运算和甘特图，设计了外存储器中的精英遗传算法耦合的精英策略。最后，将所提出的算法与不同规模的复合构件车间调度方案进行了比较。结果表明，该算法适用于求解具有灰色区间处理时间的不确定性车间调度问题。
关键词：车间调度、灰色区间处理时间、遗传算法、灰色系统理论
1.引言
由于生产更新速度和多样化的要求越来越高，在生产系统中，作业处理时间往往不能准确地作为一个时间定额给出，即作业处理时间往往是以下限和上限来估计的，而不是一个精确的数字。特别是在复杂的产品制造过程中，如火箭、飞机、复杂机械等的制造调度问题需要进一步研究[1]。在复杂产品制造车间的计划管理中，最困难的问题是作业处理时间的不确定，因此，传统的调度模型是无效的[2]。研究具有不确定性信息的调度模型，对提高生产效率和管理水平具有明显的参考价值。
复杂产品的车间调度问题是Bruker和Schliein于1990年提出的一个柔性作业车间调度问题（FJSP）[3]。经典作业车间调度问题（JSP）的推广是一个NP难题[4]。近年来，人们采用了许多启发式和元启发式算法来解决FSJP问题，如禁忌搜索算法[5]、模拟退火算法[6]、遗传算法[7]、粒子群优化[8]、蚁群优化[9]、和声检索[10]、人工蜂群[11]、人工免疫算法[12]、帝国主义竞争算法[13]等，尤其是遗传算法在这一领域得到了广泛的关注和发展[14]。J. Gao研究了关于带瓶颈转移的遗传算法的FJSP问题[15]。] G. Zhang等人设计了全局选择（GS）和局部选择以生成高质量初始人口[16]。2012年，一种具有有效选择、交叉和变异操作的改进的遗传算法被提出[17]。Mokhtari应用遗传算法解决了节能多目标的FJSP问题[18]。而Cinar在2017年提出了一种基于优先级遗传算法的FJSP问题[19]。
与传统的FJSP不同，处理时间不是精确的数值，而总是不确定的。作为FJSP问题的无限延伸，不确定的处理时间、到期日等主要由模糊数来表示[20]。D. Lei研究了模糊FJSP问题的分解集成和协同进化遗传算法[21]。考虑到模糊处理时间，徐在2015年设计了一种有效的基于教学的最优化算法[22]。K.Z. Gao提出了一种改进的人工蜂群算法，并设计了相应的模糊甘特图[23]。2017年，Palacios将不确定的任务持续时间建立为一个模糊数，并研究了一种混合算法，使模糊完工时间最小化并最大化稳健性[24]。
事实上，由于许多新产品、复杂产品的开发件，我们只能通过员工经验或历史生产数据中的贫信息来估计处理时间的大致范围，而不能准确地分配加工时间。因此，模糊理论中模糊处理时间的隶属函数是难以定义的。与模糊理论不同，邓聚龙提出的灰色系统理论（GST）[25]主要基于灰数来进行系统分析、决策和优化[26]。例如，在生产管理中，Y. Liu在灰色信息下研究了关键设备的生产缓冲[27]。Y. Liu将灰色理论的灰色关联模型应用于制造任务的分配问题，并提供了一个案例研究[28]。Y.D. Fang通过深入分析和灰色关联分析解决了多目标条件下加工设备的预选问题[29]。不可否认，灰数具有确定的信息边界和不确定的内在规律的特点[30]。灰数被定义为真实值未知，而可能值的集合可以被定义的数。它非常适合估计制造任务的处理时间。特别地，可能集合的下限和上限可以被定义，即处理时间被定义为区间灰数。
然而，针对车间调度中的灰数特征的研究却很少。2006年，B. Li试图用灰数表示流水车间调度中的不确定时间参数，并采用灰色机会约束规划解决了不确定情况下的流水车间调度问题[31]。但在模拟和计算过程中，通过净重函数将灰数转化为一个确定值。没有基于灰数信息背景的直接算法[32]对其信息特征进行有效的保存，以致于最终的甘特图无法明确地表示灰数信息和实际意义。因此，基于以往的研究和实际生产背景，本文将区间灰色处理时间与柔性作业车间调度问题相结合，设计了一种遗传算法来解决灰色信息下的调度问题。
本文的组织结构如下：第2节定义了具有区间灰色处理时间的柔性作业车间调度问题，并对其进行了建模。区间灰色处理时间和灰色甘特图的操作见第3节。第4节提出了一种基于外存储器的精英策略遗传算法。第5节设计了不同尺寸的复合材料零件车间调度方案，对所提出的算法进行了测试。最后，第5节总结了本文。
2.具有区间灰色处理时间的柔性作业车间调度
一项工作应该在许多操作中完成，不同的操作可以由不同的工作单元（机器、单个工人、工作组）执行。操作可以由候选工作单元集中的至少一个可选工作单元处理。具体来说，操作处理时间不能精确定义，但可以收集为一个区间灰数。因此，应将区间灰色处理时间与柔性作业车间调度问题相结合，解决不确定性环境下的车间调度问题。本文进一步定义了具有灰色处理时间的柔性作业车间调度问题（G-FJSP）模型。与传统的FJSP模型相似，G-FJSP模型假设：
（1）每个工作都没有优先级，即所有工作都同等重要。
（2）每个工作单元可以从零开始执行任务，此时没有任务。由于机器不停或工人倒班制度，每个工作单位可视为没有休息时间。
（3）操作一旦启动，就不能中断。
根据这些假设和传统FJSP模型的定义，G-FJSP模型的符号可以进一步定义为：
表示待调度的n个作业集合。
表示所有m个候选工作单元的集合。
表示为作业的操作之一，其中。
表示为是的一组候选工作单元。
表示为在上的灰色处理时间间隔。它可以显示为一个区间灰数，其中, 区间灰数表示可能的处理时间在区间值集合中，即从到。
表示为的区间灰色处理开始时间。同样，它可以被定义为。
表示为的区间灰色处理结束时间。因此，表示为的完成时间，并且。
表示为 和之间的灰色间隔时间，并且。特别是。
表示所有作业的最大灰色完成时间，。
是一个极大的正数。
为了在一段时间内尽可能多地完成工作，作业车间调度主要关注的是所有工作的完成时间，而不是总的工作单元工作量、工作交付时间、每个工作单元工作量、在制品库库存等，因此，该问题的主要目标是使所有工作的最大完工时间最小化。因此，可以建立如下的数学模型。
公式（1.1）和（1.2）表示每个作业的顺序约束：流程的结束时间不能早于开始时间，下一个流程的开始时间不能早于上一个流程的结束时间。在公式（1.3）中，的结束时间早于的开始时间，如果在工作单元上的之前被处理，则表示工作单元在同一时间只能执行一项任务。公式（1.4）表示同一操作只能由一个工作单元同时处理，公式（1.5）表示每个作业的开始时间不是负数，可以从零开始。
基于区间灰色处理时间的定义，如果每个作业的工作时间都可以缩写为一个实数，那么模型I可以转换为模型II，即传统的FJSP模型。也就是说，FJSP模型是G-FJSP模型的特例，而G-FJSP模型是对具有灰色间隔处理时间的FJSP模型的扩展。
3.灰色处理时间操作的定义
在调度计算中，加法运算和排序运算是区间灰数最重要的两个运算。灰数算法更关注信息背景的运算。假设两个区间灰数和具有对应的覆盖值集合和。加法、标量乘法和排序操作分别定义如下：
（1）加法运算[32]
如果，则区间灰数的覆盖值集合为：
（2）标量乘法运算[32]
如果，k是一个标量，则区间灰数的覆盖值集合为：
特别是，如果，。如果，
（3）排名操作[33]
让表示情况的概率度，根据，，，之间的不同关系，可以详细描述为：
在本文中，为了使所有作业的最大完成时间最小化，最大完成时间的信息背景尽可能小。因此，如果或者且，则定义；如果且，则定义，否则。
4.用区间灰色处理时间表示甘特图
车间复杂产品作业的区间灰色处理时间见表1。在表的每一行中，作业的每个操作都有其可选的工作单元（“-”表示无可选）。例如，表1中作业1的第一个操作有三个可选工作单元，第二个工作单元不能由执行。并给出了在所有可选工作单元下工作单元的灰色处理时间对应的灰色信息背景。上的的灰色处理时间为，表示信息范围为6～8。此外，在每个操作行中记录一次操作与其上一次操作之间的灰色间隔处理时间。在作业的第一个操作行中，间隔时间为0，而在其他行中，间隔时间是一个灰色数字，表示为与间隔灰色处理时间相同的形式。例如，和之间的间隔时间是。
基于灰色处理时间表，所有操作都可以安排在一个可选的工作单元上。图1显示了在确定操作顺序后，具有灰色处理时间的甘特图（定义为灰色甘特图）。在灰色甘特图中，每个工作单元都有自己的处理时间线来表示处理顺序。作业的每个操作都安排在要处理的工作单元处理时间线上。其灰色加工开始时间以时间线上方的弧形曲线表示，灰色加工结束时间以下面的曲线表示。时间线以上的弧形曲线的起点表示在相应的工作单元上操作的可能最早开始时间，终点表示可能的最晚开始时间。相对而言，时间线以下的弧形曲线的起点和终点表示操作可能的最早结束时间和可能的最晚结束时间。例如，作业4的第二次作业计划由作业单元3从生产到。所有作业的最大完成时间为。
5.G-FJSP的遗传算法
遗传算法（GA）是一种基于优胜劣汰理论的经典搜索技术。根据Chaudhry和Khan的研究调查，自1990年以来，GA一直是解决FJSP的最流行技术[34]。大量的研究表明，该方法在车间调度问题中的适用性，以及在具有良好的完工时间和稳定性的发电计划中的性能[35]。例如，G.H. Zhang提出了一种多目标FJSP问题的混合遗传算法，并对其性能进行了评估[36]。特别是在优化过程中，采用外存储器的方法，通过保存和更新更好的解来提高了遗传算法的效率，实验证明该方法在他的研究中是有效的。基于外存储器的基本思想，本文提出了一种基于外存储器的遗传算法（EGA）来实现G-FJSP。
5.1 精英主义遗传算法
如图2所示，所提出的EGA的工作流程主要包括编码算子、解码算子、选择算子、交叉算子和变异算子，下文将进一步说明。
EGA的整体流程描述如下：
步骤1：初始化：通过编码操作符随机生成第一代。设gen为当前一代（初始时gen=1），PopSize是每一代的人口规模。
步骤2：评估：评估当前人群中的每个个体，并计算出相应的适应值。本文中的适应值是所有作业的最大完成时间。
步骤3：确定是否满足终止条件。如果是，转到步骤8，否则，转到步骤4。
步骤4：选择：通过选择操作符选择交叉总体的所有亲代。
步骤5：交叉：对每对亲代执行交叉运算符，并生成两个子代。
步骤6：突变：对每对子代执行突变操作，产生新的群体。
步骤7：从新填充更新外部内存。转到步骤2。
步骤8：输出计划。
为了提高算法的效率，提出了一种基于最大代数和收敛状态的终止准则。EGA程序步骤3中的终止条件是达到最大生成（记为MaxGen）或达到收敛状态。MaxGen是控制EGA最大生成的设定值。收敛状态是种群的最小值和5%的适应度均值在之后几代中保持不变。本文将几代数定义为StableGen，相当于MaxGen的20%。5%修剪平均值，其中最左（最低）5%和最右（最高）5%的适应度值被排除在外，其优势是对异常值具有相对的抵抗力。
5.2 EGA算子
（1）编解码算子
染色体是遗传算法中信息传递和迭代进化的基础。G-FJSP的任何可行解都可以通过编码算子和解码算子与染色体相关联。本文采用了由工作串和工作单元串组成的染色体表示方法。作业字符串显示所有作业的产品处理顺序，工作单元字符串显示相应的处理工作单元选择。在图3中，以表1中的作业数据为例，给出了EGA的编码算子（步骤1、2）和解码算子（步骤3、4）的方法：
步骤1：生成新的作业字符串。如图3所示，初始作业字符串是根据所有作业编号生成的，每个作业编号都出现次，是的操作数量。然后通过随机打乱初始作业字符串得到新的作业字符串。在新作业字符串中，作业的每个操作都由相同作业编号的出现顺序唯一确定。例如，新作业字符串中的第一个基因“2”表示的第一个操
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[20057]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、外文翻译、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
