1）基本原理与方法
在某些情况下，通过采用成组技术等方法对被加工工件进行分批处理，可使每一批的工件具有相同或相似的工艺路线。此时，由于每个工件均需以相同的顺序通过制造系统中的设备进行加工，因此其调度问题可归结为流水排序调度问题，可通过流水排序方法予以解决。
所谓流水排序，其问题可描述为：设有n个工件和m台设备，每个工件均需按相同的顺序通过这m台设备进行加工。要求以某种性能指标最优为目标，求出n个工件进入系统的顺序。
基于流水排序的调度方法是一种静态调度方法，其实施过程是先通过作业排序到调度表，然后按调度表控制生产过程运行。如果生产过程中出现异常情况，则需要重新排序，再按新排出的调度表继续控制生产过程运行。
实现流水排序调度的关键是流水排序算法。目前在该领域的研究已取得较快进展，研究出多种类型的排序算法，概括起来可分为如下几类：
（1）单机排序算法。
（2）两机排序算法。
（3）三机排序算法。
（4）m机排序算法。
2）N作业单机排序
（1）性能指标。为实现最优作业排序，以作业平均通过时间（mean flow time，MFT）最短作为性能指标。MFT的计算公式如下：
式中，Ci=wi+ti为i作业的完工时间；wi，ti为i作业的等待和加工时间。
（2）实现MFT最短的调度方法。下面将证明，按处理时间最短（shortest processing time，SPT）优先原则排序可使MFT最短。
SPT优先原则的含义是：具有最短加工时间的作业优先加工（处理）。
证明：由图5-17可知，
第2作业的等待时间：w2=t1(www.xing528.com)
第3作业的等待时间：w3=t1+t2
第4作业的等待时间：w4=t1+t2+t3
……
第n作业的等待时间：wn=t1+t2+…+tn-1
总等待时间：
图5-17 作业加工过程
由此可见，加工时间前的权重系数由大到小递减，说明越是排在前面的作业，其加工时间对总等待时间的贡献越大，因此将加工时间最短的作业排在最前面，即按照SPT原则排序，即可使总等待时间最短。
又因为总加工时间
=常数，所以，总等待时间最短，即可保证总通过时间最短，从而使平均通过时间最短。
（3）推论：MFT最小可保证作业平均延误时间（mean lateness，ML）最小。
证明：第作业的延误时间为
式中，di为第i作业的交付时间。
作业的平均延误时间为
式中，d=
为平均交付时间。因为平均交付时间d为常数，所以MFT最小，ML也最小。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
