英语原文共 23 页
资源约束拆卸线平衡问题研究
摘要：拆卸线平衡（DLB）问题是将一组拆卸任务按照一定的顺序分配给多个工作站，从而优化某些性能指标（如工作站数量、危险不见数量、周期任务和工作负载）的过程。当拆卸作业在拆卸线上进行时，有时需要特定的资源，如，机器人、设备、材料、特定的机器或合格的在工作站上工作的工作人员。这个问题也引发了资源受限的拆卸先平衡（RCDLB）问题。因此，本文提出了考虑资源约束的DLB问题的数学模型，目标是在确定时间内尽量减少资源和工作站的数量。数学模型的求解采用一种称为GAMS-CPLEX的数学程序包，为了检验有效性，对文献的两个例子进行了求解和分析。
1.简介
拆卸操作是一种从一个产品上移除一部分或一组部件或组件，或者是将一个给定物体分解成它的所有组成部件的一种系统方法（Gungor and Gupta, 2001 ）。拆卸操作可以在一个单独的工作站，一个拆卸单元或者是一个拆卸线上进行。机关在拆卸单元和单独工作站上进行操作更加灵活，但是拆卸线有更高的效率，因此装拆卸线是拆卸任务的最优选择（Kalayc1 and Gupta,2014）. DLB问题处理的是将任务拆装到一组有序且考虑拆卸优先级的工作站并满足某些性能指标的约束。Gungor 和Gupta在2001年首次对DLB问题做出科学研究，在之后的数十年里，出现了很多关于这方面的研究。在这段时期，不同的新平衡问题概念被提出，例如 Altekin 在2008; Kocet在 2009; Altekin 和 Akkan,在2012年研究的直线型，Avikal 和Mishra,在2012， Avikal 于2013 提出的U-type，Aydemir和Turkber于2013年，hezaer和Kara于2015年提的平行型。一些解决算法，如Koc等于2009年，Bentaha于2015年提的精确解决方案，McGovern和Gupta在2007年提出遗传算法，Kalayci和Gupta在2014年提出禁忌搜素。这些问题的相同点是在最有效率的情况下都用了操作人员和机器。但是，由于拆卸线的一些性质如：危险性，有爆炸材料和紧密工具，所以需要特殊的资源。由于这些情况需要使用特殊的装备和专业的工作人员，因此有必要形成一个产业。为了从拆卸线中获得最大效益，这些装备和工人以最高效率添加到产线中，例如最大利用率和最小工作站数。尽管Pinnoi和Wilhelm于1997年，Agpak和Gokcen于2005年，Mete和Agpak于2013年都提出了资源约束下的拆卸线平衡问题，但是这个问题还没有得到解决。本文中，考虑在资源约束下的拆卸线平衡。通过在进行拆卸时最小化工作站数量来实现最大化利用这些资源。本文主要有以下几部分构成：在本部分简介及文献回顾后，第二部分将列写资源约束情况下的拆卸线公式；第三部分，对于已给出的资源约束下拆卸线平衡的数学例子进行讨论。最后一部分总结以及对未来研究的建议。
2.资源约束拆卸线平衡问题的数学模型
本文考虑了资源约束条件下的DLB问题。本文的目标是找到一个能够解决有资源约束的DLB问题的解决方案。因此，建立数学模型。假设模型集合了Agpak和Gokcen于2005年提出的简单的资源约束装配线平衡问题以及Koc等于2009年提出DLB证书规划公式。该模型的的目的是最小化分配给工作站的资源数目。这些资源可能是机器人，工人数量或者是特殊机器的数量。本文中，每种拆卸任务仅用到一种资源（R1或者R2），例如资源R1可以用来执行任务{1，3，5，7，9}，资源R2可以用来执行任务{2，4，6，8}。因此任务的交集是空的集群（Agpak和Gokcen，2005）。RCDLB问题数学模型的模型假设以及符号如下：
2.1模型假设
这些假设在数学模型中通用。在本文中，资源约束拆卸线在以下假设条件下进行：
每个拆卸任务时间已经知道；
拆卸能提取出其中一个或多个部分；
每个任务仅分配给一个工作站；
分配给每个工作站的任务处理总时间必须小于循环时间；
任务之间的优先关系必须满足。
2.2符号表示
下面给出了拟建模型的一些符号。这些符号和方程式将用来描述改问题。
指标：
I 任务序号，i=1...N
J 工作站序号，j=1...M
R 资源类型 ，r=1...R
T 循环时间
参数：
dBi：正常节点的任务时间；
决策变量：
Hjr =1,工作站“j“有资源”r”
Sjr 能在工作站“j”中用资源”r“完成的任务
Xij=1 任务Bi被分配给工作站“j”
Fj=1表示工作站“j”打开；
Zi=1表示任务Bi正在执行
基本结构的整数规划公式RCDLB问题如下：
主函数：
约束函数：
目标函数是将分配给工作站的资源数量最小化。约束(2)规定，如果在工作站“j”中至少执行一个任务，并且工作站“j”中使用资源“r”，则值取1。使用约束(3)和(4)选择一个或多个继承项。约束(5)确保所选任务分配给最多一个工作站。约束(6)解决正常节点之间的优先关系：当正好一个人造节点的OR继承者和一个OR前任约束将被选择时，约束（6）确保继承者将会被分配给更高优先级的工作站，而不是前任。(7)是分配给每个工作站的任务时间总和不超过周期时间的循环时间约束。最后一个约束(8)是二进制约束。
3.数学范例
本部分举了两个例子来说明设计模型的有效性，分别是23个任务及30个任务。所提出的模型是用GAMS/CPLEX（通用代数建模系统），本实验在核心2.40Ghz处理器，8Gb内存的Intel Xeon4计算机上进行。无线电示例和样本模型的循环时间分别是25s和35s。本实验考虑两种资源类型（R1，R2）。表1列举了每个任务的任务时间及需要的资源。图1展示了样本模型的TAOG。表1有各个任务需要的资源及任务时间。该实验分别在有/无资源约束的情况下进行。
图1.样本模型的TAOG（Koc，2009）
表1 样本模型的拆卸任务时间及所需资源
表2得到了当拟建模型在没有资源约束情况下取得的结果。在该情况下的目标是在循环时间已知的情况下最小化工作站数。
表2 不考虑资源约束情况下的DLB问题
在之前的实验结果上考虑资源约束问题得到表3的结果
表3 考虑资源约束的DLB问题
两种情况下的空闲时间和工作站数相同。表2和表3根据23个任务所需的资源对两个情况下的模型进行比较。在第一中1情况下，DLBP用了3个工作站和5个机器人（2个R1型和3个R2型）。因此，对于资源数量来说这是最好的解决方案。最小工作数量也达到。
收音机模型同样考虑有/无资源约束。图2展示了收音机模型的AND/OR转化关系。表4给出了各个任务所需的资源以及任务时间。
图2 收音机模型的TAOG（Altekin和Akkan，2012）
表4收音机模型各部分的拆卸时间以及所需资源
表5给出了没有资源约束情况下的模型实验结果。在表5中，在执行拆卸任务时有4个R1类型机器人和3个R2类型机器人。在第一和第二种情况下（有/无资源约束），打开的工作站的数目一样。
表5无资源约束的收音机DLB问题结果
在另一种情况下，用到了4个R1机器人和2个R2机器人（详见表6）。这种情况下R2类型机器人比第一种情况下少一个。
表6收音机的RCLDLB问题结果
拟建模型的主要目标是，当拆卸任务被分配给工作站时，能用同一种资源进行操作的任务应该分配到同一个工作站。通过这种方法我们可以在使资源数减少（如表3和表6）。
4.总结
本文应该是第一次尝试解决RCDLB问题。在现实生活应用中，在执行拆卸任务时，一些资源如特殊的机器，工人数量或者是机器人数量可能都会有限制。这些条件就引出了资源约束问题。为了实现资源约束，提出了一个数学模型，该模型结合了Agpak和Gokcen（2005）的方法以及Koc（2009）的方法。改方法的目标是最小化工作站数和最小化资源数目。该方法使资源节约或者利用尽可能的高效。模型结果证明这种方法有效。
在未来，所提出的方法可以应用于其他类型对于DLB问题，如并联、双面、u型等。在未来的研究中可以考虑不同的资源场景，如两种或者更多更广的情况。启发式算法也可以用来研究RCDLB问题。
混合模型多人装配线平衡问题：数学模型及模拟退火 算法
3.数学模型
在本节中，将Fattahi等人在2011年提出的单模型MALBP的数序模型扩展到多模型MALBP。首先给出了问题的描述和问题的一些假设，然后，对该问题进行数学建模。
3.1问题描述
在本文中，一个混流装配线被认为是面向流的多工位的按顺序排列的生产系统。混流装配线用来装配一组拥有相同产品特点的产品模型。每个模型都有它自己的优先关系，但是所有模型都有一个共同的任务子集。因此,
可以组合所有模型的优先关系图，生成的结果有NT个任务。所有模型组合起来的优先关系图标的任务在多人操作的工作站执行，其中有一个或多个工人
同时在同一产品上完成不同的任务。在模型m上执行任务i所花费的时间记为tim，（tim=0表示模型m不需要任务i装配）。产品模型需要在于先确定的规划的周期H内完成。需要的周期时间确定，通过公式1（Ozcan和Toklu于2009年提出）求出，全部的模型m(qm)的单位比例由公式2给出
该问题可以描述为，将任务分配给多工位的工作站，该问题的第一目标是使工人的数量最小化，第二目标是使多工位工作站数最小。下面是针对该问题做的一些约束：
针对所有的模型来说，每一个任务必须只分配给一个工人来完成；
所有的任务之间必须满足装配优先关系；
每个工人的工作时间包括闲置时间不得超过循环时间Ct。
3.2问题假设
针对多目标装配线平衡问题做出如下假设：
各个任务的执行时间确定；每个模块都有它自己的优先关系，但是所有模型都有一个共同的任务子集，因此,可以组合所有模型的优先关系图，生成的结果有NT个任务；一组相似的模型（m=1[hellip;], Nm）可以同时在一个多工位的工作站装配线上进行装配；在每个工作站上，可能根据产品的特征给一个工作站分配一个或者多个工人；每个工作站分配的工人的最大数量不得超过预先设定值AMW(每个工作站的既定最大工人数量；工人的步行时间可以忽略；不允许由平行任务和平行工作站；不允许有半成品投入仓库；每个工人装备都足够，因此他们不需要共享他们的设备；没有装备限制去限制某些任务分配给某些工作站；所有的工人掌握的技能完全相同，工作效率完全相同。
3.3数学公式
3.3.1目标函数
公式3由两部分组成，第一部分计算出了整条装配线上所有的工人数量，第二个表示的是多工位工作站的加权数量。权重因子ε确保第二部分的值一直小于1。因此，第一部分（装配线上工人的总数量）最小是第一约束，第二部分（多工位工作站的数量）最小是第二约束。
3.3.2任务分配约束
约束4表示的是不管产品模型怎么分配，都只将一个任务分配给一个工作站的一个工人。
3.3.3装配优先关系约束
分配给各个多工位工作站的工人的任务必须满足装配先后关系。当任务i的所有先验工作比如h分配给优先工作站时，任务i才可以被分配给多工位工作站的工人。约束5确保所有的模型间的优先关系必须满足。
3.3.4循环时间约束
约束6确保每个模型的每个任务必须在工作站循环时间结束之前完成装配。
3.3.5排序约束
约束(7)、(8)和(9)控制任务的顺序相关的完成时间。
约束(7)适用于每一对任务i和h，使得h是i的直接前身，并且可以分配给相同的多人工作站j。
如果任务i和h被分配到同一个工作站上，那么约束(7)对于所有模型来说都变成了Comtim-Comtimge;tim。
这个不等式表明任务i可以在它的直接前辈h完成之后开始。
如果将这两个任务分配给不同的工作站，则总是通过引入足够大的数量(例如Ct)来满足约束。
约束(8)和(9)控制任务e和g的完成时间，这些任务没有优先关系，并且分配给同一多人员工作站的同一工人。
当这两个任务分配给同一个worker时，如果g的分配时间早于e (zge 1)，则约束(8)对于所有模型m都成为Comtem，如果e的分配时间早于g，则约束(9)对于所有模型m都成为Comtgm。
然而，如果将这两项任务分配给不同的工人，由于人数众多，因此在约束(8)和(9)中没有考虑到这两项任务。
3.3.6工作站和工人约束
约束（10）强制如果一个任务分配给jth工作站的第k个工人，那么wjk必须等于1.如果至少有一个任务分配给了多工位j的一个工人，即使用了多工位j，约束（11）确保wsj为1.约束（12）显示了多人员工作站的顺序，约束（13）保证了多人员工作站中工人的负荷呈递增趋势。
3.3.7变量定义
约
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
