准时排序和窗时排序

经典排序中“延误”和“提前”是分别度量工件在交货期之后和在交货期之前完工的两个量。经典排序中把延误作为优化的目标是因为工件的延误要带来损失，要付出代价，因此要使工件的延误越小越好；经典排序又认为“提前”是“理所当然的”，是“应该的”，是不必付出代价的，也不会带来“收益”的。延误是一个正则的目标函数，这正是经典排序所研究的对象。然而，实际生活中“提前”也会造成损失，也要付出代价的。例如，对装运上船的货物来讲，在装运日之后到达码头，推迟开船，固然要课以罚款，支付费用；但在装船日之前到达码头，要支付仓库费和保管费，也是要支付费用的。

准时(just-in-time)排序是对交货提前和延误都要“受罚”，都要付出代价的排序问题。作为这种排序很自然的推广，是“交货期”不是一个“点”而是一个“区间”。在这个时间区间之后(延误)和之前(提前)交货都要付出额外的费用。这种排序称为窗时(due window)排序。窗时排序是准时排序的推广，准时排序是窗时排序的特殊情况。在这两类排序中的目标函数就不是正则的。

经典的平行机排序问题是假设所有的机器都是可以同时开始加工工件的，但在实际生产中机器不一定可以同时开工。有的机器可能正在加工另外一个排序问题的工件，有的机器加工前可能还要做清洗等准备工作，这时机器就不能立即开始加工。我们把这种机器称为不能同时开工的机器，或称为是需要就绪时间(准备时间)的机器。这种机器不是可以同时开始加工工件的平行机排序问题，简称为机器不同时开工排序，或者称为机器有不同就绪时间的排序问题。这时可能存在不起作用(inactive)的机器，这是由于机器的就绪时间太迟，以至于来不及加工工件。在分析算法的性能时要把这种不起作用的机器区别开来。

......

排序是一类重要的组合最优化问题，它广泛应用于生活中的很多领域，所以本课题的研究具有广阔的实际应用前景和现实意义。通过这次机会，接触到很多组合最优化问题（特别是排序问题）的一些理论和方法。对这些理论和方法有了初步的理解，建立了最优化的思想，并能在现实生活中指导自己的行为，收益良多。

本文试图找出发生故障的三台平行机的排序问题的最优排序，分别对目标函数是为误工任务数和总完工时间的三台机排序进行研究，在前人研究的基础上找到了比较适合的排序算法，进而得到了最优的排序，并举例进行了说明。但是对一些特殊的情况和比较复杂的情况仍没有考虑到位，还存在很多不足和需要改进的地方。