英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

基于混合整数规划的猎人谷煤炭链的维修调度

Natashia Boland ·Thomas Kalinowski ·

Hamish Waterer ·Lanbo Zheng

摘要

我们研究了猎人谷煤链的年度维护调度问题。煤炭链是一个由装载点、铁路轨道和不同类型的终端设备组成的系统，以复杂的方式相互作用。必须定期对基础设施的所有部分执行各种维护任务，以确保整个系统的运行。规划这些维护工作的主要目标是最大化年总吞吐量。基于系统的网络流模型，提出了一种混合整数规划方法来解决这一规划问题。为了解决通用求解器不能直接求解的大规模模型问题，提出了两个步骤。通过选择原始问题变量的一个有代表性的子集来减少二进制变量的数量，而滚动地平线方法可以实现长期的近似(即由一系列较短的问题(例如，每月)组成的问题。

关键字：维护调度、煤炭供应链、网络流、混合整数编程

1.介绍

猎人谷煤炭链(HVCC)由矿业公司、铁路运营商、铁路所有者和码头运营商组成，共同组成了世界上最大的煤炭出口设施。2008年，HVCC的吞吐量约为9200万吨，占当年全球煤炭贸易总量的10%以上。煤炭出口业务每年为澳大利亚带来约150亿美元的出口收入。随着近年来需求的显著增长，以及未来需求的进一步增长，高效的供应链管理至关重要。我们的行业合作伙伴Hunter Valley Coal Chain Coordinator Limited (HVCCC)的成立，是为了使所有相关方的利益能够进行整合规划和协调，从而提高整个系统的效率。关于HVCC的更多细节可以在Boland和Savelsbergh(2012)中找到。

在这篇论文中，我们关注的是将煤炭从猎人谷的采矿区一路运输到最终目的地所需的基础设施。煤炭必须通过铁路运到纽卡斯尔港的一个码头，在那里进行组装，最后装船。这条链自然地分成三部分。

1.矿点和码头之间的铁路网络。

2.终端的入站部分。煤在倾卸站从火车上卸下，通过传送带运到堆场，然后堆放在堆场的垫子上。

3.终端的出站部分。煤从堆场中回收，在泊位上装船。

我们讨论了由HVCCC执行的年度维护计划过程。像铁路轨道部分和终端设备这样的供应链部件必须进行定期的预防性和纠正性维护，造成系统容量的重大损失(高达15%)。HVCCC观察到，精心安排维护工作——对它们进行良好的对齐——可以减少维护对网络容量的影响，并建立了一个定期的规划活动来实施它，称为“容量对齐”。目前，计划每年约1500个维修工作的产能调整是一个劳动密集型、主要是手工操作的过程，通过HVCCC和各个运营商之间的反复谈判来实现。过程中需要考虑维护的项目分为三组，分别对应于上述煤链的划分:

1.铁路轨道部分,

2.终端入站，特别是倾卸站和堆垛机

3.码头出港，特别是取料机、装载机和泊位。

HVCCC目前使用在业务规则管理系统中编写的影响计算器来评估建议的维护计划的质量。该计算器是HVCCC容量模型的一个组成部分，该模型是由HVCCC开发的一个软件。对于给定的一组维护活动，它确定三个数字:铁路轨道影响、终端入站影响和终端出站影响。总的系统影响被认为是这三个数字中的最大值。对持续维护的时间间隔进行累加，可以得到整个时间范围内的单个总体影响。通过对终端冲击规则和HVCC输煤系统的深入分析发现，通过解决特定网络中的最大流量问题，可以很好地捕捉这些规则。这些网络中的弧表示不同的终端机器，维护作业只是意味着相应的弧在作业期间不能承载任何流。铁路轨道网在HVCCC冲击计算中得到了非常粗略的表示。基本上，轨道段停运的影响被认为是负荷点L的预期需求(按停运时间比例调整)的总和，其特征是停运阻止列车从L站到终点站之间运行。这是由于铁路网络的树状结构，从每个装载点到每个终点站都有唯一的路线，而且终点站之间距离很近。这意味着只要铁路不成为瓶颈，受影响的负荷点需求之和就确实对应着系统容量的降低。在未来，随着需求的增加，铁路网络将成为一个瓶颈，因此将其建模为一个网络，节点代表节点，弧代表更准确跟踪部分。为系统的所有部分建立网络模型的另一个概念上的优点是，它们可以很容易地连接起来，以捕获不同部分之间的交互。特别是，煤炭链的输入和输出部分之间的链接是我们提出的模型的一个重要特性，这是当前的影响计算中所缺少的。因此，储存场的缓冲功能，也就是煤炭通常停留3到10天的地方，是可以考虑的。这有可能更有效地协调入站和出站停机。

维护工作最初是根据标准设备要求安排的，标准设备要求通常规定在特定时间点执行特定类型的维护工作。最初的时间表是由供应商(轨道所有者和终端运营商)或多或少相互独立制定的。基于此，一个迭代过程开始了，在此过程中，协调器评估进度，为可以重新租用容量的修改制定选项，并与提供者协商这些建议的更改。我们的模型的目的是通过提供一种有效的方法来探索和评估各种不同的重新调度选项来支持这个过程。

我们的论文组织如下。在对相关文献进行简要回顾后，在第四节。2,教派。包含所考虑的维修计划问题的精确定义。这包括底层网络模型、给定的初始维护计划的形式以及优化器必须遵循的重新调度规则。在教派。给出了一个混合整数规划(MIP)公式，并对其进行了分析。5包含两个启发式约简步骤，使问题在计算上易于处理。对两个不同的真实世界数据集的计算结果在节中给出。6、最后一节。7包括结束语和进一步调查的一些指示。

2.文献综述

一般来说，维修是许多生产和运输系统的一项基本活动，在许多情况下占作业费用的一大部分。维护通常分为预防和纠正两类。前者是一种定期的、有计划的活动，而后者是在失败或故障时进行的。第三类称为预测维护，涉及使用测量来预测和诊断设备状况。我们建议读者查阅Sharma等人的著作。(2011)对维护活动及其优化进行概述。在这项工作中，我们关注的是计划预防性维护活动。

许多关于预防性维护的文献涉及到维护策略的确定:多久一次执行每种类型的维护，或在什么条件下进行维护。此外，夏尔马等人的审查。(2011)，我们建议读者参考Budai等人的综述。(2008)，它认识到在规划维修时考虑对生产的影响可以实现的重大优势。本文将这些方法分类为:在维护计划中考虑维护对生产的影响，考虑资源的影响(例如:(人力)维修计划，生产计划服从维修要求。确定了三种研究流:集中于维护活动的成本计算、调查在适当时刻(当故障或其他中断发生时)进行维护的影响的研究、以及根据生产安排维护的研究。(i)维修计划的“成本”是根据其对吞吐量的影响进行评估，并用于比较备选计划;(ii)通过寻求重新安排维护时间(调整时间，在下一段中进一步讨论)，HVCCC寻求将维护安排在与生产相一致的时间内。

在我们的工作中，已经设置了预防性维护策略，这将生成系统所有组件的初始计划。铁路和终端设备的初始维护计划主要由它们相应的维护政策指导。但是，维护策略并不能准确地确定各个维护事件的时间。可以利用一些灵活性来重新安排某些作业的时间，或者调整它们，从而减少维护对系统容量的影响。大多数文献考虑的维修调度与生产的地址维修政策设置。例外发生在发电，当维护中断必须被安排，例如，在Frost和Dechter(1998)。这些主要涉及尽量减少维修和发电的总费用，同时确保发电足以满足需求;相比之下，在我们的上下文中，维护活动的成本是固定的，我们希望最大化系统容量。运输部门也有例外，例如公共汽车或航空公司。这些通常集中在维护的资源含义上，如Haghani和Shafahi(2002)和Keysan等人。(2010)，或关于如何覆盖预定的运输操作，同时仍然满足维护要求，如巴恩哈特等。(1998)。重点是安排运输设备的维护，而不是运输设备所经过的基础设施;后者更符合我们的利益。

轨道和道路维护确实涉及交通基础设施，有许多有趣的研究，特别是在铁路维护方面，如Budai和Dekker(2002)。在这些情况下，重点是尽量减少对预定活动的干扰，而不是尽量增加可以通过的列车数量;后者更接近我们所关心的情况。但也有一些相关的论文:我们讨论了最相关、最近的一篇，即Budai等人的论文。(2006)，详情请参阅下文。

在生产系统中，可能更类似于HVCCC的情况，多部件系统维护似乎是相关的，因为子系统及其维护计划的相互作用产生了对齐的好处。多组件维护模型是指一个系统由多个单元(设备或机器)组成，这些单元(设备或机器)在经济、随机或结构上相互依赖(参见Nicolai和Dekker 2008及其参考文献)。经济依赖集中在维修活动的直接成本上，是否同时对多个机组进行维修可以降低成本。通过规模经济，或者增加规模经济。通过需要雇佣额外的资源。随机相依关系涉及到失效概率，以及这些概率是否与单元相关。例如，当需要维护的部件在内部或连接到其他部件时，结构依赖就会发生，因此为了维护一个部件，其他部件也可能需要维护，或者至少需要拆卸。很明显，后两种类型与HVCCC的情况无关:在这里，故障概率已经在预防性维护策略中被考虑到，而预防性维护策略是被设置的，维护任务之间的任何结构连接都仅仅意味着一个约束，这表明一些维护任务必须被安排在一起。这两种方法都没有解决主要的机制:维护任务的对齐(通过重新计时)可以释放系统中的容量。显然，经济效益是通过释放能力来实现的，因此我们希望在经济依赖下的工作能够解决HVCCC的问题。然而，情况似乎并非如此，所有强调多组件系统中维护调度的经济效益的工作都集中在维护活动本身的直接成本上，而不是随后的生产效益。因此，我们认为第三种经济依赖值得注意，即当将维护任务安排在一起或分开时，会影响系统的生产能力，从而影响可实现的收入。

我们所知道的在我们的上下文中阐明对齐的好处的唯一工作是Budai等人的工作。(2006)铁路轨道维修的预防性调度。在我们的上下文中，维护是在有限的时间范围内计划的。他们认为维护有两种类型:日常工作和项目。前者是循环的，有一定的周期，因此与我们考虑的情况不相似。项目类似:输入数据是维护列表项目，以及每个项目的持续时间，以及项目最早和最迟的启动时间。然而，这些相对较少(对于每种类型，每六个月到一年执行一次)，他们论文的主要贡献是探索项目和日常工作之间的相互作用，这是一个有趣的挑战。他们的目标是最小化轨道占用成本(反映列车时刻表中断)和维护活动的直接成本。在我们的设置中，后者是不相关的，但前者可以被视为轨道容量的代理。他们认识到，通过在同一时间集群作业，轨道占有成本可能会最小化:这个cor-在我们的上下文中响应一种类型的对齐。由于他们的模型集中在网络中的单个链接上，所以不注意其他类型。他们开发了一个整数规划模型，对于他们考虑的问题的规模(3-4年的15种维护类型)，解决时间太长，实际上对于他们2年的随机生成的问题，不到30%的实例在3小时内解决。因此，他们考虑一个有限整数规划和四个启发式，以获得良好的质量解决方案在合理的时间。

在本文中，我们没有循环维护任务，但是我们考虑了整个系统的同时调度，而不是单个链路。最重要的是，时间表的成本不是一个简单的线性函数，如轨道占有成本。相反，由于系统范围的影响，以及子系统在实现系统能力方面的相互依赖，我们需要一个优化模型的解决方案来确定在预定时间内维护任务组合的影响。同样重要的是对时间的处理。布代伊等。(2006)能够使用一个相当粗糙的时间离散化(周)，在他们的模型中只需要100个周期。在我们的上下文中，维护任务的启动时间在某些情况下指定为最接近15分钟(在其他情况下指定为最接近一小时)，持续时间为小时到天。因此，我们需要解决的挑战是如何处理时间而不导致大量的变量。

在Boland等人的一个更抽象的环境中，提出了本工作中考虑的问题的简化版本。(2012 b)。该论文省略了一些复杂的约束具体到煤炭链维护调度，以得出一个问题，可能适用于不同的网络相关的上下文。Boland等人从计算复杂性的角度研究了更简化的特殊情况(具有任意启动时间的单位处理时间作业)。(2012)。与此相反，本文的工作重点是尽可能接近地模拟HVCCC规划者的实际问题，并提出与当前实际相关的解决方案。

总之，我们相信我们的论文对维护优化文献做出了相当独特的贡献。它考虑一个多组件系统，其中可以对组件的维护活动进行调度，从而产生以前没有考虑过的新类型的经济效益。它以一种新的方式利用了生产和维护之间的关系。似乎没有任何工作之前考虑调度维护活动,以最大化系统的生产能力,除非一个人解释最小化跟踪占有轨道维护成本,在这种情况下,我们看到我们进行进一步的新的重大贡献。特别是，维护是全系统计划的，目标是整个系统相互作用的复杂函数，而不是简单的线性函数。此外，当维护任务的持续时间变化很大，并且它们的启动时间相对于计划时间范围很细时，我们为处理此类调度问题提供了见解和想法。

我们希望本文提供的模型和方法有更广泛的适用性之外HVCC:他们可以应用在任何环境中生产合理描述为一个在网络中流动,吞吐量(总产量率)是关键目标是最大化,和日常维护需要预定网络组件。大多数矿业供应链，无论是煤炭、铁矿石还是其他矿物，都符合这种描述。其他大宗商品供应链的应用，如化肥或小麦，也可能成为可能。

3问题描述

在这一部分，我们设置场景。第一个小节包含了底层网络的细节，第二个小节介绍了实际的调度问题。

3.1网络模型

代表HVCC的网络包括铁路轨道和终端的子网:

1.铁路轨道网有荷载点和节点，弧段表示铁路轨道段。

2.有两个终端网络，其弧对应于终端设备。

整个网络如图所示。1.椭圆表示终端，其外部为铁路网，其中方形节点表示节点，圆形节点表示荷载点。加载点节点如图所示。1只是为了说明。在实际模型中，它们被标识为形成一个单一的源节点，对于每个负载点，都有一个对应的弧将源与相应的节点连接起来。这些负荷点弧的能力是需求预

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[239254]，资料为PDF文档或Word文档，PDF文档可免费转换为Word