爱华网系列专题：2009中国营销
APS在未来的理论研究、应用研究、系统设计和集成的开发。
一、理论研究
未来的APS理论研究将仍然集中在经典理论和模型上：
（1）排程的理论集成；
（2）新排程方式和假设；
（3）特殊模型的理论性质。
（1）排程的理论基础
排程的理论基础仍然得到大量的研究。在确定性排程中的一个理论领域就是多面体组合和切平面的研究。这个研究领域已经产生了分支切平面类型精确解方法和对于一些基础排程模型来说可以保证性能的近似算法。这种方法在以后很可能扩展到更一般的排程模型中。分支定界的另一种形式-分支定价法，近来在一些并行机排程问题中也有了成功的应用。
确定性排程的另一研究方向是对于NP难问题的多项式时间近似方案。这个领域最近受到了大量关注。未来有可能得到进一步的关注，并且这类方法有可能应用到比现在考虑的更加复杂的模型中。然而，我们还不清楚这些研究什么时候能对实际中应用的启发式方法的性能产生影响。其他类型的近似方法也将得到研究。一类非常有希望的近似算法是基于松弛线性规划的。
（2）新的排程方式和假设
大多数模型的最典型排程方式和基础假设如下；在一个给定的加工环境中，有n项工作，与这n项工作相关的信息在时刻0点可知。一个特定的目标函数一般需要最小化且必须产生一个最优的（或最少是非常好的）排程。新的研究领域集中在一些模型中，它们的排程假设与以上假设完全不同。
实时排程是一个研究领域。因为它与传统的（离线）确定性模型在一些研究基础上是不同的，所以在线排程的研究非常重要，前者假设所有的信息都是事先（即在制定决策之前）已知的。在线排程中，决策的制定必须依赖于已提交的工作信息而不能依赖于已提交的工作信息。在线排程和随机排程之间的关系的研究也得到了关注。这是一个相对开放的研究领域。
再排程的概念将来会变得越来越重要。然而，分析再排程问题的正式的理论框架还未建立起来。一个再排程问题可能是多目标的：原问题的目标（例如，总加权滞后时间）、最小化新排程（再排程之后的）和原排程（再排程之前的）之间的差距。对于同一工作集或对应两个略微不同的工作集（例如，一项工作集是另一项工作集中的全部工作再加上一个额外的工作——个突发性工作而构成的）的两个排程之间的区别或相似性，可能有必要给出规范的定义或函数来进行测量。
再排程过程可能需要处理一些冻结的工作（即一些工作被事先分配在一些特定的时间段上，且不能在随后的排程过程中被移动）。有时在冻结工作上的一些约束允许排程人员在加工这些工作的时侯进行一些微小的调整。这样一个冻结工作的开始时间可以略微提前或延后，即对于冻结工作的加工（可能存在有限的松弛量）来说有一个时间范围：存在冻结工作的排程问题与存在故障的机器或有预防性维修排程问题在某种程度上是类似的。然而，也存在许多不同的方面，这是由于与冻结工作相关的数据是固定的，而与机器故障相关的数据是随机的。
鲁棒性的概念是与再排程相关的，它在今后也可能得到更多的研究。有一些测量鲁棒性的指标和构建鲁棒性的排程的几个实际规则。然而，对于这些规则的理论研究非常少。因此，还不清楚对于各种排程环境这些规则是否有效。
（3）特殊排程模型的理论性质
一类研究领域关注于结合了确定性属性和随机属性的模型。例如，考虑一个模型，它具有确定的加工时间和工期．而机器故障的发生是随机的。在许多环境中，这个模型非常现实。仅仅在一些非常特殊的情况下．该类模型才能够比较容易地解决问题。例如，一台机器，它处于工作状态的时间是独立同分布的指数随机变量，而故障时间都具有相同的的期望，则该问题是可进行分析的。WPST最小化总加权完成时间的数学期望。然而．对于更加复杂的加工环境的研究是很有意义的，在这些环境中机器的故障过程更加一般化。
因为这些模型比经典模型更加复杂．所以预期的结果类型可能更加通用或者结构化。如，这些结构化的结果可以由一些优先准则的证明或单调性结果的证明来构成。
二、应用研究
应用研究包括：
（1）启发式方法的性能分析；
（2）鲁棒性和反应排程；
（3）新的和更加应用化的模型。
（1）启发式方法的性能分析
这是在实验和经验性研究中非常重要的领域，目前只能解决小规模的加工车间问题。例如，获得10台机器和30项工作的问题的最优解是非常困难的。如果有多个目标并且需要进行参数分析，那么问题将变得非常复杂。可以利用许多下同类型的启发式方法．但是对于解决大规模问题（例如，具有2个或3个目标，50台机器和1000项工作的的加工车间排程问题），它的有效性还不是很清楚。对于这类大规模加工车间排程度问题的启发式方法在未来需要进行不断的改善和细致的调整。
启发式方法之间的比较有许多标准。实际上，有3个标准是最重要的。其一是获得的解的质量；其二是获得好的计算时间：其三是开发和实现启发式方法所需的时间。在学术界，对于启发式方法的比较汉考虑前两个标准，然而在工业界．第3个标准是至关重要的。工业界中，在很短的时间内选择一个适当的启发式方法是非常重要的。这就是为什么实际上局部搜索启发式方法比起非常夏杂的分解技术．例如转移瓶颈启发式方法，更加常用的原因。
当然，启发式方法的性能依赖于排程问题（例如，在加工车间中加工路线的约束类型）的结构。性能也与特定的数据集有关。当解决一个NP难问题时，许多问题的实例可以在合理的时间范围内得到一个最优解。但是某些实例非常难以解决，在找到最优解之前需要花费大量的计算时间，有必要找到是什么原因使那些问题实例如此难以解决。经验表明，若一个实例的数据是随机生成的，则启发式方法往往表现得很好。而对于同样问题的一组真实的数据，同样的启发式方法的性能表现却很糟糕（可能是由于工业数据的依赖性和相关性造成了求解的困难）。因此有必要建立一些规则来说明哪种类型的算法更适用于哪种类型的实例。
为了恰当地描述—个问题的实例，必须设置适当的描述因子，例如工期紧迫因子。除了这样的因子以外，还需要为这些因子设置恰当的权重。了解以下情况，对于知道哪种类型的算法对于给定的问题实例是最适合的是非常有用的：首先是实例的大小（规模）；其次是特征因子的值；第三是可用的计算时间。
一类重要的启发式方法是局部搜索过程。在过去的几十年中，局部搜索算法已经在应用和实施方面进行了大量的工作。研究在邻域结构方面产生了非常有意思的结果。然而，大量的研究还集中在不可中断的排程问题上。对于可中断的排程问题，研究者利用局部搜索方法进行的研究非常少。原因之一就是为后者设计一个有效的邻域结构要比前者困难得多。因此，首先将研究重点集中在一些特殊问题上会比较有意思，这些问题仅允许在一些特定时间点（例如，当新工作提交时）上进行中断。
将来可能会出现一种需求，即可以应用于工业界中共同的标准排程问题的工业启发式方法。例如．这个排程问题在许多流程工业中是非常典型的。有两个目标是非常普遍的：一个目标关注工期而另一个试图均衡所有机器的负荷并最小化准备时间。未来，可以开发面向特定问题的启发式方法，它可以非常方便地集成到各种排程系统中（正如线性规划软件包可以集成到许多决策支持系统中一样方便）。
（2）鲁棒性和反应排程
经验研究的一个完全不同的方面是鲁捧性和再排程。鲁棒性和再排程的概念导致了一些非常有意思的理论研究。然而，它们还可能导致一些更加有意思的经验研究和实验研究。已经开发了一些鲁棒性新的指标，这些指标的定义依赖于加工环境。再排程过程基于一些非常特殊的通用过程。
（3）新的和更加应用化的模型
更加实际的模型综合了机器排程和其他一些问题，例如人员排程、库存控制或维护排程。在航空业中，航空公司针对不同的航线必须将他们的飞机和机组成员一起进行排程。对于单纯的人员排程问题（独立于机器排程）已经有了大量的研究，但是对于综合人员排程和机器排程的模型还鲜有研究。对于这些类型的问题，即资源约束问题（即有限的人数等价于受限的资源），已经有了一些理论上的研究。然而，资源约束排程的研究主要集中在复杂度分析和启发式方法的最坏情况的分析。将来对于综合了机器排程和人员排程的更加特殊问题的研究可能是比较实用的。
三、系统开发和集成
系统的开发和集成将更加集中在以下专题：
（1）分布式排程；
（2）用户界面和交互式优化；
（3）排程描述语言：
（4）与其他供应链管理模块的集成。
（1）分布式排程
处理大规模排程问题导致分布式排程的实施。许多工业问题的规模非常大，不可能仅由单一的工作站来解决。计算将被分配到许多工作站上或者分布于不同地点的计算机上。对于某些程序，计算的划分相当简单．而对于其他一些程序就不是很简单了。例如，当用分支定界法来解决一个问题时．就可以相对简单地分解分支树，然后划分相关的计算任务。在周期性间隔中．不同的工作站之间需要比较各自的计算情况并分享信息（例如，比较当前找到的最优解）。如果通过基于时间的分解法解决了一个问题，那么也可以应用分布式排程（只要不同时间的排程之间是相互独立的）。利用最新的互联网技术，分布式排程不久将变得更加重要。
（2）用户界面和交互式优化
用户界面和交互式优化的发展将面临一些障碍。用户界面的设计必须使交互式优化可以方便且有效地实现。排程人员在所有时间都必须对排程过程有一个很好的把握，即使排程包含了1000项工作。用户界面的放大、缩小能力是非常重要的。为了允许交互式优化，用户界面必须具有单击和拖放操作、冻结操作、处理层叠与传播效应和再排程的功能。用户在系统中进行了手工修改后．系统可以进行再排程且保持可行性（不需要任何的用户输入）。用来保持可行排程的（内部）算法相对比较简单，可能只是延迟了某些操作而已。然而，内部操作可能是非常复杂的，并且可以执行一些内部的再优化（自动的）工作。然而，再优化过程也可以由用户来控制，用户可能希望为再优化过程指定一些适合的目标函数。再优化算法和开始使用的优化算法完全不同。再优化难以开始优化的原因在于再优化算法必须处理由原来的排程方案所产生的边界条件和约束。再排程算法集成到用户界面中使得用户实现交互式优化．这并不是一个简单的问题。
（3）排程描述语言
程序的编写和集成导致了所谓的排程描述语言的开发。一个排程描述语言是一种高级语言，它允许排程人员仅用一些有限的准确语句或命令为一个复杂的算法编写代码。在描述语言中的每一条语句包含了一个非常强大的程序的一个应用。例如，一条语句可以给出一条指令来为指定加工环境中的一组工作集调用禁忌搜索程序。这样一条语句的输入由工作集、加工环境、加工限制和约束、禁忌列表长度、一个初始排程和最大的迭代次数构成。输出由程序得到的最好的排程方案构成。其他语言可以用来设置各种不同的程序并行运行或链接两个不同的程序。排程描述语言仍未广泛应用。已有的语言仍有些麻烦，需要简化。但将来这个方面很有可能得到改善。
（4）与其他供应链管理模块的集成
许多公司早已经开始为制造业开发排程软件。然而，为了市场竞争，他们意识到必须为供应链管理的各个方面提供相应的软件。供应链优化管理所需的模块类型除了计划与排程外，还包括预测、需求管理、库存控制等。在供应链管理中的排程问题需要考虑预测、库存和流通路线问题。这些综合排程问题比在理论研究的基础问题要困难得多。软件的结构和组织必须很好地设计和模块化。
