英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
一种求解露天矿生产调度问题的新方法的提出
摘 要
露天矿生产计划问题（OPMPSP）包括计划将一个矿藏分成若干较小的段或块，以便使作业的净现值（NPV）达到最大。该问题已被表述为一个整数规划（IP）模型，包括背包和优先约束。然而，由于存在大量的块和优先级限制，该模型在实际规划应用中仍然不切实际。本文提出了一种利用IP模型线性规划松弛的分数解快速生成最优可行（整数）解的新方法。针对实际规模问题，提出了一种快速计算可行LP解的启发式算法。我们的方法在一组学术设计的和真实的矿床上进行了测试，并显示出比文献中用于处理相同矿床的启发式方法更好的性能。有趣的是，所提议的方法改进了大多数实例的最著名的解决方案。
关键词：露天采矿；优先约束背包问题；大容量调度问题；线性规划
目录
介绍
露天采矿是一种开采地表附近矿藏的技术。一个“坑”或洞是在一系列的”推挤”，或阶段，以一个适当的整体角度，以确保坑壁的稳定性。一旦随着深度的增加，清除越来越多的废物的成本超过了处理和销售有价值的材料所获得的收入，从而降低了经济的可能性，最终坑的极限就会达到。在这一点上，可以考虑任何数量的地下采矿技术，这些技术要求在地下挖出隧道，以便于继续开采深层沉积物。
为了规划和调度矿藏的开采，将其分成若干较小的、较易管理的分段或块，这些分段或块包含若干关键属性的估计，包括每个块中有价值物质的数量。组成矿床的所有块体的组合称为块体模型。与每个区块相关的属性通常是通过钻眼数据样本估计的利用地质统计学技术对钻孔间进行插值。块体的大小可以是均匀的，也可以根据矿床的性质而有所不同；然而，它们的尺寸通常与萃取过程中使用的设备的跨度和范围相适应。
含有有价值的矿物和废料的块体在采矿作业的整个生命周期内都被安排好。该战略矿山计划的目标是在满足所有限制条件的同时，使净现值（NPV）最大化。在采矿作业的规划中，主要问题是确定受各种作业限制的块体开采的最佳时间表。这就产生了露天矿生产调度问题（OPMPSP）。
由于提取时要有一个特定的角度，即壁面倾斜角，因此块体的提取过程必须按照每个块体上方的所有对应块体都被移除的顺序进行。这在建模OPMPSP时反映为优先约束。
当在预定的时间范围内安排露天采矿作业中有价值的矿物和废料的开采时，维持资源能力是必不可少的。最大处理能力限制了在每个时间段内发送到加工厂的有价值矿物的数量。矿山的最大生产能力限制了可从每一种矿物中提取的有价值矿物和废料的数量时期。物理限制反映了现场设备能力、运输距离和加工厂的规模。
自20世纪60年代以来，许多研究人员一直致力于解决OPMPSP问题。早期的研究只集中在最终坑极限（UPL）问题上，这是该问题的简化版本，只考虑优先约束（参见Lerchs和Gross-man[[1]]）。OPMPSP随后被Johnson[2[2]]表示为一个整数线性规划（ILP）问题。Johnson使用二进制变量考虑了许多容量约束和优先约束。它们的二进制变量表示由特定时间段发送到特定目的地的特定块的一部分。然而，为了便于实际问题的计算，将原模型转化为一个直观的线性规划模型C-PIT，其中每个block的目的地都是预先确定的[[3]，[4]]。在Eqs中给出了C-PIT的配方。（1a） - （1f）
参数和集合
T={1，...，T} 一组时间段
I={1，hellip;，I} 一组集合
R={1，hellip;R} 资源集
dri 每单位块i消耗的资源量r
Pit 在时间t从块i获得的利润
crt 时间t中可用的资源量thinsp; r
P 问题中所有优先关系的集合
决策变量
x 如果块i被时间段t移除，则为1；否则为0
Max
约束条件：
le; （1b）
（1c）
le; （1d）
isin;{0，1} （1e）
=0 （1f）
在这个公式中，目标函数（1a）寻求最大限度地模拟总NPV。约束（1b）确保在前一个块之前不会提取任何块，约束（1c）确保不会超过容量限制。C-PIT模型的优点之一是，通过使用该模型，可以直接调度块而不是调度工作台阶段，从而实现更精确的调度。然而，即使在这个公式中，由于block的数量庞大，导致决策变量和约束的数量也非常多，使得OPMPSP的求解非常困难。
自20世纪80年代以来，人们开发了许多方法来解决ILP问题。Dagdelen和Johnson[[5]]以及Caccetta[[6]]等人使用拉格朗日参数化方法，放松了采矿和铣削的约束。因此，这个问题可以通过重复任何UPL算法来解决，比如Lerchs和Grossmann[1]开发的Lerchs - grossman算法（LGA）。后来，Caccetta和Hill[[7]]提出了一种分枝定界技术来解决所制定的调度问题。Onur和Dowd[[8]]试图通过将调度问题表示为动态规划来解决这个问题。Boland et al.[[9]]通过使用聚合块来调度提取过程，解决了OPMPSP问题，而在
块模型用于处理决策。作者对考虑块目标的问题进行了更详细的分类。Jelvez等人[[10]]提出了一种基于聚集和分解的方法。
Chicoisne等人[4]开发了一种包括三个步骤的方法。首先用分解法求解了C-PIT的线性规划松弛问题。在求解LP问题后，采用四舍五入启发式（拓扑排序启发式）生成可行解。随后，作者使用局部搜索启发式进一步提高了解决方案的质量。Moreno[[11]]等人还使用相同的分解位置方法和四舍五入启发式处理了非常大的实例，以快速生成非常好的可行解。Liu和Kozan[[12]]最近开发了另一种基于拓扑排序启发式的算法。除了Chicoisne等人[4]开发的求解LPs的技术外，Bienstock和Zuckerberg[[13]]也为此提出了一种分解方法。
Cullenbine等人[[14]]提出了一种结合拉格朗日松弛和滑动时间窗启发式求解OPMPSP二进制规划模型的方法。Lambert和Newman[[15]]也给出了解决相同约束条件下问题的精确方法。利用滑动时间窗启发式算法，给出了一个初始可行解，该解适用于自适应拉格朗日松弛过程。Gaupp[[16]]也考虑到了这些限制。作者开发了一种可变约简技术，可以为每个块生成尽可能早和最新的提取时间。利用这些信息，作者提出了用分枝切割法（Bamp;C）进行特殊切割的方案。Gaupp还利用拉格朗日弛豫的概念，试图减少解的时间。
拓扑排序，或有向无环图（DAG）的拓扑排序，是它的顶点的线性排序，对于从顶点j到顶点k的每条有向边jk， j的顺序在[[17]]的k之前。这一概念在处理不同问题的优先约束时，如资源约束的项目调度问题[ 全文共27960字，剩余内容已隐藏，支付完成后下载完整资料
