英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
考虑等待时间和运输能力的
炼钢和精炼协同调度问题
摘要：这篇文献探索了位于一个炼钢车间中的制造和物流之间的联合调度问题。考虑了两个产生于炼钢和精炼工序的模型。第一个模型假定炼钢工序中有一个转换器，精炼工序则有一个熔炉。一个容量为一的运输机器被用于在转换器好熔炉之间运输工件。优化目标是最小化最大完工时间。在这个模型中，我们提供了一种最坏情况性能比为2的算法并展示了计算结果。第二个模型考虑了更加实际的情况，首先工件在相同的并行转换器中被加工，然后来自于同一个转换器的工件被一个容量为1的专用手推车运输到下一道工序。第二个模型考虑了两种优化目标。第一个目标是在满足等待时间约束的情况下最小化最大完工时间、闲置时间惩罚值以及等待时间惩罚值的总和。另一个是在满足等待时间约束的情况下最小化最大完工时间、闲置时间惩罚值和与等待时间关联的热消耗惩罚值的总和。在这个模型中，我们提出了一种禁忌搜索算法，提供了计算结果和最坏情况分析。
关键词：调度、运输、热损耗、最坏情况分析、数学模型、禁忌搜索
1 背景介绍
我们的问题产生于炼钢车间的炼钢—精炼子系统。一个转换器被充满后被称为一个“炉次”，在这个调度中相当于一个“工件”，并且已经包含了主要的合金化元素。填充工作可以在任一个转换器中进行，因为他们是功能相同的并行机。一旦在并行机中的工序结束，融化的金属会被倒入钢包中，首先被并行机后的手推车运送，然后被起重机提升到电车铁路的铁轨上运输到精炼炉。下一步是精炼，应根据添加到并行转换器中的合金元素的不同采取不同的处理方式。如果新的炉次已经被转运到精炼炉，而炉中的炉次还未完成加工，则新的炉次必须等待精炼炉闲置，因此产生了等待时间，等待过程中不会占用起重机。通常，炉次在精炼工序前的等待时间不应该太长。如果一个炉次在转换器中加工结束后没有可用的手推车，那么该炉次的开始加工时间必须被推迟，因此出现了转换器的闲置时间。另一种会令转换器出现闲置时间的情况是炉次在无等待要求（实则应该是等待时间不应太长）下在精炼炉前出现了太长的等待时间，如图1，图2中所示。
图1 考虑运输的从转换器到精炼炉的charge流动
图2 四炉次的包含运输的炼钢-精炼流程的甘特图
从实际情况中抽取出了两个问题。假设只有一个转换器，一个手推车和一个精炼炉，等待时间限制无限长，那么该问题可以被抽象为一个有半成品约束的两台机器的flowshop问题。如果考虑所有的转换器，手推车和精炼炉，等待时间是有限长约束，则可以把问题抽象为一个需要满足等待时间约束的考虑半成品运输的两阶段生产调度问题。
在考虑半成品工件的两台机器的flowshop问题中，一个工件在第一台机器上完成加工后必须马上被一个运量为1的运输设备运送到第二天机器上去以便于进行之后的加工。在满足等待时间约束的考虑半成品工件运输问题的两阶段调度问题中，一个工件在阶段一可以被并行机中的任意一台机器加工，在第二阶段中则必须被制定的机器加工。因此，工件根据第二阶段的加工机器被划分为了不同的类型。有一个运量为1的运输设备在每一台并行机的后面，负责将半成品工件从第一阶段中的机器配送至第二阶段的对应机器。第一阶段后的缓冲能力为零，第二阶段之前的缓冲能力无限大。因此，半成品工件应该在第一阶段完工后立即被配送至下一个工序，若下游的机器不可用，则在满足等待时间约束的条件下应被存储在第二阶段之前的缓冲空间中。
在炼钢—精炼制造过程中要被调度的工件是热的流体，因此生产流程要求细致而准确的计划以满足实际生产的约束和要求。否则，将会存在大量的热量损失，甚至可能使得工件不能继续进行下一步生产。
我们问题的特殊性可以遵循下述说明：第一，我们考虑生产和调度之间的协同调度问题。第二，我们考虑运输时间和运输能力对生产带来的影响。最后，我们通过对转换器的闲置时间以及精炼炉前的热量消耗惩罚值或等待时间惩罚值求和来计算生产和运输之间的热量损失。
许多文献致力于研究不含运输能力约束的两阶段生产调度问题。Su，Chou，和Ting（2005）研究了第一阶段是flowshop，第二阶段是openshop的两阶段加工问题。Sung和Kim（2002）年研究了两台机器的flowshop调度问题，其中第一台机机器是离散加工机器，第二台机器是批量加工机器，且工件在第一台机器上的到达是动态的。Sung和Min（2001）研究了考虑不同机器序列的两台机器的flowshop调度问题，加工方式包括批量到离散，批量到批量和离散到批量。Chu（2006）提出了一种时间复杂度为的算法来解决2循环相同工件的无等待的机械化flowshop调度问题，每个循环中分别有两个工件进入和离开生产线。Tang，Liu，Rong和Yang（2000）研究了产生于连续炼钢铸造的两阶段调度问题。
众所周知，最早的明确考虑到运输问题的调度文献是Maggu，Das和Kumar（1981）和Maggu，Singhal，Mohammad和Yadav（1982）发表的。Lee和Chen（2001）研究了flowshop和并行机环境下的半成品工件和完工工件配送的调度问题，该研究考虑了运输机器的运量和运输时间。Change和Lee（2004）研究了最小化最大完工时间的包含成品配送的调度问题，讨论了三种情况：第一，工件都在同一台机器中加工，然后被运输机配送给客户；第二，工件在并行机中加工，然后被运输机配送给客户；第三，工件在同一台机器中被加工，然后被运输机配送给两名客户。Allaoui和Artiba（2004）研究了考虑定期检修并包含了运输时间的混合flowshop调度问题。Hurink和Knust（2001）研究了考虑运输时间的m台机器的flowshop调度问题。Chen（1996）研究了考虑批量配送费送和交货期约束的单机调度问题。Li，Vairaktarakis和Lee（2005）研究了整合配送车辆路径选择的单机调度问题，问题中有多位客户作为配送目标。Li，Ganesan和Sivakumar（2006）研究了消费电子行业生产后的运输成本。Shen和Honda（2007）研究了三个三级供应链系统中的运输路径。Wangle和Cheng（2000）研究了考虑配送费用的并行机调度问题。Brucker，Knust，Cheng和Shakhlevich（2004）研究了open-shop问题。
大多数关于提升机的文献来源于电镀系统。比如Zhou和Li（2003）以最小化循环时间为目标，研究了多个罐体单个提升机的循环调度问题。Chen，Chu和Proth研究了源于印刷电路板电镀工厂的包含时间窗约束的最优化循环提升机调度计划问题。Che和Chu（2005）研究了包含再进线操作的无等待电镀生产线的单个循环提升机调度问题。Lin和Jiang（2005）给出了一个多项式算法，用于解决有恒定罐体处理时间的电镀系统中有两台提升机且无等待循环调度问题。Jeacute;gou，Kim，Baptiste和 Lee（2006）解决了多个提升机在一个拥有两个不同的多中介系统的轨道上运行的问题。也有文献研究来自于码头运物流运输的提升机运行问题。Lim，Rodrigues和Xu（2007）研究了来自于码头货运的提升机平行移动调度问题。Tanizaki，Tamura，Sakai，Takahashi和Imai（2006）研究了有关提升机运输的炼钢企业调度问题，但未等待时间约束和热量损耗。
本文，我们研究了第一阶段包含并行机，第二阶段有专用机器的两阶段生产问题，这与之前所研究的两阶段生产问题中的机器环境都有所不同。更多的，两阶段生产中的运输时间和运输能力也被同时考虑，与其他文献中考虑运输的传统机器环境不同。至于运输，我们研究了运输时间而非手推车和吊装机器的路径，因此没有考虑所涉及的运输器械的路径细节。吊装机的运输时间和手推车运输时间的关联性核销，并且吊装机的数量足够，因此吊装机的调度被省略了。本文所做出的贡献可以被归纳如下。对于一个考虑半成品的两台机器的flowshop调度问题提供了一种2-近似算法。对于包含等待时间限制的两阶段调度问题，提供了一种禁忌搜索算法以及它的最坏情况分析。
本文的剩余部分的按下述方式组织：在章节二，我们研究了一个考虑半成品的两台机器的flowshop调度问题。在章节三，研究了有运输系统和等待时间约束的两阶段生产调度问题。一些结论性论述记录在章节四中。
2 考虑半成品工件运输时间的两台机器的flowshop问题
在研究考虑半成品运输的炼钢和精炼调度问题之前，我们首先关注最简单的情形，只有一台转换器，一台手推车和一台精炼炉，惩罚系数为零且没有等待时间约束。因此，问题变成了考虑半成品工件运输时间的两台机器的flowshop问题，优化目标为最小化加工时间。在这种最简单的情景下，我们提供一个近似算法并检验它的效果。
2.1 问题描述
最简单的情形可以被描述如下：零时刻有一组个工件正准备进入一个两台机器的flowshop系统中加工。表示工件在第一台机器上的加工时间，而表示工件在第二天机器上的加工时间，。有一台运量为1的运输机器负责在两台机器之间运输半成品。运输时间与工件无关，表示从第一台机器将半成品运往第二台机器所需要花费的时间，表示运输机器的返程时间。调度决策是在加工机器和运输工具间找到一个工件序列。目标是最小化最大完工时间。
使用常规表示法，这个问题可以被描述为，该问题已经被Lee和Chen（2001）证明是一个强NP-hard问题，即便运输时间。以下结果约束了及其中的加工顺序和这个问题的运输顺序。我们参考Lee和Chen（2001）作为证明。
性质1. 当工件在第一台机器中的加工顺序和被运输机运送到相应的第二台机器上的加工顺序相同时存在一个最优的调度计划。
Lee和Chen（2001）证明了这个问题是一个强NP-hard问题，但并未给出近似算法。他们证明出在那些问题中的工件必须按顺序排列。在下一节中，我们提供一个该问题的近似算法。算法的质量会通过理论和计算测试的方式展现。
2.2 近似算法
在接下来的部分中，我们提出一个有效的启发式算法来解决考虑半成品工件运输问题的两台机器的flowshop问题，该算法假设所有工件在两台机器上都按照排列顺序加工。
算法1.
第一步：把工件分成两组，组Ⅰ的工件满足条件，组Ⅱ的工件满足。第一组里的工件先加工，然后加工第二组的工件。
第二步：以的非递增方式排列组Ⅰ的工件（工序时间最长的工件排在第一个位置），然后将位置的满足的工件和第一个位置的工件交换位置，是排列对应于最小函数值，。
第三步：将和应用于Johnson法则来排序组Ⅱ中的工件。
第四步：对于步骤1-3中得到的序列，将满足条件的位置和位置的工件交换位置，（满足SPT规则，即一阶最小处理时间），若减缓可以减少目标函数时间则进行该操作。
第五步：对于步骤1-4中得到的序列，将满足条件的位置和位置的工件交换位置，（满足LPT规则，即一阶最大处理时间），若减缓可以减少目标函数时间则进行该操作。
2.3 下界
使两台机器的flowshop问题变成。我们从以下三种启发式算法中得到下界：
启发式算法1：假设，因此我们可以使用Jhonsn规则处理该问题。将对应的值记为。
启发式算法2：假设，因此这个问题的工件序列可以按照非降序排列（SPT规则）。将对应的值记为。
启发式算法3：假设，因此这个问题的工件序列可以按照非升序排列（LPT规则）。将对应的值记为。
定理1. 原问题的下界可以通过表达式得到，而分别是启发式算法得到的制造时间。
2.4 最坏情况分析
记算法1得到的制造时间为，记理论最优解的制造周期为。下面的定理为算法1提供了性能保证。
定理2. 算法1最坏情况的性能比一定小于等于2，即。
证明. 记为第一个机器的最小加工时间，记为第二个机器的最小加工时间。
如果即第二台机器的加工时间不比运输时间短，则我们可以得到如下结果：
（1）
（2）
（3）
由此可以推导出
（4）
同样地
（5）
因此
（6）
接下来的部分，我们将说明对于满足的问题最坏情况的性能比肯定会小于等于2。定义为使用（一阶最小加工时间）进行非降序排列后的队列中，在被加工后可以马上运输的第一个工件，。很明显，使用算法1得到的函数值不会比使用进行非降序排列后的工件队列的加工时间长。如果，我们可以得到最坏情况的性能比。我们知道：
（7）
因而可推导出
（8）
同样地，
（9）
明显有
（10）
因此，我们知道
（11）
注意到最坏的情形中算法的性能比可以达到，如果，则当很大时，性能比将会趋近于。
即使适用于某个工件，，即，某个工件在第二台机器上的加工时间比运输时间短，我们依然可以得到结论。
记为以为对象使用规则得到的队列的目标函数值，而为以为对象使用规则得到的队列的目标函数值。和都可以通过观察算法1
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238668]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
