文摘
本文研究一个起重机调度问题出现在冷轧材料仓库的钢铁企业。一组线圈存储在两个水平是需要拿起和运送到指定位置。如果需要线圈在上层,它可以马上拿起和运送到指定位置(运输操作)。线圈在低水平无法拾起,直到所有的屏蔽线圈在上层移动到其他位置(洗牌操作)。一个高架起重机是用于执行所有运输和移动操作。我们的问题是安排起重机操作,所有需要的线圈检索指定的位置在最短的时间内(考)。因为显示的问题是np困难,提出了一种遗传算法(GA)。我们确定了一些分析性质,使我们能够开发一个有效的启发式算法作为遗传算法的初始解。我们从最坏的角度进一步分析其性能。评估平均表演,一个数值测试进行与一些现有的方法相比,其结果表明了该算法的质量好。
1。介绍
在钢铁企业中,冷轧生产过程主要是最后阶段的最终生产钢铁产品与客户要求尺寸,表面光洁度,机械性能等等。在冷轧过程中使用的材料是钢热轧线圈。这些线圈存储在冷轧材料仓库和检索时需要根据冷轧生产计划。通常一个区域在仓库是由一个单一的桥式起重机。请参见图1三行作为一个例子。起重机在该地区沿着轨道移动,而其传感器设备(起重机)可以沿着起重机桥。这样,吊车的吊车可以达到任何位置。从这里开始,我们将参考起重吊车的位置仅仅是起重机的位置。在每个区域中,线圈存储在行。根据工艺要求,线圈最多可能存储在两个水平。必须支持任何线圈储存在上层由两个线圈在较低的水平。当线圈是必需的,它可以直接检索存储在上层或存储在低水平,而不是阻止线圈在上层。如果它是储存在较低的水平,有一个或两个线圈在上层屏蔽,屏蔽线圈必须打乱其他空位置在该地区之前所需的线圈可以检索。检索所有必需的线圈和洗牌的屏蔽线圈是由桥式吊车。
在整个论文中,接所需线圈和移动到其指定地点将被称为起重机运输操作。接屏蔽线圈的移动到一个空的位置将被称为起重机移动操作。运输操作或移动操作,有关线圈需要举起从当前位置,移动到另一个位置,然后下降。整个过程被认为是一个装载起重机移动。起重机卸下一个线圈后,空起重机可以移动到另一个线圈加载执行下一步。我们探索一个起重机调度问题来确定运输和洗牌动作序列,并决定屏蔽线圈的位置应该被打乱。目标是最小化考的时间,完成所有必需的线圈的检索。
有效的解决方案的调度问题有助于实现更好地利用昂贵的高架起重机和提供更好的物流支持钢铁生产过程。同样的问题也存在于其他仓库、材料和产品仓库等热镀锌和acid-rolling操作和堆栈码在集装箱码头,但没有收到许多研究关注。这种现象的一个明显的原因是相关的困难同时考虑相关的运输和移动业务。
起重机调度问题,相关的研究主要集中在不同的上下文中,例如码头起重机调度问题(QCSP)和院子起重机调度问题(YCSP)集装箱码头来确定一种起重机作业计划提高终端的效率,和起重机调度问题(HSP)电镀线通过优化起重机动作尽量减少生产周期。有丰富的文学各种起重机调度问题。有兴趣的读者可以参考Steenken et al。1],Stahlbock和Voß[2],和Bierwirth Meisel [3)调查的集装箱码头和李et al。4),大厅等。5],Crama et al。6]在HSP调查系统。然而,研究起重机调度的数量在钢卷仓库相对较小。Zapfel和并7)研究一个起重机调度问题的配送中心钢卷存储传入的线圈和检索线圈所要求的客户。问题是视为一个线圈车间调度问题和制定作为一个非线性整数规划模型,很难解决。提出一种基于局部搜索的启发式通过计算和测试。丽et al。8]是一种单一的起重机调度问题来存储和检索钢铁项目与已知的到来和检索日期起重机动作的数量降到最低。项目逐个堆叠起来的另一个类似于容器堆积。提出了基于仿真的启发式来解决这个问题。最相关的问题研究是研究唐et al。9),但是他们提出了一个启发式算法与最坏性能分析不使用遗传算法来解决这个问题。谢et al。10)进一步研究multicrane调度问题在钢卷仓库还没有提出遗传算法。
此外,这里的问题研究问题在仓库和物料搬运活动可能被视为一个仓储运营管理问题。有丰富的文学各种仓储运营管理问题。有兴趣的读者可以参考van den Berg和Zijm11)讨论仓储系统和仓库管理问题的分类和de Koster et al。(12)的研究综述,仓库设计和控制问题。研究这些指令拣选仅涉及从存储区域检索产品针对特定的客户订单。属于防守型中锋,罗森塔尔(13)解决路由的问题订单农户、考虑旅行时间和水平作为一种特殊的旅行商问题(TSP)的情况下,以线性计算时间的通道的数量和选择地点的数量。Ascheuer et al。14)模型选择的路线问题,考虑了水平和垂直旅行时间,作为一个在线不对称TSP。金等。15)使用一个智能基于主体模型解决了订单选择问题有分开存储区域各有一个专门的选择器、和货物存储在多个位置和动态地挑选商品可以选择的位置。彼得森和Aase16)检查选择的影响,存储,使用仿真模型和路由基于配送中心的操作。丽et al。8]介绍了堆垛机的情况下,为客户提供所有项目顺序钢堆放仓库动作的数量降到最低(总交付和重组或改变操作)。彼得森和Aase16)检查选择的影响,存储,使用仿真模型和路由基于配送中心的操作。他们把实体(货物或部分)和资源(存储区域和顺序器)作为智能代理的相互合作,以实现个人和整个系统的目标。然而,这些指令拣选问题不涉及洗牌的决定是一个主要的问题在我们的问题。
研究涉及洗牌活动通常是在集装箱装卸问题。金和香港17)提到一个分支和绑定过程提出了一个启发式确定重组容器的存储位置在检索给定序列的出口集装箱打乱的数量降到最低。Wan et al。18)建立了一个线性整数规划模型容器检索和洗牌问题和提出启发式处理容器动态地存储和检索。y y李和j·李(19)提出了一种三相启发式检索给定序列容器减少的数量的加权和容器运动和起重机的工作时间。考虑到存储配置和序列检索的容器,李和许20.)提出了一个整数规划模型与最小数量的编组premarshalling容器运动所需的容器可以检索后没有洗牌。李和曹国伟(21)解决更大的问题,社区的实例搜索启发式。Avriel et al。22]研究了船舶积载计划问题最小化打乱的数量需要在目的地卸货码头。在更多的聚合级别,Zhang et al。23在院子里)分配存储空间为传入集装箱起重机的工作负载平衡在每个时期不同的块。在我们考虑的问题都有自己的特性使得现有的模型不能直接应用于我们的问题。线圈的堆积是不同的容器或其他公寓项目。这些问题是比我们更容易在线圈放置在栈上的,因此一个线圈可能被要求只有一个线圈。
本文以以下方式组织。问题描述和部分制定2。节3我们开发一个MILP详细描述我们的问题。部分4致力于开发一个遗传算法与最坏的性能分析。计算结果被发表在一节5比较的解决方案与MILP模型和遗传算法。一些结论终于给出了部分6。
2。问题陈述和符号
节,我们统一问题提出的符号是唐et al。9),研究的问题是描述如下。考虑一个仓库区域位置由一个桥式起重机。该地区安排行。每一行最多可以存储两个级别的线圈。上下水平称为水平1和2,分别。有存储位置水平在每一行。很明显,由于特殊的堆积结构。让是所有位置的集合。每个职位可以通过其惟一地识别row-level-position坐标吗。在本文的其余部分,我们可以引用一个使用数字或其坐标位置,哪个更方便。图2显示了一个领域的顶视图大型和小型的圆圈表示线圈在上下位置,分别和一个空圆圈表示一个空位置。成一圈数是那个位置的数量在这一行。
有线圈存储在仓库区域。线圈屈指可数的方式检索所需的组卷和搬到他们指定的地方。为了方便表达,所需线圈也称为目标线圈。让所有屏蔽线圈的集合,让是一组线圈屏蔽目标线圈。然后设置还包括其他线圈。每一个线圈有一个已知的初始存储位置。
进行加载,所需的时间起重机举起或放下一个线圈(这可以很容易地扩展到不同情况下具有和下降时间)。加载动作,大车运行速度沿轨道和沿桥和,分别。同样,空鹤两个方向的速度和,分别。所有的位置都是提前知道,位置之间的距离和在两个方向,和(),也称。然后加载位置之间移动的时间和可以通过计算和一个空的位置之间移动和可以通过计算。在这里,旅游时间满足三角不等式。考虑到一个位置也可以由它的坐标,每个移动时间可以用两种方法表示:。
我们的问题是确定目标的检索序列线圈,并决定屏蔽线圈的位置以最小化的目标应该重组的时间检索所有线圈完成目标。虽然屏蔽线圈可能打乱任何空的位置,为了避免进一步洗牌,我们不允许任何阻止线圈被打乱,阻止另一个目标线圈。
根据他们的位置,目标线圈可以被归类到四类如下所述。一行的侧视图如图3可以帮助理解的分类。图中的网格圈代表目标线圈。
类1。这些线圈位于二级目标(例如,线圈1和5图3)或位于一级而不被其他线圈(如线圈2图3)。让表示线圈在这类的子集。
类2。这些线圈位于一级目标,只有被其他目标线圈(如线圈6在图3)。让表示线圈在这类的子集。
类3所示。这些目标线圈位于低水平,每一个都被一个不属预定目标的线圈(如线圈3被线圈10,线圈7被13日和线圈9被圈在图143)。让在这个类表示线圈的子集,让表示一组线圈的线圈不属预定目标的阻碍。
类4所示。这些目标线圈位于较低的水平,这是被两个不属预定目标的线圈(如线圈4被线圈11和12线圈和线圈8被13和14)。让在这个类表示线圈的子集,让表示一组线圈的线圈屏蔽。
根据上述定义,我们有。注意,一些屏蔽线圈可能阻止两个目标同时线圈,例如,线圈13块两线圈7和8。此外,屏蔽线圈等13和14可能属于两种和。因此,它是可能的。屏蔽线圈的数目是如此。很明显从上面的线圈的分类可以直接检索,在吗也可以直接检索检索后的吗阻止他们。为了检索一个线圈或,线圈屏蔽其他职位需要先打乱。
为方便参考,我们总结所有上面提到的符号符号的部分。一些进一步的符号会在需要的时候被定义之后。
3所示。数学公式
更清楚地提出我们的问题,在本节中,我们继续使用一个混合整数线性规划(MILP)模型提出的唐et al。9]。
3.1。问题参数
3.1.1。输入数据
初始位置的线圈吗()。这些信息我们也可以计算出指标,每= 1,如果线圈的初始位置是或等于0。也就是说,,其他所有。注意,每个是一个已知的参数,而不是一个变量,代表事实是否线圈最初的位置。 目标盘的指定地点吗()。 起重机的初始位置。 正在加载所需的时间从职位定位。 所需的时间是空的从职位定位。 是一个很大的正数。
3.1.2。决策变量
一个有以下:
3.2。数学模型
这个问题可以制定以下模型:
我们的目标(2)在模型中是最小化考。约束(3)保证起重机执行加载一个线圈。约束(4)保证检索每个目标线圈和每个屏蔽线圈的洗牌只执行一次。约束(5)保证,在检索目标线圈,其屏蔽线圈必须重组。约束(6)确保如果阻止线圈是打乱位置(),最初是被另一个线圈,线圈洗牌之前必须搬走了吗。约束(7)保证屏蔽线圈必须只有一个位置。约束(8)确保屏蔽线圈不能打乱位置被其他线圈不动在整个操作。约束(9)确保屏蔽线圈可以打乱一个2级的位置只有下面两个位置被线圈总是存在或被打乱。注意的价值在(9)可以作为位置(最多1)最多只能持有一个线圈。同样,的价值也可以最多1。约束(10)确保屏蔽线圈的洗牌一个一级职位之前必须完成另一个屏蔽线圈是一个位置上面。请注意,最多的一个和在(101)可以,因为线圈只能到一个位置。约束(11)和(12)确保有足够的时间空之间移动的起重机的完成时间加载的开始时间加载。的两组约束的情况下加载是屏蔽线圈和一个目标,分别。约束(13)确保首次加载后才可以开始空鹤到达的起始位置加载的举动。约束(14)和(15)状态,加载的开始和完成时间之间移动,为起重机必须有足够的时间来执行这个动作。加载的两组约束措施阻止线圈,线圈和目标。约束(16)- (18)nonnegativity和二进制变量约束。
注意,问题定义假定每个屏蔽线圈将打乱一个位置,不是阻止其他目标线圈;即屏蔽线圈需要重组过程中只有一次检索所有目标线圈。这是符合什么是在实践中观察到。上述模型在这种假设。模型的扩展,包括每个屏蔽线圈的情况可以打乱不止一次将需要更多的变量来表示屏蔽线圈的位置在每个目标检索线圈。有兴趣的读者被称为Wan et al。18)等建模的方法一个洗牌的问题在集装箱堆场环境中。
4所示。提出了遗传算法和性能分析
因为我们的问题是np难的强烈(见唐et al。9])和解决方案的快速增长与实例的大小仍然MILP的主要缺点,提出遗传算法提供了,相比之下,一个合理的组成的计算负担和解决方案的质量。遗传算法是一个著名的metaheuristic方法的灵感来自于自然进化的生物,同时作用于人口的解决方案。它是一种随机优化技术,它的灵感来自生物科学。特别,它使用的基因决定了任何物种的进化的自然世界。整数字符串用于编码的优化问题和这些字符串组合操作称为复制、交叉、变异,提高这些字符串,使他们“进化”到一个最优或接近最优的解决方案。
4.1。提出的遗传算法
遗传算法(气)已被广泛用于组合优化问题,如排序和调度问题。乔治亚州是一个著名的metaheuristic方法受生物体的自然进化,同时作用于人口的解决方案。探索过程执行通过遗传算子,即交叉,和另一个遗传算子,即突变。这两个进程之间的权衡是由母公司控制的选择和后代接受策略。一个迭代被称为一代。新一代的人得到了个人的前一个通过复制和突变过程。
4.2。遗传操作设计和染色体表示
正如我们所知,GA开始个人和人口的每个解决方案被称为染色体的基因组成代表决策变量。本文演示了使用的染色体表示计划中的每个线圈的基因染色体。决策变量的总数计算中起着重要作用。问题更多的变量需要较长的计算时间。在节中给出的数学公式3决策变量的总数。在报纸上我们定义一个染色体两部分。第一部分表示的顺序打乱线圈和所需的线圈,和第二部分代表打乱位置为每个块相应的线圈。一个遗传算法的染色体编码被描绘成图4。这个染色体代表我们的问题与需要线圈和3卷。显示在第一个染色体的一部分,有六个加载(编号1 - 6)。线圈1、2和3是所需的线圈和线圈4、5、6是打乱的。的第二部分染色体表明空头寸8日9日7是打乱的线圈4、5和6。这条染色体编码方法可以减少决策变量的数量。
4.3。初始解过程
这是一个众所周知的事实,初始种群的结构中扮演着重要的角色在决定效率的气体(戈德堡(24])。然而,大多数文献中采用遗传算法实现随机生成的数量为起始。初始种群生成随机的解决方案,我们认为以下步骤。
步骤1。运输所有线圈属于和与最小,通过选择线圈()作为第一个线圈和左边线圈在任意序列。去一步2。
步骤2。如果有足够的线圈的位置是在不使线圈和被阻塞,洗牌屏蔽线圈一一按照下列原则:选择一个线圈与起重机当前位置最近的距离和转移到最近的位置。别的,去一步3。
一旦所有的屏蔽线圈完全被打乱,然后去一步1。
步骤3。比较两个的距离由(3.1)和(3.2)选择最近的一个来执行。如果两个的距离是相等的,那么选择的线圈线圈在之前。如果没有任何一个线圈的位置请转到步骤1运输电流线圈。一旦所有的线圈运送到指定地点,停止。一个有以下:(3.1)起重机的总距离当前位置的线圈然后对其最近的打乱位置;(3.2)起重机的总距离当前位置的线圈然后到指定的地方。
4.4。算术交叉
重要的是要保持的新生成的后代的可行性问题。因此,我们使用算术交叉(AC)算子来探索解空间和维护的可行性同时新生成的后代。交流产生一个新的后代免费父母如下的线性组合。
后代=×父1 + (父母)×2,在一个时间间隔中是一个随机生成的数字从0到1。因此,每个基因值(即。,allele) in the newly generated offspring is obtained. To increase the effect of the parent with better fitness, we set the parent with better fitness to Parent 1. The AC guarantees that the generated offspring will remain feasible if its parents are feasible. Since values in genes are integer values, the rounded of gene value (offspring) must be considered as a true value.
4.5。父母选择策略
父母选择是重要的调节生殖过程中的偏差。父母选择策略意味着如何选择染色体在当前的人口将为下一代创造后代。一般来说,最好是最好的解决方案在目前这一代有更多的机会被选为父母创造后代。最常见的方法选择机制是“轮盘赌”抽样,每个染色体分配一块圆形轮盘赌和切片的大小正比于染色体的适应度。
4.6。后代接受策略
我们使用semigreedy策略接受遗传算子产生的后代。在这个策略,新一代的后代接受如果其健身小于平均健身其母(s)。这种策略减少了算法的计算时间和导致单调收敛到最优解附近。
4.7。停止规则
我们用两个标准停止规则:(1)经过一代的最大数量,是一种常见的标准和(2)标准差在当前一代染色体的健身价值。这个参数意味着在当前人口多样性的程度或相似的目标函数值。如果这一标准减少低于一个任意常数,说,则算法停止。
4.8。性能分析
让计划来自于遗传算法。一个下界的问题可以从以下两个范围:为方便表达,我们将参考起重机初始位置和线圈之间的距离作为线圈之间的距离和其指定地点和线圈之间的距离和作为。让和。考虑 在哪里。
是最佳的客观价值如果所有需要的线圈吗和。的基本原理是我们考虑最小运输和洗牌时代的总和。
作为一个起重机必须运输所有指定地点所需的线圈和洗牌屏蔽线圈,考取决于起重机执行序列。算法的目的是减少起重机运输和移动距离尽快。由于算法包括所有可能的情况下,我们在以下三个情况下分析最坏性能。
例1 ()。在这种情况下,所有需要的线圈和,我们可以得到最优调度通过应用步骤1算法和客观价值等于最优的客观价值。因此,我们得出
例2 ()。在这种情况下,有足够的屏蔽线圈位置在不使线圈屏蔽。根据步骤2运输之前,所有需要的线圈,我们首先洗牌屏蔽线圈。调度的客观价值不能超过以下表达式,前两项之和最长时间拖着所有的线圈和最后三项之和最短的时间运送所有需要的线圈
例3 ()。在这种情况下,因为没有足够的屏蔽线圈位置在不使线圈阻塞,阻塞线圈可能不止一次。为了尽可能减少洗牌时间,起重机可以洗牌和传输线圈交替。因此,考 完成所有需要的线圈总是满足以下表达式,第一项是起重机的最大时间空从其初始位置,第二和第三项的最大时间洗牌线圈和运输所需的所有线圈,分别和第四项是装卸时间的总和: 一起案件2上方和,我们得到一个坏的结合性能和, 一起案件3上方和,我们得到绑定结合的其他糟糕的性能和, 因此,是最糟糕的性能。
定理1。对于任何时间表我们的遗传算法生成的问题,它提供了最坏性能保证,,, 注意,这个比例仅限潜在的坏的情况下的性能。这个绑定与距离参数。
5。计算实验
为了测试提出了遗传算法的性能,使用的计算实验方法提供的是唐et al。9]。这些方法MILP,顺序的方法,启发式算法,启发式和修改。对于每个问题设置,10个实例被解决的问题。组不同的问题实例生成,每个特点是的行数在存储区域存储位置的数量在每一行的低水平(在上层),空间利用率,目标卷的数量。一端指定地方的可能位置的行(每行的附近位置1)。对于每个实例,是随机生成的从1到指定的地方,他们的位置都是随机选择的潜在的职位。每个目标的指定地点线圈然后随机选择从这些选定的位置。两个相邻位置的距离相同的行(如图2同一行中,两个相邻位置定义为两个各自的位置接触线圈位于同一行)不同级别1和两个相邻行之间的距离是2。装载大车运行速度和空两个方向的移动。举起的时候,送一个线圈。测试的效果与距离无关,我们增加了一倍的价值和解决这个问题实例。相应的结果显示在表的下方1和2。
10小时的时间限制是解决每个实例的MILP设置。以备的期限内没有获得最优解,最可行的解决方案被记录。括号中的数字表示的实例数量的组MILP模型内没有解决最优时间限制。这些算法使用Visual c++实现,运行在一个电脑,一个2.33 GHz奔腾CPU和1 G内存。MILP模型实例的解决PC上使用最大化策略11.0版本使用相同的配置。我们使用下界磅,作为比较的基础解决方案的质量。一个解决方案考的质量是衡量其相对偏差的磅,。
对于大多数较小的情况下,遗传算法可以获得一个最优的解决方案。虽然遗传算法的计算时间稍长一点的启发式算法、GA的ARD小于MILP。随着问题规模或空间利用率增加,遗传算法解决时间问题和空间利用率超过90%(50%)和低(70%)空间利用率。这可能是因为对空间利用率非常高的有更少的空槽慢吞吞的线圈是迭代的数量,空间利用率低,屏蔽线圈越来越少,这也有助于减少搜索时间。
从结果表3,我们可以看到GA继续这一趋势的结果显示较小的问题。随着问题规模的增加,ARD磅稳步增加。因此,看着ARD的趋势表1和3,我们可以看到,GA可能不远的最佳解决方案。GA的ARD非常相似的启发式算法和启发式的修改。遗传算法的计算时间随问题规模。然而,它只需要几分之一秒和100多个目标线圈解决一个问题。甚至800线圈可以解决的问题在半分钟之内。因为在实践中很少有问题的大小,提出了遗传算法能够在很短的时间内产生良好的解决方案。因此他们是适合实际应用。
6。结论
最后,本文的贡献如下。与之前的相关文献不同的是,我们的研究的目的是阐明这个通过一些理论分析实际问题。问题是制定作为一个MILP模型。作为强np困难自然,我们开发生产良好的遗传算法和快速近似实际应用的解决方案。这个算法的性能已经证明有效的和有效的参数相关的一些问题。它提供了一个解决方案提高的起重机和输出的效率生产仓库的钢铁企业。可以使用这些贡献对企业实现更高效的生产力在仓库管理和利用昂贵的设施。
请注意,我们的研究是适合解决单一起重机调度问题所需接线圈在钢铁企业的仓库。进一步的研究可以考虑应用等著名的以人群为基础的metaheuristics迷因算法来解决我们的问题涉及到其他类似的洗牌和重组过程在钢板仓库和集装箱码头而考虑实现细节。
符号
| 仓库区域中的所有职位的数量 | |
| 所有位置的集合 | |
| 在该区域的行数 | |
| 指数的水平;和分别代表了上下的水平 | |
| row-level-position坐标为 | |
| 该地区所有存储卷的数量 | |
| 的一组目标线圈(需要检索和搬到他们指定的地方), | |
| 屏蔽线圈的集合, | |
| 一组线圈屏蔽线圈的目标 | |
| 一组线圈, | |
| 目标子集的线圈位于二级或位于一级但不能被其他线圈 | |
| 目标线圈位于一级的子集,只被其他目标线圈 | |
| 的子集线圈位于一级目标,每一个都是被一个不属预定目标的线圈 | |
| 的不属预定目标的线圈屏蔽线圈 | |
| 的子集线圈位于一级目标,每一个都被两个不属预定目标的线圈 | |
| 线圈的线圈屏蔽的集合 | |
| 所需的时间起重机举起或放下一个线圈 | |
| 和 | 起重机行驶速度跟踪和沿桥,分别 |
| 和 | 空鹤旅行速度沿轨道沿着桥分别 |
| 和 | 位置之间的距离和分别沿轨道和沿桥 |
| 和 | 加载的时间为空移动,移动和位置之间的分别和,,。他们也可以用另一种方式表示:,。 |
利益冲突
作者宣称没有利益冲突有关的出版。
确认
这项研究是由中国国家自然科学基金(批准号71201104)。