英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
基于机器可用性约束的车间作业调度问题求解算法
Kanate Ploydanai 泰国农业大学工程学院工业工程系，曼谷，泰国
Anan Mungwattana 泰国农业大学工程学院工业工程系，曼谷，泰国
摘要
一般情况下，一般作业车间调度问题假定机器的工作时间是相等的，例如每天八小时。然而，在实际的工厂，这些工作时间是不同的，因为机器可能有不同的运转速度，或者他们可能需要维护。也就是说，一台机器可能只需要进行半天操作，而其他机器可能必须为整个一天工作。所以，每台机器都有自己的工作时间窗口。在本文中，这种类型的问题被称为作为一个车间作业调度问题的机器可用性约束，这是基于比典型的作业车间调度问题更复杂的问踢的基础上。在以往的研究中，之前这种类型的问题已经很少调查。因此，开发一种基于非延迟调度的新算法，算法通过增加机器的可用性约束求解作业车间调度问题来最小化最大完工时间。利用机器可用性约束假设新开发的算法更现实。这项研究揭示的算法的结果认为机器的可用性约束的算法用于实际问题时，忽略了机器的可用性约束。
关键字：作业车间调度算法；启发式算法；优化；非延迟调度；机器可用性约束
一．简介
求解车间作业调度问题的算法是优化领域中的一个热门研究课题。众所周知，车间调度问题是NP很难的。这意味着当问题的规模增长，确定问题的最优解的时间呈指数级增长。
通常情况下，有M台机床和N个岗位去调度。这些工作必须利用不同的路线或次序去处理这些机器。因此，调度的复杂性取决于关于机器的数量，岗位的数量和岗位次序。每台机器上的顺序岗位有N! 种方法（解）。对于某些类型的调度问题，所有的机器使用类似的序列。因此，从可行的解决方案中找到最佳的解决方案的数量是N!个。对于作业车间调度问题，每台机器都有不同的序列，因此，可行的解决方案的数量增加到个解决方案。
解决作业车间调度问题的很多研究会开发算法。In-Chan Choi的目的是开发本地搜索算法解决车间作业调度问题。目标函数极小化。序列相关的设置条件被添加到这个问题。每个作业的设置时间取决于每个机器的工作顺序。本文用局部搜索算法解决了这个问题。本地搜索算法有助于减少计算时间。D.A. koonce 利用数据挖掘技术来开发作业车间调度问题的调度模式。提出这项工作是为了应用数据挖掘方法去探索新模式。问题的目标是最小化完工时间。遗传算法可用来产生良好的解决方案。数据挖掘是用来寻找序列的关系，并预测下一步的工作序列。数据挖掘的结果可以用来总结新的调度规则，显示遗传算法的结果。Chandrasekharan 提出了三个新的动态流水线和作业车间调度问题的调度规则。与13个调度规则比较规则的性能。案例研究是从模拟研究流水车间调度问题开始。通过随机路径的工作，重新修改调度问题，将问题转化为作业车间调度问题。这项研究可以得出结论，调度规则的性能影响工作和车间配置路径。Hiroshi 用移动瓶颈法求解作业车间调度问题。问题的目标是最小化总持有成本。该问题的具体约束条件是添加没有延迟的作业约束。实验表明，移动瓶颈过程可以减少计算时间。安东尼提出了一个具有时间滞后的作业车间Memmetic算法。时间滞后意味着操作开始时间的最小和最大化。
本文提出的框架来解决作业车间调度问题是基于析取图修改问题，利用Memmetic算法来求解。扬森解决了在假设条件下工件具有可控加工时间的作业车间调度问题。这意味着他可以通过支付一定的费用来减少工作的时间。扬森提出了2个模型。第一是连续模型，另一个是减少模型。可以证明的是，在多项式时间内，他们可以用多项式时间近似的方法来解决问题，并且在数量上是固定的。研究最小化完工时间的作业车间调度问题。古奈特利用工作优先约束问题减少车间流水问题。之后，利用约翰逊的规则扩展定义解决这个问题。
此外，他指出，延长约翰逊规则的最优性证明了解决2台机器的作业车间问题的一些方法对三和四机器一样有效。Drobouchevitch 提出了两种启发式求解作业车间调度问题的特殊情况。案例基于假设每个岗位由最多两个操作构成，其中一个在M台机床中的一台上加工。当其他的操作必须同时在一个单一的瓶颈机器上执行。两个启发之一保证了最坏的情况下的性能比3/2。此外，他指出，这些技术可以应用到相关的问题，如流水车间调度问题的并行机。Ganesen 求解作业车间调度问题的特殊情况。最小方差（CTV）比赛时间约束的问题。下界的CTV开发问题。为了解决这个问题，负向的调度方法被使用。为了显示性能负向的调度方法，将结果与正向调度方法进行了比较。这项研究表明，负向的调度方法应用于这种特殊情况下的作业车间调度问题。另外2层技术是解决作业车间调度问题的一种技术。Pan描述二元混合整数规划为折返作业车间调度问题，利用两层技术Ganesen [ 12 ]研究了作业车间调度问题的两目标解决问题。第一是最小化总完工时间的绝对差，另一个是平均流动时间。对负向调度技术进行了研究。此外，他采用了静态优化技术。
在这项研究中，82个问题被带去研究。结果是一个新的基准问题。Pham解决作业车间调度问题，即多模式封锁作业车间调度问题的特殊情况。问题是从医院的医院资源，以分配的手术病例。CPLEX被利用去求解问题。由于计算时间的限制，该模型是能够解决小和中等大小的问题。这是研究所建议的。
其他研究的元启发式。Watanabe和Koonce用遗传算法求解作业车间调度问题。Ganesen用模拟退火算法求解作业车间调度问题。一些研究利用神经网络选择调度规则。一些研究解决了双元启发式算法之间的混合算法的作业车间调度。
本文重点研究开发的算法来解决车间作业调度问题。该算法的设计考虑机器的可用性约束。下一节介绍问题的细节和问题的数学模型。接下来，讲解机器可用性约束的描述。机器的可用性约束是用来计算来处理时间断裂时期工厂的现实问题。
二．问题陈述和数学公式
在前一节中，我们回顾了用于解决作业车间调度问题的算法。本节介绍了一般作业车间调度的数学模型和机器可用性约束的细节。在一般情况下，变量如下：
让成为工作j在机器i上执行开始时间，
让成为工作j在机器i上执行完成时间，
让成为工作j在机器i上机加工时间，
让Cmax成为完工时间（最新的工作完成时间）。
问题的目标是最小化完工时间。没有机器可用性约束的作业车间调度问题的数学模型在下面显示。
为了确保在机器h上的j工作的下一步的工作开始于在机器i上的j工作上的步骤结束之后，方程2被调用。接下来，方程3保证Cmax必须超过的最后工作完成时间。方程4用于在机器上进行排序作业。这个方程意味着只有一个工作在某一个时间只有一个机器可以运转。通过使用公式5，过程的开始时间是非负的。一些时间，一些问题需要工作条件发布时间。方程6确保工作必须在发布时间后开始。最后一个约束来控制工作必须在到期日期前完成。
数学模型是一般的作业车间调度问题，但基于机器可用性约束的作业车间调度问题更为复杂。此外，我们开发了程序去计算完成过程时间和完工时间。
让
alpha; 成为工作日类型指标
Beta; 成为中断期指标
成为在工作日的 alpha;类型beta;时期停机的时间
成为在工作日的 alpha;类型beta;时期开机的时间。
工厂有很多工作日类型。本文建议保持工作时间的信息，利用和通过alpha;作为工作日类型的指标，Beta;作为破损期工作日类型的指标。例如，工作日类型1有2个破裂期。第一个破裂时期是午餐时间（下午十二点和下午一点）。第二中断期下午4:00至明天8:00。这意味着等于下午4：00和等于上午8:00。案例二中断期超过，意味着是一天的时间。另一方面，如果小于小于 ，则和是同一天。
事实上，这部分介绍了一般作业车间调度的数学模型，并简要介绍了机器可用性约束。车间调度与机器可用性约束是一个特殊的问题。在下一节中，我们提出了非延迟调度算法。对于特殊情况下的问题，我们提出了一个算法来计算完成时间与机器可用性约束。利用机器可用性约束名称工作时间窗算法来计算作业时间。
三．作业车间调度问题的算法
在这一节中，我们提出了一个非延迟调度算法（NSA），工作时间窗口算法（STA），和非延迟调度算法和工作时间窗口算法的结合算法。我们把新算法称之为非工作时间窗延迟调度算法（WT-NSA）。
首先，NSA算法被提出。NSA使用一台机器从来没有空闲时，它的队列不是空的概念。该算法所需的计算时间可以是最小的。对于M台机器和N个工作，它花费了MN计算时间来解决这个问题。该算法的解决方案，然而，不是最佳的解决方案。尽管如此，这个问题是NP-难的。最佳的解决方案可能不可能在短时间内确定。
A.非延迟调度算法
NSA的程序是计算所有工作时间的所有列表中的工作。接下来，选择最早完成的操作。然后，可以将处理的操作更新到列表中，并且在选定所有操作之前，同样的过程将继续进行。
B.工作时间窗口
在这一节中，我们提出了一种算法，用于计算机器可用性约束的时间。这很适合有许多机器，许多工作，和几个中断时期的工厂。该算法被称为工作时间窗算法。
工作日包括工作期和中断期。工作周期是在机器上工作的时间。中断期是停止运行的时间段。
如果中断期之间不发生在操作时间，完成时间等于操作开始时间加上处理时间。否则，如果部分中断期是在运行时间，完成时间被补偿。
所开发的算法是递归算法。算法调用自己，直到完成的时间被完整地计算。例如，为了迭代，算法检查中断周期，并进行补偿。有时，一个操作不能处理一天。算法称为一次重新计算。
首先，结束时间近似优于开始时间和处理时间。（）被认为是下一个中断周期信息。该算法集设置beta;为第一个中断周期的操作开始时间和结束时间之间。b1、b2和b3，b4被设置成识别中断周期状态用来弥补。之后，我们用if-then结构计算完成时间的作业。最后，如果作业的完成时间是工作日结束的话，则算法再次调用它自己。迭代一直发生，直到完成作业操作的时间少于当前工作日结束。
此外，本文提出了工作时间窗口算法和瞬发的调度算法和工作时间窗口算法的混合算法。混合算法称为WT-NSA。这种混合算法类似于NSA，但它是不同于WT-NSA地，我们修改了程序计算的工作操作完成时间。
算法2显示了WT-NSA的细节。首先，如果在这个时候准备操作，算法计算每个作业的所有操作的完成时间。下一步，该算法检查和重新计算完成时间的工作时间窗口算法。这一步是新的添加到算法中使用的具体问题。
此外，选择最早开始时间的操作。如果很多工作都有相同的开始时间，算法选择最早完成时间的操作。此外，算法更新准备在机器上加工的操作。当操作时间变化时候，所选择的操作被记录在更新完成时间的序列中。迭代开始运行，直到所有作业完成为止。
四．实验
40个案例用于实验来说明WT-NSA算法适用于车间调度问题。所有案例几乎都是来自互联网的。处理时间在零和一百之间。
首先使用非延迟调度算法。之后，当我们使用的解决方案，从算法上不考虑机器可用性约束的问题时，我们据此调查解决方案的影响力。三项作业时间的实验显示
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[147928]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
