首 页 用户登录 |  用户注册
|
|||
|
|||
| 按字母检索 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 按声母检索 | A | B | C | D | E | F | G | H | J | K | L | M | N | O | P | Q | R | S | T | W | X | Y | Z | 数字 | 符号 |
|
|
 |
您的位置： 5VAR论文频道 → 论文中心 → 理工论文 → 信息技术 |
|
|||||
| 机器发生故障的排序问题 | |||||
收集整理：佚名 来源：本站整理 时间：2012-06-29 22:00:24 点击数：[]  |
|||||
|
[本篇论文由5var5VAR论文频道为您收集整理，5VAR论文频道http://paper.5var.com将为您整理更多优秀的免费论文，谢谢您的支持] | |||||
前言
排序问题作为运筹学的一个重要分支，起始于二十世纪五十年代，创立以来在运筹学、计算机科学、信息管理、经济学等学科领域受到了普遍的重视。题为《美国国防部与数学科学研究》的报告认为，20世纪90年代以至整个21世纪数学发展的重点，将从连续的对象转向离散的对象，并且组合最优化将会有很大的发展，因为“在这个领域内存在着大量急需解决而又极端困难的问，其中包括如何对各个部件进行分隔、布线和布局的问题”。现实生活中，有很多问题都反映为数学上的排序问题。生产中将生产出来的许多零件组装成某种产品需要排序，航空公司的飞机调度及人员培训需要排序，车站、码头以及十字路口的交通管理需要排序，等等。在达到预定目标的前提下如何有效利用时间、空间和人力、物力、财力，是我们经常遇到的优化问题。从深层次和长远来看，排序理论对提高效率、资源的开发和配置、工程进展的安排以及经济运行等方面都能起辅助科学决策的作用。
第一章 绪论
1.1 排序问题
1.1.1 排序问题的基本概念
排序问题是一类重要的组合最优化问题，它是利用一些处理机、机器或者资源，最优地完成一批给定的任务和作业。在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源堆加工时间的影响等。最优的完成指的是使目标函数达到最小，而目标函数通常是对加工时间的长短、处理机的利用率等描述。
在排序问题中，处理机的数量和种类，任务和作业的顺序、到达时间、完工限制，资源的种类和性能等情况是错综复杂的，很难用精确的数学描述给出一般的排序定义。我们用如下方式来描述排序问题：
给定 个任务的任务集 ， 个处理机的处理机集 和 种资源的资源集 。
排序问题指的是在一定条件下，为了完成各项任务，把 中的处理机和 (如果有)中的资源分配给 中的任务，使目标函数达到最优。
排序问题基本上是由处理机的数量、种类与环境，以及任务或作业的性质和目标函数所组成。
排序问题有不同的分类方法。最常用的分类方法是按机器、工件和目标函数的特征来分类。从机器的特征划分，有单台机器的排序问题和多台机器的排序问题。对于多台机器的排序问题，情况比较复杂。如果是多台完成相同加工的机器，属于平行加工的排序问题。如果是多台不同韵机器，又可分为三种情况：工件的加工路线相同为流水车问(f1ow Shop)排序问题，工件加工路线不同为单件车间(job Shop)排序问题， 工件加工路线可以任意为开放车间(open shop)排序问题。对于流水车间排序问题，若工件在每台机器上的加工顺序都相同，则为排列排序问题。按工件到达车间的情况分，当所有工件都已到达车间，可一次对它们排序，为静态的排序问题；若工件陆续到达车间，需随时对它们排序，是动态的排序问题。按目标函数的特征不同，可以分为单目标排序问题与多目标排序问题。不同的目标函数又构成多种不同的排序问题。此外，还可根据参数的性质划分，加工时间和其它有关参数为已知确定的量，为确定型排序问题；否则，为随机型排序问题。
1.1.2 排序问题的表示法
排序何题有不同的表示法。1967年，Conway等最先提出了四参数表示法： ，其中，A 描述工件的有关特征。对动态排序问题，A 表示工件到达时间间隔的分布；对于静态排序问题，A处以n表示工件数。B描述机器数，一般以m表示。C描述车间类型，C处若为F，则为流水车问排序问题；若为G，则为单件车间排序问题； 若为R，则为开放车间 排序问题； 若为P，则为同顺序排序问题。D为目标函数，例如， —平均流程时间， —平均延迟时间， —平均延误时间， —最长流程时间，等等。
1979年，Graham等提出了三参数表示法： 。下面记号 表示空集。
（1） 参数 描述“机器的环境（machine environment）”
参数 描述机器的类型：
表示单台机器，此时 ，
表示同型（号）机，
表示同类（别）机，
表示非同类型机，
表示自由作业机器，
表示流水作业机器，
表示异序作业机器。
参数 反映机器的数目
表示机器的数目不指定，可以是任何正整数，
表示有m台机器。
（2） 参数 描述“工件的特征（job characteristics）”,
参数 描述工件是否是在线的：
表示工件是离线的，
表示工件是列表在线，
与 一起表示工件是不可预测的时间在线，
表示工件是不可预测的列表在线，
与 一起表示工件是不可预测的时间在线。
参数 描述工件的就绪时间：
表示工件的就绪时间不相同，
表示工件的就绪时间相同，也等价于工件的就绪时间都等于0。
参数 描述工件是否有截止期限（deadline）：
表示工件有截止期限，
表示工件没有截止期限。
参数 描述工件加工是否可以中断：
表示允许中断加工，
表示不允许中断加工。
参数 描述工件的先后约束：
表示独立工件，即工件之间不存在先后关系，
表示先后关系是内收树（或称为入树）的形状，
表示先后关系是外放树（或称为出树）的形状，
表示先后关系是根树的形状，可以是内收树也可以是外放树，
表示先后关系是链状的，
表示工件之间存在某种先后关系。
参数 描述工件的加工时间：
表示每个工件的加工时间都是1个单位时间，这只会发生在
的情况，
表示每个工件的每一个工序的加工时间都是1，这只会发生在 的情况，
表示加工时间的数值不定，可以是任何非负（整）数。
我们经常用矩阵给出多台机器上的任务加工时间，用 ，用第i行 表示n个任务在第i个机器上的加工时间。 参数 还可以反映工件别的情况。例如 或 。他们的意义根据上下文将是很明确。
（3） 参数 表示“优化的目标（optimality crieria）”.
排序最为一个最优化问题的优化目标是一个一维实数。通常
1.1.3 排序问题的特点
1．复杂性。由于车间调度问题是在等式或不等式约束下求性能指标的优化,在计算量上往往是NP-完全问题,因而使得一些常规的最优化方法往往无能为力。
2．不确定性。实际生产中存在机器故障、紧急定单插入等随机性因素,以及模糊加工时间等不确定性因素,从而限制了精确建模和求解方法的实用性有时又称为动态随机性。
3．多约束性。生产线中人力、设备、信息等多种资源相互制约,生产线调度实际是在许多等式和不等式约束下寻求优化问题。
4．多目标性。生产线调度目标主要包括基于加工时间的指标(如完工时间、制造周期等) 、基于交货期的指标(拖期数、提前和/或拖期成本等)和基于成本的其他指标,多数优化准则下的生产线调度问题都是NP难题。实际作业过程一般都追求多项相互冲突的性能指标。
总之,排序问题是具有明确制造应用背景和相当研究难度的技术领域,传统的解析建模和最优化方法很难适应实际问题需求,需要探索基于启发式算法和问题知识的近优化智能方法。因此,掌握详细的分类情况和特点有着重要的实际意义。
1.2 排序问题的研究历史
非正规的排序方法已经使用丁好几个世纪，至今仍在使用。第一次世界大战期间出现的甘特图(Gantt Chart)，是最早的正规排序方法。这种条形图现在仍在广泛使用。用甘特图来安排轮船的装卸货问题，曾使得整个装卸时间减少一半。
正式的排序问题的数学模型是在甘特图出现40年之后，1954年由Johnson S M提出的，这就是著名的Johnson法则。按Johnson法则得出的算法解决了 问题。直到1977年，才有人证明三台机器同顺序排列问题是一个NP-完备问题。经过半个世纪的努力，排序的理论和应用已经发展成一门相当重要的学科。题为《美国国防部与数学科学研究》的报告认为，20世纪90年代以至整个21世纪数学发展的重点，将从连续的对象转向离散的对象，并且组合最优化将会有很大的发展，因为“在这个领域内存在着大量急需解决而又极端困难的问，其中包括如何对各个部件进行分隔、布线和布局的问题”。排序问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。从普通的生产部门的计划安排、人员调度，学校课程表的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法。
普遍认为1954年johnson的论文是经典排序的第一篇。从这篇论文问世以来的半个世纪中全世界已经发表排序文献2千多篇，其中包括排序专著和教材40余种，这些排序的论文和书籍中绝大部分是在过去10年发表。早在上世纪60年代中国科学院越民义就注意到排序问题的重要性和在理论上的难度。1960年，他编写了国内第一本排序理论讲义。70年代初他和韩继业一起研究排序问题，他们发表在《中国科学》上的著名论文开创了中国研究排序论的先河。在他们两位的倡导和带动下，国内的排序理论研究和应用研究有了较大的开展。排序论的长足发展，特别的新型排序的丰硕成果，使排序论已经成为发展最迅速、研究最活跃、成果最丰硕、前景最诱人的学科领域之一。
许多关于排序问题的研究论文出现在运筹学(OR)、管理科学(MS)、工业工程(IE)和计算机科学杂志上。研究大体沿着以下几个方向进行：
1．由两台机器的排序问题扩展到三台以及多台机器的排序问题
Johnson法则只适合于两台机器的流水车间排序问题，对于三台或多台机器是否也存在一个判别条件，以便确定工件的加工顺序呢？经过研究，人们找到了一些特殊的三台机器流水车间排序问题的算法。Szwarc W归纳了六种特殊类型的 问题的算法。对于多台机器的排序问题，Szwarc W归纳了五种特殊结构的 问题的算法。韩继业又提出了一种新的特殊结构的 问题及其算法。对于一般结构的 问题，越民义和韩继业得出了确定任意两个工件相对位置的一般法则。由于三台和三台以上机器的 问题与 问题本质上不同，越—韩法则不可能象Johnson法则那样，得出n个工件的全序。
2．由穷举法发展到分支定界法、动态规划法、消去法和启发式方法
1965年，Lomnicki和Ignall等人分别提出用分支定界法求 问题的最优解。随后，很多人对分支定界法进行了改进，提出了一些确定目标函数下界的方法。Lageweg等人对所提出的定界方法进行了归纳，并提出了一种新的定界方法。分支定界法是求排序问题最优解的一般性方法，不仅可用于解流水车间排序问题，而且可用于解单件车间的排序问题、单台机器的排序问题和平行加工的排序问题。但是，分支定界法本质上仍然是一种枚举法，只不过利用巧妙的定界方法，排除了不包括最优解的列举计算，它实质上是通过部分列举来找出最优加工顺序。
动态规划是1957年Bellman提出的，它可广泛用于各种组合优化问题。按实质，它与分支定界法一样，也是一种枚举法。1962年Held和Karp最先将动态规划用于求解排序问题。此后，将它用于调整准备时间与加工顺序有关的问题和有优先顺序约束的问题。
消去法是利用一些消去法则消去那些不可能是最优的部分顺序，从而得出一组优先顺序，然后从中找出最优解。Szwarc提出过
1.3 现代排序的分类
1.3.1 可控排序
经典排序中工件的参数，例如，工件的加工时间、交货期、就绪时间和权等都是固定不变的常数或固定不变的随机变量。然而，现实生活中的排序问题，工件在机器上加工，除了机器以外，还需要使用人工、资金等别的资源。改变或控制机器以外的资源可以改变或控制工件参数的大小。这时，工件的参数就不是固定不变的。如同在PERT中的赶工分析，在排序中也就提出赶工排序问题。赶工排序是一种可控排序，是通过对工件加工时间的赶工、压缩或控制来研究排序问题。这时，工件的加工时间不是固定的常数，而是决策变量。除了控制或改变工件的加工时间还可以控制或改变工件的交货期、就绪时间或权来研究排序问题。所有这类排序问题统称为可控排序。这类可控排序既要使排序问题的目标函数为最小，又要使控制参数所支付的费用函数为最小。因此，可控排序实质上是一种多目标排序。但它又与多目标排序不同，因为除了经典的排序目标函数以外，还有与这种目标函数本质上不同的控制(决策)变量的费用函数作为优化的目标。
1.3.2 成组分批排序
工件在机器上加工前所需要的安装(setup)时间往往是与排法有关的(sequence dependent)。柔性制造系统FMS(flexible manufacturing system)的发展，数控机床的高度柔性，可以适用于加工越来越多的不同种类的工件，从而可以避免和大大减少工件的安装时间和安装费用，适应订货式、多品种、小批量生产的需要。这种考虑成组技术GT(group technology)，考虑安装时间和安装费用的排序问题就是成组排序(scheduling with batching)。研究这类排序问题对提高GT的效率，提高FMS的生产能力具有重大的意义。
计算机集成制造系统CIMS (computer integrated manufacturing system)生产计划的主要功能是由制造资源计划MRP II (manufacturing resources planning)来完成的。作为MRP II核心的物料需求计划MRP(material requirement planning)主要是确定生产的批量(1ot-size)。为了保持较低的库存和满足较为紧迫的需求，就要考虑如何把工件分成子批，就要考虑何时发送相应的子批等。这就是分批排序(scheduling with lotsizing)所要研究的问题。排序不仅仅在短期计划，即在最底层计划中予以考虑，而且渗透在中期(中层)或长期(高层)计划之中，这是排序论在CIMS中的最新发展和应用。这类把工件分成子批的分批排序的研究，对改造传统的MRP和MRPII是有重大意义的。
1.3.3 在线排序
经典排序是假设排序问题一个实例的所有信息，包括工件的个数、就绪时间、加工时间等在开始排序前都是事先知道的。这种情况称为是离线(off-line)的。然而在现实生活中许多情况并非如此，而是在所有信息知道之前就必须进行排序。这种情况称为是在线(on-line)的或者是半在线(semi on-line)的。在线排序中，工件的信息是逐个释放的，在决定当前工件的加工时，对其后面就绪的工件的信息是一无所知的，并且一旦决定工件的安排后就不允许改变；离线排序在安排所有工件之前知道所有工件的信息。半在线排序是介于这两者之间，即不允许对已经安排的工件重排，在排序之前不知道所有的信息，但是知道后面就绪的工件的部分信息。
1.3.4 同时加工排序
经典排序是假设任何机器在任何时刻最多只加工-个工件，但在实际生活中，有的“机器”可以同时加工多个“工件”。例如，在一个烘箱或烤箱中可以同时烘烤多个面包。比较典型的是发生在大规模集成电路的生产中。为了保证成品合格，大规模的集成电路的生产最后阶段是要把多个集成电路同时放在烘箱中测试，看看是否能够在一定的温度下经受一定时间的烘烤。这类机器可以同时加工多个工件的排序问题称为同时加工排序，或称为批加工机器排序(scheduling a batching machine)。按照机器可以同时加工工件的个数(机器的容量)B的大小，这种排序问题可以分为两类：第一类是 (n是需要加工的工件个数)的情况，称为机器容量是有限的；第二类是 的情况，称为机器容量是无限的。我们把机器容量为有限的认为是默认的情况。不同工件一般可以有不同的加工时间，但是放在同一批中同时被加工时，根据问题的实际背景，作为一个批的加工时间有两种计算方法：一种是批的加工时间等于这批工件中所有工件加工时间的最大者，另一种是批的加工时间等于这批工件中所有工件加工时间的总和。这两种问题分别称为平行工件同时加工排序(parallel batching problems)和串联工件同时加工排序(serial batching problems)。
1.3.5 准时排序和窗时排序
经典排序中“延误”和“提前”是分别度量工件在交货期之后和在交货期之前完工的两个量。经典排序中把延误作为优化的目标是因为工件的延误要带来损失，要付出代价，因此要使工件的延误越小越好；经典排序又认为“提前”是“理所当然的”，是“应该的”，是不必付出代价的，也不会带来“收益”的。延误是一个正则的目标函数，这正是经典排序所研究的对象。然而，实际生活中“提前”也会造成损失，也要付出代价的。例如，对装运上船的货物来讲，在装运日之后到达码头，推迟开船，固然要课以罚款，支付费用；但在装船日之前到达码头，要支付仓库费和保管费，也是要支付费用的。
准时(just-in-time)排序是对交货提前和延误都要“受罚”，都要付出代价的排序问题。作为这种排序很自然的推广，是“交货期”不是一个“点”而是一个“区间”。在这个时间区间之后(延误)和之前(提前)交货都要付出额外的费用。这种排序称为窗时(due window)排序。窗时排序是准时排序的推广，准时排序是窗时排序的特殊情况。在这两类排序中的目标函数就不是正则的。
1.3.6 机器不同时开工排序
经典的平行机排序问题是假设所有的机器都是可以同时开始加工工件的，但在实际生产中机器不一定可以同时开工。
1.3.7 资源受限排序
经典排序是假设加工工件只需要机器一种资源，并且假设机器的能力是“无限”的，即任何时候和任何情况下，机器是一直可以加工的。突破这种假设有两个方面。第一，加工工件除了需要机器以外还需要其它的资源；第二，包括机器在内的所有资源的能力，不是“无限”的，而是有限制的。例如，有可用性约束的排序(scheduling with availability constraints)是机器是在某些时间段内可以加工，而在另一些时间段内不不能工。又如，数控机床加工零件时，数控机床是一种可恢复的(renewable)、使用性的(recoverable)或者讲是使用量受限制的资源，而数控机床加工零件所需要的电力是一种不可恢复的(nonrenewable)、消耗性的(nonrecoverable)或者讲是消耗量受限制的资源，还有一种如人力是双重受限制(doubly constrained)或者讲是使用量或消耗量都受限制的资源。资源受到限制的排序问题称为资源受限排序问题。
1.3.8 随机排序
经典排序都是假设排序问题中所有的参数都是预先知道的，是确定性的。但是，这个假设并不总是能满足的。例如，工件的加工时间可能会波动的，工件的到达可能是随机的，机器的故障也可能随时发生的。因此，必须从概率论的角度来研究排序问题。这就是随机排序问题。
1.3.9 模糊排序
除了概率论所描述和研究的一种不确定性之外，现实世界中还存在着另外一种不确定性，它是模糊集理论所描述和研究的对象。输入参数(工件的加工时间或交货期等)是模糊数的排序问题称为模糊排序。最早在排序问题中使用模糊集理论是在1979年。进入20世纪90年代以来，国外大多是研究模糊交货期的排序问题；而涉及模糊加工时间的排序的论文还很初步，有的列举出所有可行解，从中找出所谓“非受控解(non-dominated solutions)”，有的用遗传算法来搜索非受控解。随着在模糊集理论基础上发展起来的模糊推理和模糊控制等得到越来越广泛的应用，成为信息科学和系统科学研究的热点，模糊排序是值得引起关注的一种新型排序。
1.3.10 多目标排序
研究多个优化目标的排序问题称为多目标排序。多目标排序作为一种多目标决策问题，在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。例如，在一个工厂的生产过程中，生产决策者不但要使工件的总的加工时间为最小，以减少生产费用，还要尽量使误工工件的个数为最少，以更好地满足顾客的需求。这就是多目标排序问题。与一般的多目标决策问题一样，关于“解”的定义及其“偏好关系”是研究多目标排序问题非常关键的2个因素，因为多个目标之间常常是相互“冲突”的，一般不存在使多个目标同时达到最优的“绝对”最优解。在多目标决策问题中，有“有效解”、“序有效解”、“真有效解”、“妥协解”和“满意解”等，在多目标排序中，可以提出三种“解”的定义：约束解和多重(hierarchica1)解，有效(efficient)解或非支配解，权函数(weighted criteria)解等，分别称为第1、2、3类多目标排序。
以上分类为现代排序的分类，它突破了经典排序关于资源类型、确定性、可运算性、单目标和正则性等基本假设。具有深刻的现实意义和应用性。
1.4 排序问题的算法
算法根据它的性能大致可以分为三种：多项式算法(polynomial algorithm)、近似算法(approximation algorithm) 和启发式算法(heuristic algorithm)。由于多项式算法比较简单，这里就不做具体说明。
1.4.1 近似算法(approximation algorithm)
实际上，并不是所有的组合最优化问题都能找到多项式时间算法。对于NP-hard问题，当输入规模较大时，很难求出精确的最优解，所以寻找一种用多项式时间的计算量来求解NP-hard问题的非精确解的算法变得十分有意义。将问题的计算总次数从问题规模的指数时间下降到多项式时间，代价是精确度的损失。这一类算法称为多项式时间近似算法，简称近似算法。近似算法最后求得的不是最优解而是近似最优解。
评价近似算法性能好坏的一个主要标准是精确度，即求解结果与最优解的接近程度[10]。组合最优化问题近似算法的精确度通常用最坏情况绝对性能比(absolute worst-case performance ratio)和最坏情况渐近性能比(asymptotic worst-case ratio)来刻画。
1.4.2 启发式算法(heuristic algorithm)
启发式算法是相对于最优算法提出的。一个问题的最优算法求得该问题每个实例的最优解。
启发式算法是一个基于直观或经验构造的算法。在可以接受的花费(指计算时间、占用空间等)下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。
启发式算法与近似算法的主要区别在于启发式算法不考虑算法所得的解与最优解的偏离程度。启发式算法概念定义的算法集合包含了近似算法概念定义的算法集合。由于很多组合优化问题算法的最坏情况误差估计需要很强的数学基础和技巧，甚至一些问题无法给出最坏情况误差的界，而实际问题又迫切要求解的方法，因此，只能通过启发式算法解决问题。
评价启发式算法的性能主要分为对算法的计算复杂性的分析和对算法计算效能的分析。常用的方法有最坏情形分析(worst case analysis)、概率分析和大规模计算分析。[10]
第二章 误工任务数问题
很多情况下，延误时间的长短并不重要，但一旦有延误发生，造成的影响是一样的，例如，用航空飞机发射太空站，每个天空站都是完成特定的太空观测任务，误期发射的太空站将失去作用。在这种情况下，目标应使误期发射的太空站数目最少。 个任务要在处理机上加工，每个任务的加工时间和工期都是已知的。如何安排加工顺序，使得延误的任务数最少。经典的最小化误工工件数问题是希望找到一个排序，使得误工件数 达到最小，其中 。
2.1问题
对于排序问题
2.2问题
我们这里只研究机器带故障的排序问题。
在单台机情况下 是P问题，有最优算法。在这个基础上可以尝试找三台机的算法。而在 ， 是NP困难，可能无法找到一个最优的，但可以找一个近似算法。下面对以下2个问题讨论：
（1）
（2）
2.2.1问题
基于 的Moore算法。
算法2.2.1 ( 算法)
设中断发生时刻， 上正在加工的工件为 ， 上正在加工的工件为 。
１） 工件集 在时刻 开始在机器 上按单台机最优算法Moore算法排序，称该序为 ，记该序下误工工件数 。
２） 工件集 在时刻 开始在机器 上按单台机最优算法Moore算法排序，称该序为 ，记该序下误工工件数 。
３） 比较 ， ，选择值小的排序。
可得上述算法得出了问题 的最优序。
2.2.2问题
（１）当 时，故障机 上的工件转移到 时， 的所有任务已经完成，则剩余的 工件按原次序在 上加工，且全部误工。所以在这里我们不考虑这种情况。
称从 发生故障时刻到 上原工件被加工完时间为 ，则我们以下考虑的问题是
情况下的误工工件问题。
（２）如果存在中断t时刻在机器 上加工且尚未完工的工件，则称其为跨越工件。这里我们假设不存在跨越工件的情况。即中断时刻机器正好加工完一个工件。
称原始排序在机器 上加工工件称为 工件。
由于中断时刻为0。转移时间t>0时，机器 上原序所安排的t时刻之前开工的工件没来得及转移就已经误工了，称它们为哑工件，并记哑工件组成的集合为R。设 为工件集I\R（除去哑工件）按2.2.1算法得到的关于 问题的最优排序。
算法2.2.2 ( 算法)
（１） 计算工件集I\R关于问题(2.2.1)的最优算法排序，得到排序 。
（２） 若 中t时刻之前不含 工件，则 即为问题(2.2.2)的最优排序，算法结束；否则转到下一步继续。
（３） 依次选取 中开工时间大于t的l个 工件 ，使满足 ，而 。记 。
（４） 若 ，算法先依次安排 中的工件排序，然后在中断时刻安排 ，接着在t时可安排 ，再按 中的顺序加工 中的工件，最后任意顺序加工哑工件。
（５） 若 ，算法先依次安排 中的工件排序，然后在中断时刻安排 ，接着在t时可安排 ，再按 中的顺序加工 中的工件，最后任意顺序加工 及哑工件。[13]
2.3 问题
已知两台机中断误工工件数最小化排序： 其中 是NP困难的。三台机问题也是NP困难的，从而寻求求解这一问题的多项式时间近似算法就成了一项十分有意义的工作。由于对给定的最优排序下误工工件数有可能为零，此时若在近似算法求得的排序下存在误工工件，则两者无法进行比较，为避免这一困难，将研究目标函数设为按期完工工件数 最大化问题。
为了研究的方便我们只取一般性，不考虑特殊情况，如 或者 上的未加工工件中有工期靠前，但是完成时间要求特别长的情况（这种情况下我们应该放弃完成加工时间特别长的工件，而加工加工时间短的工件，这样可以增加按期完工任务数）。
2.3.1问题 算法
不妨设三台机器中 发生故障中断，中断发生时 上未完成的工件集为 ， 上正在加工的工件为 ， 上未完成的工件集为 ， 上正在加工的工件为 ， 上未完成的工件集为 。
算法2.3.1（ 算法）
1) 将 ， ， 构成工件集（设为 ）整理成按交工期限的单调非减顺序。
2) 按Moore算法，依次将工件分配给 加工，记在 上按期完工工件集为 。
将 中工件按Moore算法依次分配给 加工，记 上按期完工工件集为 。
将 中的工件以任意顺序安排给 或 加工（ 先加工 中工件， 先加工 中工件），对应序记为 。
3) 将 ， ， 构成工件（记为 ）整理成按交工期限的单调非减顺序。
4) 按Moore算法，依次将工件分配给 在工件 后加工，记 上按期完工工件集为 。
将 中工件按Moore算法依次分配给 在工件 后加工，记上按期完工工件集为 。
将 中工件以任意顺序安排给 或 加工（ 先加工 中工件， 先加工 中工件），对应序记为 。
5) 记1）和2）下按期完工工件数为
记3）和4）下按期完工工件数为
比较两者大小，选择值大的排序。
2.3.2问题 举例
例2.1 考虑排序问题 ，当 机器发生故障中断时，其他两台机器上的跨越工件 ， 没有故障下三台机器上的最优加工序列对应工件的加工时间为 ，（ 表示第i台机器上按原排序的第j个任务的加工时间），对应的工期为 ，在t=2时刻中断发生。
解：（1）当t=2时刻， 对应的工期为 ，首先将剩下的全部工件分配 加工，得到 上能按期完工工件为 ，对应的加工时间为 ，工期为 ，对剩下的工件 分配给 加工，得到 上能按期完工的工件为 ，对应的加工时间为 ，对应的工期为 ，接着对剩下的工件加工（ 先加工 中工件， 先加工 中工件），得到对应的加工序列为 ，即 上加工序列为 ， 上加工序列为 ，得到按期的完工工件数 为5。
（2）当t=2时刻， 对应的工期为 ，首先将剩下的全部工件分配给 加工，得到 上能按期完工的工件为 ，对应的加工时间为 对应的工期为 ，将剩下的工件 分配给 加工，得到 上能按期完工的工件为 ，对应的加工时间为 ,对应的工期为 ，再把剩下的工件以任意顺序分配给两台机器（ 先加工 中工件， 先加工 中工件），得到对应的加工序列为 ，即 上加工序列为 , 上加工序列为 ，得到按期的完工工件数 为6。
比较两者大小，选择值大的排序 ，最小误工任务数为3。
图2-1为最优排序
2.3.3问题 算法
现研究机器的传输时间不为零的中断排序问题 ，
下面考虑 的情况，不失一般性，不妨设 ，规定算法总是给传输时间较少的机器先分配加工工件，不妨设 为 上工件转移到 上
算法2.3.2（问题 算法）
1）将 ， ， 构成工件集（设为 ）整理成按交工期限的单调非减顺序。
2）按Moore算法，在 时刻依次将工件分配给 加工（若首个工件为 ，则继续，不则中断），记 上按期完工工件集为
将 中工件按Moore算法在 时刻依次分配给 加工（若首个工件为 ，则继续，不则中断），记 上按期完工的工件集为
将 中的工件，任意顺序安排给 或 加工（ 先加工 中工件， 先加工 中工件），对应排序记为
3）将 ， ， 构成的工件（记为 ）整理成按交工期限的单调非减顺序。
4）按Moore算法，依次将工件分配给 在工件 后加工，记 上按期完工工件集为 。
将 中按Moore算法将工件分配给 在工件 后加工，记 上按期完工工件集为 。
将 中工件以任意顺序安排给 或 加工（ 先加工 中工件， 先加工 中工件），对应排序记为 。
5）记1）和2）下按期完工工件数为 ；
记3）和4）下按期完工工件数位 ；
比较两者大小，选择值大的排序为最优排序。
2.3.3问题 举例
例2.3 考虑排序问题 ，当 机器发生故障中断时，其他两台机器上的跨越工件 ， 没有故障下三台机器上的最优加工序列对应工件的加工时间为 ，（ 表示第i台机器上按原排序的第j个任务的加工时间），对应的工期为 ，在t=2时刻中断发生。 上的工件转移到剩下两台机器上的时间分别为 。 间不需要转移时间。
解： （1）在t=2时刻， ，对应的工期为 ，将工件分配给 加工，由于首个工件为 ，则继续加工 ，得到按期完工工件为 ，对应的完工时间为 ，对应的工期为 ，将剩下的工件集 分配到 上加工，由于首个工件不是 ，则中断，即在t=4时刻开始加工 ,得到按期完工工件 ，对应的完工时间为 ，对应的工期为 ，将 中的工件，任意顺序安排给 或 加工（ 先加工 中工件， 先加工 中工件），对应排序记为 ，即 上加工序列为 ， 上的加工序列为 ，我们能够得到 为5。
（2）在t=2时刻， ,对应的工期为 ，将工件分配给 加工，得到按期完工工件为 ，对应的完工时间为 ，对应的工期为 ，将剩下的工件集 分配到 上加工，得到按期完工工件为 ，对应的完工时间为 ,对应的工期为 ，将 中工件以任意顺序安排给 或 加工（ 先加工 中工件， 先加工 中工件），对应排序记为 ，即 上的序列为 ， 上的加工序列为 ，（ ， 先加工完自己的任务再加工 的）我们能够得到 为6。
比较两者大小，选择值大的排序为最优排序 ，最小误工任务数为3。
图2-2为最优算法
第三章 总完工时间问题
对于目标函数是加权总完工时间的情况，如果各个任务的权因子不同，即使限定只有两台处理机，问题 也是 NP-难的。因此，这里仅讨论权因子相同的情况，即目标函数为总完工时间问题。在这一类问题中，如果任务集是相关的，则问题都比较复杂，只有极个别情况例外。对于同速机的情况，可中断往往并不能使问题简化。如果任务集是相关的，问题相对简单。
3.1 问题
类似于单机问题 ，对于总完工时间问题 采用SPT规则可以得到最优排序。 对应的加工时间为 。
3.1.1 SPT算法
SPT算法
1） 将全部任务按加工时间不减列表 使 ；
2） 在表中取前面3个任务依次分给3个处理机；
3） 重复2），直到全部任务排完。
3.1.2 问题 举例
例3.1 考虑排序问题 ，其中n=8，
解：利用SPT规则得到的排序是最优排序，如图，可得总完工时间为
图3-1 例3.1的最优排序
3.2 问题
本节算法基于 的SPT算法。
3.2.1 算法
中断发生时刻，机器上会有尚未完工的工件，我们称其为跨越工件。由于跨越工件的存在，我们要需要考虑故障机器台数，由于2台机故障是1台机故障的2次重复，所以不再研究，这里只考虑一台故障，不失一般性，设第1台机器发生故障，所以仅分两种情况考虑中断后的重新排序问题。
情况1：将正在加工的跨越工件当作未加工工件，和其他未加工工件放在一起重新排序加工。
设发生中断时，3台机器上正在加工的工件分别为 ，
1）将每台机器的跨越工件 和剩下未加工的工件按加工时间不减重新排序列表 使
2）在表中取前面2个任务依次分给剩下的未出故障的2个处理机；
3）重复2），直到全部任务排完。
最终得到排序 ，总完工时间为
情况2：除发生故障中断的机器上的跨越工件作为未加工的外，其它机器将正在加工的跨越工件完成后再开始对重新排序的工件进行加工。
设发生中断时，3台机器上正在加工的工件分别为 ，
1）将每台机器剩下未加工的工件和发生故障机器上的跨越工件一起按加工时间不减重新排序列表 使
2）在表中取前面2个任务，由于中断时刻每台机上都有跨越工件，所以我们等待机器加工完跨越工件后，依次将这 个任务分给剩余的2个处理机；
3）重复2），直到全部任务排完。
最终得到排序 ，总完工时间为
比较以上2种情况下的 与 ，选取值小的排序，则该排序就是问题 的最优排序。
3.2.2 问题 举例
例3.2 考虑排序问题 ，当 机器发生故障中断时，其他两台机器上的跨越工件 还需要加工的时间为 ， 上的跨越工件为 。所有跨越工件对应的加工时间为 ，每台机器上还有1个工件未加工，对应加工时间 。
解：
情况1下，即把跨越工件和其他未加工的工件，按加工时间不减排序，得到对应的加工时间序列 ，进行如图排序，得到总完工时间为
图3-2 情况1下的排序
情况2下，即先将 的跨越工件加工完，然后把 上的跨越工件和其他未加工的工件，按加工时间不减排序，得到对应的加工时间序列为 ，进行如图排序，可得总完工时间为
图3-3 情况2下的排序
因为 ，则得出 是问题的最优排序，比较两种排序得最优的总完工时间为 。
3.3 问题
3.3.1 算法
现在我们研究转移时间不为0情况下的，带故障的三台平行机的排序的问题。基于 问题，我们可以得到类似的算法。为了消除转移时间的干扰，我们进行如下调整：对于不需要转移的工件，新的加工时间等于原加工时间；对于需要转移的工件，新的加工时间等于原加工时间和转移时间的和。
情况1：将正在加工的跨越工件当作未加工工件，和其他未加工工件放在一起重新排序加工。
设发生中断时，3台机器上正在加工的工件分别为 。
1）将每台机
情况2：除发生故障中断的机器上的跨越工件作为未加工的外，其它机器将正在加工的跨越工件完成后再开始对重新排序的工件进行加工。
设发生中断时，3台机器上正在加工的工件分别为 ，
1）将每台机器剩下未加工的工件和发生故障机器上的跨越工件一起按新的加工时间不减重新排序列表 使
2）在表中取前面2个任务，由于中断时刻每台机上都有跨越工件，所以我们等待机器加工完跨越工件后，依次将这 个任务分给剩余的2个处理机；
3）重复2），直到全部任务排完。
最终得到排序 ，总完工时间为
比较以上2种情况下的 与 ，选取值小的排序，则该排序就是问题 的最优排序。
3.3.2 问题 举例
例3.3考虑排序问题 ，当 机器发生故障中断时，其他两台机器上的跨越工件 还需要加工的时间为 ， 上的跨越工件为 。所有跨越工件对应的加工时间为 ，每台机器上还有1个工件未加工，对应加工时间 ，工件的转移时间为1。
解：情况1，由于 上的工件 需要转移时间，则他新对应的新的加工时间为原加工时间和转移时间之和，即 ，先把跨越工件和其他未加工的工件，按加工时间不减排序，得到对应的加工时间序列 ，进行如图的排序，可得总完工时间
图3-4情况1下的排序
情况2，由于 上的工件 需要转移时间，则他新对应的新的加工时间为原加工时间和转移时间之和，即 ，先将 的跨越工件加工完，然后把 上的跨越工件和其他未加工的工件，按加工时间不减排序，得到对应的加工时间序列 ，进行如图排序，可得总完工时间
图3-5情况2下的排序
比较 和 得到最优的总完工时间为55。
第四章 总结
排序是一类重要的组合最优化问题，它广泛应用于生活中的很多领域，所以本课题的研究具有广阔的实际应用前景和现实意义。通过这次机会，接触到很多组合最优化问题（特别是排序问题）的一些理论和方法。对这些理论和方法有了初步的理解，建立了最优化的思想，并能在现实生活中指导自己的行为，收益良多。
本文试图找出发生故障的三台平行机的排序问题的最优排序，分别对目标函数是为误工任务数和总完工时间的三台机排序进行研究，在前人研究的基础上找到了比较适合的排序算法，进而得到了最优的排序，并举例进行了说明。但是对一些特殊的情况和比较复杂的情况仍没有考虑到位，还存在很多不足和需要改进的地方。
总之，通过这次论文的写作，使得我的能力得到了方方面面的锻炼，如：自学能力、语言的表达能力、理解能力、独立思考能力、分析能力，同时也发现了很多自身的缺点和不足，为以后更好的工作实践做准备。
致谢
在本文完成之际，我由衷的感谢所有给予我关怀、教育、帮助、支持和鼓励我最终完成学业的亲人、老师、同学以及朋友们。
首先感谢我的毕业设计指导老师——浙江科技学院理学院叶赛英老师，在机器发生故障的排序问题学位论文选题、文献查阅、论文修改、最后定稿无不包含着指导老师的心血，在大学期间，指导老师渊博的专业知识和严谨的治学态度给我留下了深刻的印象，使我受益匪浅。在此谨向指导、培养我多年的导师表示衷心的感谢。
其次，在本科生学习阶段，我得到了众多老师的指导和帮助，从而顺利修完了本科生阶段要求的课程。借此机会，向所有教导和关心过我的任课老师致以最诚挚的感谢。
最后，感谢各位评阅老师提出的宝贵意见，我将虚心接受，并在以后的学习和工作中继续坚持虚心好学、奋发向上的态度。
谢谢各位老师！
参考文献
唐恒永,赵传立.排序引论[M].北京：科学出版社.2002年6月第3次印刷：8-68.
唐国春.现代排序论[M].上海科学普及出版社.2003年12月第1版：1-80.
Conway,R.W.,W.L.Maxwell and L.W.Miller.Theory of Scheduling[M].Addison-Wesley Publishing Company.Reading.Massachusetts,1967.
Graham,R.L.,E.L.Lawler.J.K.Lenstra and A.H.G.Rinnooy Kan.Optimization and appr-
oximation in deterministic sequencing and scheduling[J]. A Survey Annals of Operations Research,1979,5:287-326.
Baker K.R.Introduction to sequencing and scheduling[M].Wiley,New York,1974.
周仲良,郭镜明.美国数学的现在和未来[M].上海:复旦大学出版社,1986年8月第1版.
Johnson,S.M.Optimal two and three-stage production schedules with setup times included[J].NRL,1954,1:61-68.
越民义,韩继业.n个零件在m台机床上的加工顺序问题(I)[J].中国科学,1975,5:462-470.
[9]陈荣秋.排序问题研究的历史及发展趋势[J].维普资讯http://www.cqvip.com, 2009年5月引用.
[10]唐恒永,赵大宇,赵玉芳.最优化理论与算法[M].沈阳:辽宁大学出版社.1997.
[11]张勇传,瞿继恂.组合最优化:计算机算法和复杂性[M].华东理工大学出版社.1994年6月,第1版:1-20.
[12]叶赛英等.机器带故障的两台机排序问题的一个近似算法[J].杭州电子科技大学学报. 2008年4月,第8卷第2期:90-92.
[13]Lee C.-Y. and Z. L. Chen. Machine scheduling with transportation considerations [J].Journal of Scheduling,2001.4:3–24.
| 提供人：佚名 | |
| 【返回上一页】【打 印】【关闭窗口】 | |
 中查找“机器发生故障的排序问题”更多相关内容
|
5VAR论文频道 |
 中查找“机器发生故障的排序问题”更多相关内容
|
5VAR论文频道 |
 文章-网友评论：（评论内容只代表网友观点，与本站立场无关！） |
| 关于本站 -
网站帮助 -
广告合作 -
下载声明 -
网站地图
Copyright © 2006-2033 5Var.Com. All Rights Reserved . |
小
大