高级排程(Advanced Scheduling)是实时的、动态集成的、基于内存计算，主要用于车间订单工序的排程。是基于事件的有限约束排程，意味是实时的考虑目前的负荷和能力和材料供应等多因素。可以支持不同的优化方法，考虑基于规则的资源和工序选择如最少换装时间、最小闲散时间和尽可能的迟考虑排序的相关性等。

 

高级排程(Advanced Scheduling)一般分三步：预见性排程，可以给一组订单预先准备优化的排程。响应性排程，可以在多变的环境中适应变化以维护可行的排程。交互性排程，可以用甘特图触摸屏手工拖拉工序排程调度。

 

高级排程需要可以处理以下难度：

 

1、种类繁多，多品种、变批的复杂情况

2、标准工艺路线与具有特点的工艺路线混合

3、工序可能有加工时间、准备时间、等待排队时间、移动搬运时间及固定偏置时间等

3、每道工序可选设备，设备可选模具、刀具、选工装、选物料，选特类的人员

4、具有班次（三班）的考虑，可以加班，也可以加不整的班。

5、工序之间流转一般采用平行移动模式。

6、加工任务可以被抢占，可以快速切换，有切换时间的约束

7、满足交期的前提下，工艺、设备、工装、人员、物料等不确定因素的优化组合

8、加权多目标权衡优化，但也受到决策者偏好的影响。

 

APS的排程方法很多，最常用的有正排和倒排两种方法或是将两者混合使用。

 

一、排产的逻辑

 

每一个要进行排产的最终订单都具有一个承诺日期，该日期是通过订单承诺CTP（capable to promise）确定的。排产算法的逻辑按照如下方式对每一个订单进行操作：

 

（1） 自动识别关键路径

 

（2）从承诺日期反向开始，并且保留每道工序需要的工作中心的能力和物料。如果所需要的物料是已经生产的组件，则同样从其需求点开始对其进行反向计划。如果在此途径结束时，开始日期在排产时间范围的开始或之后，则继续执行下一个订单。

 

（3）如果反向途径失败，则意味着生成的开始日期可能已经过去，则从计划开始日期保留能力和物料。如果生成的截止日期在计划时间范围内（虽然有可能在承诺日期之后，）则完成对此订单的计划。如果反向和正向途径都失败，则不将该订单包括在计划期间内。

 

二、规则算法的演绎

 

以“方桌”任务为例。方桌的工艺路线我们已经给出。假定现在是6月13日，我们接到两个订单(C001和C002)，各订购方桌100套，交货期分别为6月16和6月17日。为简明起见，再假定所有涉及的采购物料都不短缺，且目前所有工作中心资源均未被占用，我们试着用APS的顺排正排的方法为它们安排主生产排产。

 

（1）将所有任务按优先级排序形成任务队列

 

在处理所有的任务时必须遵循一定的顺序，该顺序取决于一定的规则。主要包括要求完成日期、先到先服务、加工时间、下达日期等，这些规则可以按需要单独使用，也可以组合使用。为简明起见,我们按订单要求的交货期确定优先级，交货期早的优先级高。因此任务队列的顺序是C001 、C002。

 

（2）取第一个任务

 

计算该各工序占用对应工作中心的工作时间的跨度。

 

（3）要求将各个工序放在时间坐标上进行考察，所以首先要计算出各工序占用对应工作中心的时间跨度。

 

计算方法是：占用工作中心时间=加工数量/效率。如下表，我们可以计算出“方桌”任务各工序占用对应工作中心的时间跨度。

 

（4）确定关键路径

 

我们利用上表的数据可以作出任务C001的网络图。我们知道，任务的总时间跨度是由图中的关键路径，即最长路径决定的，因此应该先找出关键路径，确定关键工序，在处理上优先安排资源，才能使排产在整个任务的层次达到最优。

 

关键路径是: 开始- 4(加工面板)- 3(装配桌面)- 1(总装)- 完成

 

如果网络图的节点较多，求解关键路径会比较麻烦，排产系统会自动完成这项工作。在制造窗口中会自动加了粗黑框的工序，就是系统自动求解的关键工序，它们所组成的路径就是关键路径。

 

有时候，在网络图上两条或以上路径所用时间完全相同的，就会出现两条以上的关键路径，对于这种情况，通常可以任意选择一条当作关键路径，优先分配资源，其余的视为非关键路径。

 

当路径之间不存在资源争夺关系（即使用不同的工作中心），各资源的占用情况也相同时，选择哪一条关键路径进行优先处理并不会影响排程的结果，而要是上述条件不满足时，选择不同的关键路径优先处理就有可能得到不同的排程结果。但这种差异并不明显，可能是可以接受的。

 

（5）取第一个关键工序

 

工序4，即“加工面板”

 

（6）确定当前工序最早可开始时间

 

在正排法中工序的最早可开始时间就是当前时间，如果工序所需物料当前短缺，则应加上该工序所需物料的提前期。如果是加工件就是生产加工提前期，如果是采购就是采购提前期。

 

由于工序4没有要投入的加工件，而采购件当前不短缺，故最早可开始时间就是当前（6月13日9：00）。

 

（7）确定资源可用

 

通过确定当前工序最早可开始时间就可以计算其结束时间，那么该工序的排产就算完成了。但实际上还有一个重要的问题没有解决：该工序对应的工作中心资源在该时段的状态可用吗？还是已经被别的任务占用？根据已知，工序4对应的工作中心Shop3未被占用，即状态为“空闲”。

 

（8）确定工序计划开始时间和计划结束时间

 

如果该工序对应的工作中心资源在该时段的状态可用，那么工序的计划开始时间和计划结束时间就分别等于最早开始时间和最早结束时间。如果工作中心资源在该时段已被占用，则我们将当前工序往后移至第一个未被占用的时段，重新确定计划开始时间和计划结束时间。

 

因此工序4的计划开始时刻就是最早可开始时刻，即6月13日9：00。计划结束时刻为计划开始时刻往后推5个工作小时即6月13日14：00。

 

需要注意的是，我们这里使用的是“工作小时”，按照工作日历，如果时间跨度超过了当天的工作时间，超过的部分就要从下一个工作日的工作开始时刻接着计算。

 

（9）设置对应工作中心相应时段的状态为“占用”

 

设定了计划开始时间和计划结束时间后，要将相应时段相应工作中心资源的状态设为“占用”，以免后面的任务在该时段被重复分配：在本例中，我们需要将Shop3从6月13日9:00到14:00的状态设置为“占用”。

 

（10）转向紧后关键工序

 

一个工序的紧前或紧后工序可能不止一个，但我们此处先考虑关键路径上的紧后工序，按照我们在第4步中介绍的方法，这最多只会有一个。安排的方法和前面(3)～(6)是一样的。该过程是一个循环，直到当前任务中所有的关键工序都已被安排。完成对订单C001的关键工序的排程图。

 

（11）转向非关键工序

 

在完成了关键工序的排程后，当前任务的总时间跨度就已经被确定了，接着系统开始转向当前任务的非关键工序。非关键工序的安排在时间上可以有一定的松动，即只要在其紧后工序开始之前结束，并且在其紧前工序结束之后才开始就可以了。因此对非关键工序的排程，我们至少可制定两种规则：

 

一是紧前工序结束后立刻开始本工序；

 

二是本工序开始前紧前工序刚完成。排产系统有时可以让用户选择遵循规则（1）或（2），如果选择规则（2），则相当于关键工序正排，非关键工序倒排。

 

至此，我们完成了任务C001的排程。我们可以看到，Shop4对应的两个工序为非关键工序，在这里采用的是规则（2）。完成对任务C001的排程图

该过程是一个循环，直到当前任务所有的非关键工序都已被安排。

 

（12）转向任务队列中下一个任务，完成了C001所有工序的排程后，排产系统转向任务C002。

 

同样，先安排关键工序，并且也是首先安排工序（4）。我们注意到，此时工序（4）的最早可开始时间同样是6月13日9：00，但Shop3在该时段已被标记为占用，于是排产系统将当前工序的计划开始时刻移动到下一个未被占用时段的开始时刻即6月13日14：00，以此为基准往后推5个工作小时得到计划结束时刻即6月14日11：00。

 

完成对任务C001的安排后,系统开始对任务C002进行排程,同样也是由关键工序开始, 如图:

然后安排非关键工序，最后完成的两个各式各100套“方桌”任务正排计划如图：

该过程是一个循环，直到完成队列中所有的任务都已被安排。

 

在当前的资源条件下，任务的累计提前期不能满足交货期的情况下，正排法会通过推迟部分或全部工序的加工来解决，例如图中Shop1对应的被标为红色的两个工序（即C001的工序（1）和C002的工序（1）的计划就是被延期加工的情况。

 

虽然我们并不希望交货被延迟，但这却是现实约束下的一个可行的方案。

 

三、倒排法

 

倒排法与正排法方法相似但方向相反，从交货期或指定的完成时刻开始，将各工序计划逆时间顺序向前排程。

 

如图，假如我们将订单C001的交货期定为6月21日，那么系统将会从来6月20日工作时间的最后一刻即17:00开始向前排程。结果我们得到的计划是最早开始的工序即工序(4)在6月15日16:00开始。

倒排的特点是在满足完交货期的情况下，加工尽可能迟开始，这符合JIT（just in time）的思想。倒排法的问题是当累计提前期不能满足交货期时，按照刚才的算法将会导致某些工序的开始时间被安排到了“从前”，即计划开始时刻早于当前时刻，显然这是不可行的。

 

四、融合应用

 

从以上的介绍我们可以看到，正排法与倒排法各有利弊，在实际的应用中，有的系统会根据情况自动采用其中哪种方法。例如，当某任务累计提前期不能满足交货期时，系统自动对该计划各工序正排，以便得出一个可行的计划。而相反当累计提前期可以满足交货期时，系统自动对该计划各工序进行倒排，以符合JIT的原则。

 

此外，有的排产系统还允许对关键工序采用正排的方法，而对非关键工序采用倒排的方法，在保证排产计划的可行性和符合JIT之间采取一种折中的方法。

 

图就是一个例子,与前图相比较,工序(4)、（3）、（1）并无变化，而计划由Shop4完成的工序（2）、（5）则采用了倒排法。即关键工序采用正排法，非关键工序采用倒排法。

APS需要自动的替换设备来，满足交期。需要自动的替换工艺路线，来满足交期。需要自动合理安排班次，来满足交期。需要自动跟踪订单完成情况，以避免订单延迟。需要自动调度设备、人员满负荷，满足资源利用率。需要调度模具、夹具的准备情况。需要调度材料短缺与积压。对车间意外状况进行处理。如设备故障、缺料、员工病事假等

 

一般成熟的APS系统的有限排程引擎, 可以同时检查资源能力和物料的可用性。不过，也可以对不同的资源选择有限能力、无限能力。对不同的物料选择有限物料约束、无限物料约束，有限外加工资源约束或无限外加工资源约束。并可以把以上选择组合针对不同复杂的场景以满足企业的多种的优化目标。

 

*来源：蔡颖专著-APS走向实践（2007），P62-Infor 公司的Visual APS

 

.......

更多文章欢迎访问：

公众号： 高效计划与智能调度排程研究会

微信号： APS_Society

网站： www.itapss.cn