英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
附录A 外文参考文献(译文)
作业车间调度问题综述
A. Arisha, P. Young, 和 M. A. ELBaradie
都柏林城市大学机械制造工程学院
摘要
作业车间调度是一项重要的工业活动，尤其是在制造计划中.问题的复杂性随着操作和产品组合的复杂性的增加而增加。为了解决这一问题，已经开发了许多结合离散事件仿真方法的方法。本文的范围和目的是提出一份涵盖了JSS问题的大部分求解技术的报告。对这些技术提出了分类：传统技术和先进技术。解决JSS问题的传统技术不能完全满足全球竞争和快速变化的客户需求。仿真和人工智能(AI)已被证明是解决一般的调度问题、特别是JSS问题的极好的战略工具。本文定义了制造系统所使用的人工智能技术。最后，对未来的发展趋势进行了简要的展望。
关键词：作业车间调度，仿真，人工智能，智能调度
1 介绍
在过去的十年中对调度的研究，特别是在其最常见的工业形式的作业车间调度上，由于工业的需求，变得越来越重要。虽然在学术战线上取得了很大进展，对于技术转让以适应现代化生产设施的灵活性要求仍然存在疑问。作业车间调度在文献中受到了很大的关注，由于满足批量生产和连续生产的矛盾需求的解决方案变得更加困难。在过去的研究中，有相当数量的对机器调度问题的研究，希望找到最优解或者甚至接近于复杂问题的最优解。
对相当数量的分析技术如线性规划、分枝界限法或启发式方法，如优先级规则和邻域方法进行了研究。
近年来，大多数的研究转向了处理新的求解技术，如仿真和人工智能技术。这些方法以较小的计算量和更强大的结果证明了在解决JSS问题方面迈出了重要的一步。鉴于此，本文对这些新技术进行了简要的概括，介绍了以前为调查和解决JSS问题而开展的工作。最后，将讨论今后在提供有效的JSS工具方面的趋势。
2 问题定义
考虑一个工作是由机器处理的车间。每个作业由一定数量的操作组成。每个操作都必须由专用机器执行并且需要预定义处理时间。操作顺序由生产配方中的每个作业规定，对调度施加静态约束。因此，每个作业都有自己的机器顺序，并且两个作业中任何一个的机器订单之间都不存在任何关系。
在JSS问题中，设定#39;n#39;个工作为J1, J2, J3, hellip; Jn必须在#39;m#39;个不同机器M1, M2, M3, hellip; Mm每项工作由一系列按特定顺序排定的操作( Oj1, Oj2, Oj3,hellip;.., Ojmj)组成。
此外，每个操作只能由#39;m#39;可用的机器中的一台进行处理。操作#39;Ojk#39;的处理时间为#39;Pjk#39;。目的是为每个机器找到一个操作序列。使作业完成时间的某一特定功能最小化，并使两个操作任何时候都不会在同一台机器上被处理。
对不同的调度问题及其算法和复杂性进行了详尽的调查。
3 问题的性质
近几十年来，为了解决JSS问题，人们开展了大量的研究，包括对调度问题的全面研究。调度问题最初是在50年代中期约翰逊(1954)发表的一篇论文的公司提出的。
文章讨论了当所有工件的处理时间均由指数分布导出时，2台机器上n个工件的期望完成时间最小的方法。
基本的JSS问题是一个优化问题。它可以根据生产计划的信息分为静态的或动态的，确定性的或随机的。
4 调度问题的求解技巧
在过去的20多年里，研究人员开发了几种技术来处理调度问题。这些技术可按以下几个标题分组：传统技术和先进技术。
4.1.传统技术
传统技术可被分为分析技术和启发式技术两大类。
如文章所述，LEKIN软件是作为一种工具设计的，其主要目的是介绍主要的调度理论和展示几种传统技术的能力。表(1)和(2)分别简要介绍了用于处理JSS问题的主要分析和启发式技术。
表1：分析技术
|
主要特点 |
局限性 |
|
|
1. 显式枚举 - 在这种方法中，它们生成一个完整的枚举树。树的叶子代表了所有可行的解决方案。从根到叶最小距离的路径表示最优解。. - 提出了一种算法，该算法针对析取弧创建了一个主动调度。 - 一种在386 PC机上，16 MHz，耗时2.5小时的处理最优作业顺序的计算机程序算法。 |
- 剩下的困难是生成搜索树的大小。因为我们有最大的(n!) m个解要考虑。 - 算法的局限性在于它提出在建立调度之前无法确定过程关系。此外，在每种情况下都不足以捕获序列相关的设置和拆卸时间(White等人，1990)。 |
|
|
2. 隐枚举 - 隐枚举的策略尝试在不考虑每一个可能的解决方案的情况下，尽量最小化目标函数。隐式枚举格式检查越来越小的可行解子集直到这些子集绝对不包含改进的解决方案为止。 |
- 当他们被多个资源测试时，所有确定最优时间表的隐式枚举方法似乎都容易受到这些问题的组合性质的影响（超过50项活动）。 |
|
|
2.1. 分支定界 - 分支和定界算法从枚举树中削减分支，从而大大减少生成节点的数量。通过系统地研究可行解的子集，可以找到最优解。 - JSS有几种不同的算法，并已应用于流水调度和分支定界方法综述. |
- 该算法的局限性在于，完工时间是该算法唯一可以评价的标准。 - 该技术的效率在很大程度上取决于下限的效率。边界越有效，需要执行的方案树的枚举量就越小。 - 列举这组简化的备选方案也是不切实际的，因为它太大了。 |
|
|
2.2. 分支和支配 - 类似于分支和边界，但在修剪方法上有所不同。如果某个节点存在一组条件，这意味着该调度不如其他节点的最佳调度，可在进一步考虑中删除第一节点。这样，第二节点控制第一节点。 |
- 使用优势条件可以充分缩短搜索，从减少总的计算需求的。枚举这个简化的集合仍然是不切实际的。 |
|
|
3.部分计数 -已证明最优时间表总是在一个可行时间表的子集中，称为'活动'。这种对这些可行的现行时间表的识别已经被使用。最近，移位瓶颈算法被认为是局部枚举的一个很好的步骤。 |
- 这种定义活动和半活动计划的方法有助于在一定程度上减少计算量.然而，仍然需要产生大量的计划才能得到最佳的时间表。问题复杂性随着机器和作业的增加而增加。 |
|
- 从建立模型的角度来看，线性规划的特别吸引之处在于，可以使用高效的程序代码来处理涉及多个变量和约束的非常大的问题。 - 可以公平地说，在某些情况下，问题的具体性质允许某些简化近似，从而允许用线性规划求解。 |
- 线性规划通常可以作为一种实用技术使用，但只有当问题完全符合该方法的要求时才行。 - 主要的缺点是大多数实际的制造计划和调度在大多数情况下都不是线性的，即使在简化之后也是如此。 - 此外，实践中的一些或大部分约束不能表示为线性约束。例如，一个示范是可以使用机器A或B来处理作业j。 |
|
|
5.整数规划 - 为了克服线性规划的一些局限性，可以使用整数变量。这种复杂的解决方案需要使用效率较低的算法。文章介绍了JSS问题的整数规划公式。 |
- 现有的整数规划计算即使是非常小的JSS问题，公式也是过大的.即使考虑到整数规划计算中的可能发展和改进，它也是不可能作为解决JSS问题的一般方法的。 |
表2：启发式技术
|
主要特点 |
局限性 |
|
|
1.增量调度 - 增量调度从一个空的时间表和一组要调度的任务开始构建。增量调度的基本思想是选择下一个要调度的任务，并将其放置在在时间线上执行任务，这样就不会违反任何限制。布局算法试图进行某种程度的优化，可能非常简单，也可能非常复杂，。 - 此过程会重复执行，直到所有任务都已排定为止，或者仍然有一些任务需要调度，但没有时间。在后一种情况下，调度程序实际上已经到达了死胡同。 |
有些系统在这个死胡同处停止运行，给用户提供了一个不完整的解决方案.另一些人则试图通过取消先前做出的一些决定，将调度程序从死胡同条件中解放出来。增量调度可以退化为蛮力的试错搜索。由于这是一种计算困难的替代方案，所以增量调度系统可能是缓慢的，也可能是极少的优化，或者两者兼而有之。 |
|
|
2.邻域法 - 邻域搜索技术以任何可行的计划开始，稍微调整一下，检查调整是否进行了任何改进。 - 在本循环中继续进行调整和测试取得了改进措施，直到取得改进措施为止。两个相关的概念邻域序列和这些序列的邻域生成机制是该方法的基础。 |
- 这类算法的搜索过程以一个局部最优的序列结束。 - 不幸的是,通常无法保证或甚至知道终端序列是否为全局最优。然而，很少有实验(Spacisamp;King，1979)表明，上面描述的基本邻域搜索算法作为一种通用的启发式算法是相当可靠的(Baker 1976)。 |
|
|
2.1.禁忌搜索 - 禁忌搜索方法在合理的运行里产生良好的结果。Taillard将这种全局优化技术应用于JSS，并表明它通常比移位瓶颈过程和由Lenstra(1992)实现的模拟退火更有效。对于一些比较复杂的问题，Taillard给出了计算时间较短的问题的最优解。. |
- 需要大内存，因为解决方案路径的子集保存在内存中。 - 另一个关键方面是使用可变的禁忌列表长度和循环检测机制来维护禁忌列表，这些机制防止了围绕多个相邻解决方案的循环. |
|
|
2.2.局部搜索技术 - 模拟退火和禁忌搜索技术(Widmer 1989，Dellrsquo;Amico等)是在JSS问题上测试过的主要局部搜索技术。在这两种情况下，邻域结构都是基于调度安排的。 |
- 与其他启发式方法相比，这两种技术都得到了相当好的解决方案。模拟退火比禁忌搜索在困难的实例上花费的时间要长得多。 |
|
|
3. 截断分支定界法 -迄今为止提出的最有效的近似方法之一可能是由Adams等人(1988)开发的移动瓶颈程序。以下是它的主要思想：从最初的JSS问题开始，用Carlier(1982)算法对单机问题进行逐个优化排序。机器排序的顺序取决于与它们相关的联瓶颈度量。 |
- 此过程嵌入到枚举类型的第二个启发式中，对于该枚举类型，搜索树的每个节点对应于排序机器的子集。与其他算法相比，它的效率较低，因为每次对一台新机器进行排序时，它们都试图在长时间的重新优化步骤中改进所有以前的调度机器。 |
|
|
4. 拉格朗日松弛 - 基于拉格朗日松弛的调度方法已被证明是高计算效率的，并为并行机调度问题提供了近似最优解。它被应用于调度作业车间，其中包括多个机器类型、通用优先级约束和简单的路线考虑。 |
- 它可以应用于在一定的条件和机器调度的某些案例。 - 复杂的JSS问题结果得不到保证。 - 在相同机器调度的情况下，它提供了近似最优解。 |
|
|
5.优先权规则 - 优先级规则指示当机器可用于处理时，如何在给定的时间将特定的作业分配给特定的计算机(Rowe, Jackson 1956)。对这些规则进行了大量的研究，Pinedoamp;Bhaskaran(1992)提出了基本调度规则的分类。 - 将100多条优先权规则归类为
|
- 研究人员结合其他动态决策对排序决策进行了分析，如工作释放(Wein 1990 a，1992)，到期日(Seidmann 1981，Bakeramp;Bertand 1981)，定价(KleinRock 1967，Dolan 1978和Mendelso 剩余内容已隐藏，支付完成后下载完整资料 资料编号：[469061]，资料为PDF文档或Word文档，PDF文档可免费转换为Word |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
