Accepted Manuscript
Exact and Heuristic Methods for solving the Robotic Assembly Line Balancing Problem
Leonardo Borba, Marcus Ritt, Cristacute;obal Miralles
PII: S0377-2217(18)30220-0 DOI: 10.1016/j.ejor.2018.03.011 Reference: EOR 15030
To appear in: European Journal of Operational Research
Received date: 25 October 2016 Revised date: 5 March 2018 Accepted date: 7 March 2018
Pleasecitethisarticleas:Leonardo Borba,Marcus Ritt,Cristacute;obal Miralles,ExactandHeuristicMethods for solving the Robotic Assembly Line Balancing Problem, European Journal of Operational Research (2018), doi: 10.1016/j.ejor.2018.03.011
This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Highlights bull; Weproposenewalgorithmsforminimizingthecycletimeinroboticassembly lines. bull; The first is a branch-bound-and-remember method with cyclic bestfirst search. bull; The second is an iterative beam search. bull; Both methods use newly proposed lower bounds and dominance rules. bull; Our methods improve the results from the literature and are faster.
1
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Exact and Heuristic Methods for solving the Robotic Assembly Line Balancing Problem Leonardo Borbaa, Marcus Ritta, Cristacute;obal Mirallesb aInstituto de Informacute;atica, Universidade Federal do Rio Grande do Sul, Av. Bento Gonccedil;alves 9500, Porto Alegre-RS, Brasil bDepartamento de Organizaciacute;on de Empresas, Universitat Polit`ecnica de Val`encia, Camino de Vera, s/n, Valencia, Espatilde;na Abstract In robotic assembly lines the task times depend on the robots assigned to each station. Robots are considered an unlimited resource and multiple robots of the same type can be assigned to different stations. Thus, the Robotic Assembly Line Balancing Problem (RALBP) consists of assigning a set of tasks and a type of robot to each station, subject to precedence constraints between the tasks. This paper proposes a lower bound, and exact and heuristic algorithms for the RALBP. The lower bound uses chain decomposition to explore the graph dependencies. The exact approaches include a novel linear mixed-integer programming model and a branch-bound-and-remember algorithm with problem-specific dominance rules. The heuristic solution is an iterative beam search with the same rules. To fullyexplorethedifferentcharacteristicsoftheproblem,wealsoproposeanewset of instances. The methods and algorithms are extensively tested in computational experiments showing that they are competitive with the current state of the art. lowast;Corresponding author Email addresses: lmborba@inf.ufrgs.br (Leonardo Borba), mrpritt@inf.ufrgs.br (Marcus Ritt), cmiralles@omp.upv.es (Cristacute;obal Miralles)
Preprint submitted to Computers amp; Operations Research March 13, 2018
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Keywords: Production, Robotic Assembly line balancing, Branch-bound-and-remember, Beam Search 1. Introduction The range of tasks that can be performed by robots has increased significantly in the past decades Purnell (1998); Henrich amp; Wuml;orn (2000); Baeten et al. (2008). Robots are especially efficient for the repetitive small tasks, which are common in flexible assembly lines Milberg amp; Schmidt (1990); Pires amp; Sacute;a da Costa (2000). TomodelthiskindofproblemRubinovitzetal.(1993)haveproposedtheRobotic Assembly Line Balancing Problem (RALBP). The RALBP extends the Simple Assembly Line Balancing Problem (SALBP) Baybars (1986) by adding the concept of robots. In the SALBP a set of partially ordered tasks must be assigned to a linearly ordered set of stations, such that the task precedences agree with the linear order of the stations Scholl amp; Becker (2006). Each taskt has a task time pt and the station time of each station is given by the total time of the tasks assigned to that station. The greatest station time defines the bottleneck of the line and therefore the cycle time of the line. Possible objectives are to minimize the cycle time, or the number of stations, or both, or simply finding a valid solution. In the caseoftheRALBP,arobotmustbeadditionallyassignedtoeachworkstation,and is responsible for performing the tasks assigned to that station. Robots are usually heterogeneous and the time to execute a task depends on the robot performing it. According to the definition of Rubinovitz et al. (1993), the RALBP is composed of a set T of nonpreemptive tasks. These tasks must be assigned to a set of workstations S. There is also a set of types of robots R and one robot of type risin;R must be designated to each workstation.
3
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT The time ptr needed to execute the task t isin;T is deterministic and depends on the type r of the robot assigned to the station where task t is performed. The station timeCs is the sum of the task times ptr of the tasks t assigned to station s, given that robot r is responsible for that station. The cycle time of the line then is the largest station timeC = maxsisin;SCs. We also have a set of precedence relations A. If (t,t0)isin;A task t precedes task t0. For such a pair, task t0 can only be executed at the same station as t or at a station following the station performing t. Based on these assumptions, the RALBP has two dependent variables: the number of workstations |S| and the cycle time C of the line. In this paper we propose solutions for the minimization of C given a fixed |S|. This problem is called RALBP-2 in the literature. 1.1. Related Work Assembly Line Balancing research, which was traditionally focused on the SALBP defined by Salv
全文共63682字，剩余内容已隐藏，支付完成后下载完整资料
摘要
在机器人装配线上, 任务时间取决于分配给每个工作站的机器人机器人被认为是一个无限的资源, 多个相同类型的机器人可以分配到不同的站因此, 机器人装配线平衡问题 (RALBP) 包括将一组任务和一个机器人类型分配给每个工作站, 前提是任务之间的优先约束。本文提出了 RALBP 的下界、精确和启发式算法。下界使用链分解来探索图形依赖关系。具体的方法包括一种新的线性混合整数规划模型和一个具有问题 specific 优势规则的分支绑定和记忆算法。启发式解是具有相同规则的迭代波束搜索。fullyexplorethedifferentcharacteristicsoftheproblem, wealsoproposeanewset 的例子在计算实验中对方法和算法进行了广泛的测试, 表明它们与当前的艺术状态具有竞争性
1. 导言
在过去数十年中, 机器人可以执行的任务范围增加了 significantly Purnell (1998);亨利克 amp; Wuml;orn (2000);Baeten 等 (2008)。机器人是特别 efficient 的重复小任务, 这是常见的flexible 装配线 Milberg amp; 施密特 (1990);皮雷 amp; Sacute;a 大哥斯达黎加 (2000)。TomodelthiskindofproblemRubinovitzetal。(1993) haveproposedtheRobotic 流水线平衡问题 (RALBP)。通过增加机器人的概念, RALBP 扩展了简单装配线平衡问题 (SALBP) Baybars (1986)。在 SALBP 一组部份地被定购的任务必须被分配到一个线性地被定购的集合驻地, 这样任务优先权同意驻地的线性顺序 amp; 贝克尔 (2006)。每个 taskt 都有一个任务时间角每个站的站时间由分配给该站的任务的总时间给出最伟大的驻地时间 defines 线的瓶颈因此线的周期时间可能的目标是尽量减少周期时间, 或站的数量, 或两者, 或者干脆finding 一个有效的解决方案。在 caseoftheRALBP, arobotmustbeadditionallyassignedtoeachworkstation, 负责执行分配给该站的任务。机器人通常是异构的, 执行任务的时间取决于执行它的机器人根据 Rubinovitz 等 (1993) 的 definition, RALBP 由 nonpreemptive 任务组成。这些任务必须分配给一组工作站。还有一组类型的机器人 r 和一个类型为 risin;r 的机器人必须指定给每个工作站.
执行任务 t 所需的时间 ptrisin;t 是确定性的, 取决于分配给执行任务 t 的工作站的机器人的类型河。站 timeCs 是任务的任务时间 ptr 的总和 t 分配到驻地 s, 考虑到机器人 r 负责那驻地。该行的周期时间是最大的站 timeC = 麦克斯isin;南海。我们还有一组优先权关系。如果 (t,t0)isin;在任务 t0 之前执行任务 t。对于这样的一对, 任务 t0 只能在 t 或工作站执行之后的工作站上执行。基于这些假设, RALBP 有两个相关变量: 工作站的数量 |S |和循环时间 C 的线。本文提出了fixed 的最小化解S |。这个问题在文献中被称为 RALBP-2。
1.1. 相关工作
装配线平衡研究, 传统上侧重于 SALBP defined 由 Salveson (1955) 通过几个众所周知的简化假说, 最近已经丰富了许多现实的特点, 已相继添加在文学 (参见学的评论 amp; 贝克尔 (2006);贝克 amp; 上学 (2006);Boysen 等 (2007, 2008);Battauml;ıa amp; Dolgui (2013))。在考虑到所涉资源的异质性的特殊情况下, Rubinovitz 等 (1993) 所提出的 RALBP 模型是明确的 antecedentofthistrend、inspiringfurtherapproachesliketheAssemblyLineWorker问题 (ALWABP) first 提出的 Miralles 等 (2007)。本文提出了一组由残疾人庇护工作中心装配线驱动的新假说, defined, 所有工人都被认为是异类RALBP 的根本区别是 theresources 可用性受到约束: 在 RALBP、中、如果方便、可以将同一类型的机器人分配给多个工作站而在 ALWABP。尽管清楚的区别, 确切的方法为 SALBP Salveson (1955);上学 amp; 贝克 (2006);克莱因 amp; (1996);莫里森等 (2014);Vil amp; (2013) 和 ALWABP Miralles 等 (2007, 2008);维拉港 amp; (2014);Borba amp; Ritt (2014) 可应用于 RALBP。值得注意的是, SALBP 下限 amp; 贝克尔 (2006), 一些优势规则 (如最大负荷规则杰克逊 (1956)) 和搜索策略, 上学 amp; 贝克 (2006);莫里森等 (2014);Vil amp; (2013)维拉港 amp; (2014);Borba amp; Ritt (2014)。然而, SALBP 和 ALWABP 的许多方法在很大程度上依赖于这些问题的性质, 不能适应 RALBP。杰克逊的统治统治杰克逊 (1956), 建议 SALBP, 高度 dependsonstation independenttasktimestodefinepotentialdominationbetween 的任务。同样, 这个问题不能放宽到无界并联机器调度问题 Borba amp; Ritt (2014), 像 ALWABP。在 RALBP 文学中, SALBP 的两个下限被使用 Rubinovitz 等 (1993): LM1 = Pminus;/C RALBP-1 和 LC1 = Pminus;/|S |对于 RALBP-2, 其中 Pminus; = sum;tisin;t minrisin;R ptr 是最小任务时间的总和 amp; 贝克尔 (2006)。这两个下限放宽优先约束, 并考虑优先级的任务, 在各站之间平等地划分Rubinovitz (1993) 还提出了一个最佳first 搜索 branchand 绑定算法的类型1的问题。对于 RALBP-2, 列维京等 (2006) 提出了遗传算法。他们的算法使用一个共同的基因型, 变异和交叉算子的遗传 algorithmsfor SALBP Rubinovitz amp; 列维京 (1995)。他们还通过爬山算法改进了这个 GA 的结果。Mukund Nilakantan (2015) 提出了粒子群优化 (pso) 方法和 pso 算法的混合方法, 并给出了 RALBP 最著名的结果。他们还介绍了 RALBP 的数学公式, 这里称为 M1。模型 M1 是一个使用两个索引变量的二次混合整数规划模型。最后, 高等 (2009) 解决了一个不同的 RALBP 问题, 其中只有一个机器人的每种类型是可用的, 因此, 只能分配一次。这个问题等同于 ALWABP, ALWABP 在文献 Miralles 等方面 significantly 了较好的效果 (2007);查韦斯等 (2007);Mirallesetal。(2008);Chavesetal。(2009);百隆 amp; Miralles (2011);Moreira 等 (2012);Mutlu 等 (2013);维拉港 amp; (2014);Borba amp; Ritt (2014);Polat 等 (2016)。
1.2. 文件概要
在下一节中, 我们将介绍 RALBP-2 的解决程序。2节介绍了问题的数学公式。在3节中, 我们研究了一种新的下界它使用任务相关性来提高文献中的下限。此外, 在4节中提出了一个分支绑定和记住 (BBR) 方法来解决这个问题, 并为 RALBP 设计了一系列的优势规则。然后在5节中提出了使用相同的优势规则和下限的迭代波束搜索。在6节中介绍了 computationalexperimentsforthemixed 整数规划问题 (MIP) 模型、下界、启发式和分枝约束方法, 并提出了一套新的实例来探索 problem2 的不同特征。数学公式
我们提出使用模型 M2, 避免了模型 M1 的二次函数。我们还使用 Ritt amp; 哥斯达黎加 (2015) 提出的技术来改进优先约束。结果模型 M2, 用表示法在表1中描述, 然后可以 defined 由
M2 = 最小化 C, (1) 受限sum;tisin;ptrxtsle;c Mr (1minus;ysr),forall;sisin;S、risin;R, (2)sum;risin;R ysr = 1,forall;sisin;S, (3)sum;sisin;xts = 1forall;tisin;T, (4)sum;kisin;Ii | kle;s xikge; sum; kisin;Ij | kle;xjk, forall;iisin;isin; sisin;s, (5) xts isin;{01}, forall;sisin;s, t isin;As, (6) ysr isin;{01}, forall;sisin;s, risin;R. (7)
模型最小化循环 timeC (1), defined 约束 (2)。自 rightsideofconstraint (2) mustbefreetoassumeanyvaluewhenysr isnotsetand、givenalowerboundC onthecycletime、wecanassumethatMrge;sum;tisin;t {ptr} minus;C, 为每个机器人 r. 约束 (3) 和 (4) 确保每项任务将执行, 每个工作站将有一个机器人分配给它约束 (5) defines precedencerelationsbetweenthetasks。Therobotsdonotaffectthedependencies, 因此 SALBP 的优先约束可以直接应用于 RALBP。我们确保变量 xts 仅 defined 在给定的工作站 s (t isin;) 中执行的任务 。模型 M2 是线性的并且有 O (|T | |S | 表 1: 文章中使用的符号。
T 集任务;R 组机器人;S 组工作站;Et 和它是最早的和最新的驻地, 分别, 在那里一个任务可以安置;as = {t isin;t |Et le;sle;s}, 可分配给工作站的任务集;它 = {sisin;s |Et le;sle;s}, 可执行任务 t 的工作站集;G (T, A) 任务的优先关系图, 其中 (t,t0)isin;指示任务 T 必须在任务 t0 之前执行;否则为glowast;(t,lowast;) 图 g (T, a) 的传递闭包;任务 T 的 ptr 执行时间由机器人 r;P t sube;集合任务 t 的直接前辈;F t sube;设置任务 t 的即时追随者;P lowast;t sube;集任务 t 的所有前辈;F lowast;t sube;集所有任务的追随者 t;(C) 解决方案的周期时间;常量等于 sum;tisin;t {ptr} minus;C; xts 1 如果任务 t 被分配到驻地 s, 并且0否则; ysr 1 如果机器人 r 被分配到驻地 s, 并且0否则.
|S | |R |)变量和 O (|S | |R | |T|2|S |)约束。
3. 下限
下界 LC1 Rubinovitz 等 (1993) 放松优先约束。在我们建议的下限 LC2 中, 我们维护一些优先约束, 使我们有一组任务链 Tc, 并删除所有其他优先约束。由于这组链的优先约束存在于 theoriginalgraph 中, allthesolutionsthatarevalidfortheoriginalproblemarevalid 为适应的实例。因此, 新实例的最优解是原始问题的有效下限为了将原始图分解为一组链 Tc, 我们迭代选择了图表中最长的链, 直到所有任务都分配给其中一个链。最长的链子被选择, 因为这增加了机会 multipletasks 被分配到同一个驻地, 并且同样机器人必须执行他们。请考虑如图1所示的示例。我们first 选择图的最长链 (t1,t2,t5,t6)。然后, 只有任务 t3 和 t4 保持, 它们形成第二个链。选择链后, 我们确定每个链的最小总任务时间, 考虑到一些小组的任务必须在同一站, 因此由同一机器人。一组链的最小总任务时间是每个链的最小总任务时段的总和。对于给定的链 Q = (q0,q1,..., qnminus;1), 可通过动态规划计算最小总任务时间。让
MQ (t, s) =
0, 如果 t = n,infin;, 如果 t lt; nand;s = 0, min t lt; t0le;n min risin;Rsum;tle;t00 lt; t0 pt00,r MQ (t0、sminus;1), 否则,
(8)
betheminimumtotaltasktimefortasksqt,..., qnminus;1 onsstations。ThenMQ (0, |S |)是链 Q 的最小总任务时间。有first 两个条件处理基本情况: 如果已分配了所有任务, 则剩余任务的总和为零;如果没有站, 但仍然任务分配, 这是不可能解决的问题。否则, 我们在范围 [t,t0) 中分配任务, 对于当前工作站的某些 t lt; t0le;n, 并将执行这些任务的机器人分配到该 stationTo 的执行时间, 我们必须将最小总时间添加到执行剩余的任务从 t0 开始在一个驻地较少。考虑的情况下, 我们有一个链 Q = (q0,q1,q2,q3) 长度四, 两个站和两个机器人。任务有时间 p11 = 1, p12 = 2, p21 = 2, p22 = 1, p21 = 1, p22 = 2, p41 = 2, 和 p42 = 1。minimumtasktimesis4 的总和。然而, atleasttwosubsequenttasksmustbeassigned 是同一个机器人实际上, 定期 (8) 获得的最小总任务时间的结果是 MQ (02) = 5。函数 M 可以通过动态规划确定, 时间 O (n2 |S | |R |)对于
全文共29605字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11452]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
