英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
一种针对具有柔性路径和机器共享的多单元调度的三层染色体遗传算法
Yangling Feng，Guo Li，Suresh P.Sethi
摘 要：在现代动态单元制造系统 (CMS) 中，可供选择的机器分配、机器共享和单元间运动是非常普遍而又难以集成解决的问题。在本文中，我们结合这些问题，并考虑一个具有柔性路径和机器共享的动态单元调度问题。我们使用混合整数规划模型来最小化最大极值点和总工作负荷。为了求解这个模型，我们提出了一种三层的染色体遗传算法(TCGA)。我们首先比较提出的TCGA与CPLEX 最优解的性能。计算结果表明，TCGA在合理的时间内表现良好。我们进一步通过数值实验比较了我们提出的TCGA与经典遗传算法(GA)和最短加工时间(SPT) 规则。结果揭示 TCGA 显著提高了求解性能，并有效平衡了机器的工作负荷。
关键词：动态单元制造；单元间移动；双目标规划；三层染色体遗传算法；机器共享；
1.引言
在过去 20 年中，制造商见证了产品品种的增加和产品生命周期的缩短。为应对激烈的市场竞争和定制化需求，单元制造系统 （CMS）逐渐实施，并引起了学术界和从业者的更多关注。作为即时制造、精益制造和成组技术的组合应用，单元制造具有几个优势，例如减少运输和准备时间、缩短提前期和更好地运作控制（Houshyar 等人，2014）。因此，CMS是多品种小批量生产最有效的生产方式之一。
单元生产已在实际中得到广泛应用于具有多品种的小型到中型批次流水车间的生产中(Dawande等,2007)。该生产模式已在文献中从多个方面进行了研究，包括 CMS 设计 (Won and Logendran,2014；Chattopadhyay等,2013)、设施布局 (Helber等,2016；Gonfialves and Resende,2015；Saraswat等,2015) 和单元调度和控制 (Li等,2013,2017；Wang等,2016；Delgoshaei等,2017)。我们的研究属于单元调度问题，我们进一步将其分为两个主流：(1)流水作业单元调度，其中所有工序必须通过相同顺序的机器进行加工；(2) 作业车间单元调度，其中工序以不同的顺序访问机器。由于本文主要研究的是 job shop 的单元调度问题，因此我们聚焦于研究这个问题的文献。Yan等(2015)提出了一种交替迭代遗传算法，以集成混合批次作业车间的生产计划和调度。Kuhpfahl 和 Bierwirth (2016) 采用一般方法来建立车间调度问题的模型，以最小化总加权延误。在实际的单元调度问题中，单元间移动是很常见的。然而，很少有研究考虑到了这一点。例如，Halat 和 Bashirzadeh (2015) 提出了一种基于遗传算法的启发式算法，用于考虑单元间运输时间的制造单元调度。Solimanpur 等人 (2004) 提出了一种SVS启发式算法来求解具有单元间移动的单元调度问题，并将其性能与LN-PT方法进行了比较。
尽管前面提到的一些研究在他们的模型中包括了单元间的运动，但是他们假设这种运动是已知、固定的。实际上，跨单元路径通常是柔性的，因为在单元系统中不止一台机器是可选的（Li等,2013）。因此，工序可以由可选的机器处理，并在制造单元中形成柔性路径。然而，只有很少的研究调查了这种趋势。例如，Eguia等(2017)研究了存在可选路径和多个时间段的可重构CMS。Tang等(2016)解决了一个柔性多单元工件调度问题，并设计了一个基于拍卖理论的方法来最小化完工时间。
上述关于柔性路径的文献假定每台机器都属于某一个单元，但实际上，每个工件完全只在单个单元内完成加工是几乎不可能的。因为通过购买额外的机器来实现单元独立可能并不经济。CMS中的机器可能会重叠，因为它可以属于多个单元以实现资源的充分利用（Khilwani等，2011）。这种做法被称为机器共享，在高负荷条件下特别有价值，可以显著减少瓶颈机器的重复，提高机器利用率（Wemmerlov 和 Hyer，1989）。例如，在半导体制造中，许多昂贵的高性能关键设备在不同的单元之间共享，以最小化重复机器的数量，并避免使用已达到其最大生产负荷的机器。然而，文献中对机器共享的单元制造调度研究还不足。因此，我们考虑了具有柔性路径和机器共享的跨单元调度问题。据我们所知，本文是第一个同时考虑柔性路径和机器共享的单元调度问题的。
众所周知，经典的job shop调度问题(JSP)是NP难题（Lawler等人，1993；Al-Anzi等人，2006；Yuan等人，2013）。由于JSP是柔性作业车间调度问题 (FJSP) 的一个特例，我们研究的FJSP也是NP难题。针对大型调度问题的求解困难，为获得近似解，多种元启发式算法被提出。例如，模拟退火算法(Kaplanoglu，2016)、遗传算法（Guo等，2008）、和声搜索（Li等，2015）、禁忌搜索（Solimanpur和Elmi，2013）、细菌觅食优化算法（Nouri，2016；Liu等，2016a）和蚁群优化算法（Delgoshaei等，2016；Rossi，2014）。
在这些元启发式算法中，GA遗传算法在寻找近似解方面已被证明是强大和有效的（Costa等，2017）。由于具有较强的全局搜索能力，近年来遗传算法被广泛应用于解决单元制造问题。Niakan等(2016)提出了一种非支配排序遗传算法，以最小化总成本。Imran等人(2017)开发了模拟集成混合遗传算法，以最小化 CMS中的在制品增量。Feng等人(2016)开发了一种改进的遗传算法来解决集成单元形成和调度问题。Liu等人(2016b)提出了一种用于优化能耗和车间生产性能的多目标遗传算法。
与以往的文献不同，我们考虑了具有柔性路线和机器共享的动态单元制造调度问题，并建立了一个新的双目标数学模型，以最小化完工时间和总工作负荷。我们把更多的重点放在机器负载的平衡上，以更好地优化CMS中的资源。为了解决调度问题，我们提出了一种新的三层染色体遗传算法，其中采用联合选择策略，以确保最优个体被复制到下一代，同时保持基因库中的变异性。此外，构建的染色体结构和交换规则可维持各工件的工序顺序。提出的TCGA可以显著减少完成、等待和单元间移动时间。最后，我们在附录A中总结了我们的论文和相关文献之间的主要差异以及我们的贡献。
本文其余工件的结构如下：第2节描述了问题并阐述了模型。第3节介绍了提出的TCGA算法。第4节进行仿真实验。第5节总结论文并提供未来的研究方向。
2.问题描述
一个单元制作系统包含一系列单元U={1，2，hellip;，c}，和一系列机器M={1,2，hellip;，m}。一台机器可能属于多个单元，且单元布局预先给出。有一组n个工件J={1,2，hellip;，n}，且需要由这m台机器进行加工。每个工件j都有其特定的编号和工序序列{，，hellip;，}。一道工序可以由多台机器（称为可选机器）以不同的处理时间和效率进行加工。每道工序在各台机器上的加工时间提前可知。对于每个工件，我们需要同时决定机器的分配和他们工序的排序。如果工件的相邻工序被分配到位于不同单元的机器，则必须考虑单元间移动的时间。
每个工件j都有一个整数的交货期dj。为保持生产过程的平稳，原材料的短缺是不允许的。在交货期的约束下，空闲或低工作负荷的机器必须优先调度。必须确定的最佳调度以同时最小化所有机器的总工作负荷和系统的完工时间。
2.1. 假设和符号说明
本文考虑的调度问题基于以下假设：
1. 每台机器同一时刻最多只能处理一道工序，每道工序最多只能被一台机器处理；
2. 准备时间与工序排序无关，包含在加工时间中；
3. 假定单元内移动时间为零；
4. 单元配置事先已知（即一个机器属于哪一个单元是明确已知的）；
5. 允许单元间机器共享。
因此，本文中使用的符号总结如下：
n：工件总数；
m：机器总数；
j：工件索引，jisin;J，J={1，2，hellip;，n}；
k：机器索引，kisin;M，M={1，2，hellip;，m}；
nj：工件j的工序总数；
Oij：工件j的第i个工序，iisin;Ij，Ij={1，2，hellip;，nj}；
pijk：机器k上工序Oij的加工时间；
A：可以加工工序Oij的可供选择的机器，
tuu＇：工件j 从单元u移动到单元u＇的单元间移动时间，如果u=u＇，则tuu＇=0；
c：单元总数；
U：单元集，U={1，2，hellip;，c}；
u：单元索引，uisin;U；
dj：工件j的交货期；
yku
决策变量：
xijk
Cij：工序Oij的完工时间；
sij：工序Oij的开始时间。
2.2. 目标函数及约束条件
我们的优化目标是同时最小化所有机器的总工作负荷和最大完工时间。因此，多目标模型公式如下：
（1）
其中
（2）
（3）
约束条件：
表达式 (1) 是最小化和的目标函数，如式(2)和(3)所示，是所有机器的总工作负荷，是系统的完工时间。约束(4)确保每道工序只能分配给一个可用的机器。约束(5)是工序优先级约束，即一道工序必须在其前面的工序完成后开始。约束(6)确保每台机器同一时刻只处理一道工序。约束(7)表示工序Oij的完成时间。约束(8)表示，如果分配的工序Oij和O(i 1)j的机器在不同的单元中，则将出现单元间移动时间。约束(9)是工件交货期约束。约束(10)和(12)意味着每道工序的开始时间和完成时间必须是非负的。约束(11)表示x是二元变量。约束(5)、(6)和(8)有助于确保工序的加工顺序。约束(5)和(8)是同一工件的工序优先级约束，索引较小的工序 O(i-1)j比后续工序Oij加工得早。约束(6)是同一机器的工序优先级约束，每台机器同一时刻不能处理多个工序。我们考虑了两个经典的目标，总工作负荷和完工时间，这是在单元调度问题中常用的。应该注意的是。必须说明的是不同的可选机器对于相同的工序具有不同的加工时间；将工序分配给需要最少等待时间但需要较长加工时间的机器可能不是最佳方式。我们的模型是建立在同时考虑等待时间、加工时间和单元间移动延迟的基础上，有效地解决单元调度问题。
3. 提出的TCGA算法
本节根据CMS的特点开发了TCGA。该算法引入了一个新的三层染色体来解决NP难题单元制造调度问题。本节提供了该算法的更多详细信息。
3.1.TCGA框架
在我们提出的TCGA中，每个基因代表一个工件的一个工序分配，群体中的每个个体代表所有工序的可用机器和单元的分配。该算法还应用了混合选择算子和修复过程。除变异程序外，在所有选择和交叉程序中，各工件的工序顺序均未违反。具有能够最小化完工时间和总工作负荷的工序序列的染色体被确定为最佳个体。
提出的TCGA算法的主要步骤概述如下：
第 1 步：初始化参数。输入群体大小、最大终止代数、交叉率和变异率。设置 Gen=0并加载测试数据。
第 2 步：根据基于单元工件特征的程序生成初始群体。
第 3 步：如果达到最大代数，则进行第 9 步；否则，执行第 4 步。
第 4 步：计算当前代中每个个体的适合度。
第 5 步：选择当前群体中适应度最好的个体，然后采用轮盘赌转轮机制。找到适合度最差的个体，然后用适合度最好的个体替代该个体。
第 6 步：对每对染色体上执行交叉操作。
第 7 步：对当前染色体上执行突变操作。如果获得的个体有效，直接进入第 8 步；否则，按照修复程序重新分配改变的工件的基因，然后进入第 8 步。
第 8 步：用新群体替换当前群体。令Gen=Gen 1，然后执行第 3 步.
第 9 步：停止并输出最优解。
图1 提出的TCGA算法的一般结构
3.2. 编码与解码
传统的染色体编码方法只能处理特定机器的工件。这样的表示中，每个基因表示一道工序或一台机器，不能同时表示可选机器上的工序和分配的单元。在本节中，我们开发了一种三层染色体，以处理CMS中的可选机器。图 2 说明了染色体的表示。基于工序的排列的染色体编码方法表示加工工序Oij的单元系统。该编码方法不仅能表示工件的加工顺序，而且还能表示所分配的机器和工序的单元。
图2
全文共20991字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[1734]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
