第十四章作业排序

1、 第十四章第十四章 作业排序作业排序 当多项任务（零件）排队等候某个工作中心加工时，哪项任务应当优先安排？这就是作业优先次序安排（简称为作业排序）要解决的问题。 1、排序规则 常用的排序规则有； 先到先服务规则(FCFS 排序排序)：即任务的处理顺序是按照其到达工作中心的先后次序依次进行。 最短作业时间规则(SPT 排序排序)：即在所有排队等候某个工作中心加工的任务中，选择作业时间（准备时间十加工时间）最短的那一件最先加工。 第十五章第十五章 作业排序作业排序 超限最短加工时间规则：即事先设定一个排队等候时间限度对于等候时间超过此时间限度的任务，优先安排其中作业时间最短的任务。如果没有哪项任务

2、的排队等候时间超限，则按最短作业时间规则排序。 最早到期规则：即在所有排队等候某个工作中心加工的任务中，按照计划交货期从早到晚的顺序，最先安排计划交货期最早的任务，而不管该项任务何时到达该工作中心。最短松弛时间规则：所谓松弛时间，等于某项任务距离计划交货期的剩余时间与该项任务的作业时间之差。而最短松弛时间规则，是将最高优先级分派给具有最短松弛时间的任务，而不管其计划交货期的早晚。 第十五章第十五章 作业排序作业排序例： 假设任务是按字母顺序依次同时到达某个工作中心的即A任务第1个到达；其次是B任务；等等。顾客要求的交货日期（或计划交货日期）和各项任务的作业时间均列示于表中。表还列出了每项任务的

3、通过时间，所谓通过时间是任务在系统中的排队等候时间与作业时间之和。 下面我们以平均通过时间、系统中每天的平均任务数（包括等候的任务和正处于加工中的任务）和任务的平均延迟时间三项指标，分别对先到先服务、按最短作业时间规则和按最短松弛时间规则的排序结果进行评价。 按先到先服务规则排序按先到先服务规则排序 a.全部完成时间为55天。b.平均通过时间为318天。其计算过程如下： （421354455）5= 318（天） c.系统中每天的平均任务数为289。 54+417+314+29+111 55 = 289（件天） d.任务的平均延迟时间为18.6天。 （0十117十32十43）5186（天） 任务

4、的优先次序作业时间通过时间交货期从现在算起ABCDE41714911421354455620181212 全部完成55 按最短作业时间规则对其排序结果如表所示按最短作业时间规则对其排序结果如表所示a.全部完成时间为55天。b.平均通过时间计算过程如下： （413243855）5= 26.8（天）c.系统中每天的平均任务数计算方法如下： 54+49+311+214+11755=2.44（件天） d. 任务的平均延迟时间计算如下：0+1+12+20+355=13.6天 任务的优先次序作业时间通过时间交货期从现在算起ADECB49111417413243855612121820 全部完成55按最短松

5、弛时间规则排序其结果如表所示按最短松弛时间规则排序其结果如表所示a.全部完成时间为55天。 b.平均通过时间计算过程如下： （1115324155）5= 30.8（天）c.系统中每天的平均任务数计算方法如下：511+44+317+29+11455=2.8（件天）d. 任务的平均延迟时间计算如下：0+9+12+29+375=17.4天 任务的优先次序作业时间松驰时间通过时间交货期从现在算起EABDC11417914123341115324155126201218 全部完成55B和D调换顺序后的结果：a.全部完成时间为55天。b.平均通过时间计算过程如下： 29.2（天）c.系统中每天的平均任务数

6、计算方法如下： 2.65（件天）d. 任务的平均延迟时间计算如下：15.8天 平均通平均通过时间过时间（天）（天）系统中每系统中每天的平均天的平均任务数任务数（件（件/天）天）任务的平任务的平均延迟时均延迟时间（天）间（天）先到先服务规则先到先服务规则31.82.8918.6最短作业时间规则最短作业时间规则26.82.4413.6最短松弛时间规则最短松弛时间规则30.82.817.4三种规则的排序结果三种规则的排序结果 第十五章第十五章 作业排序作业排序 通过比较三种规则的排序结果，我们发现最短作业时间规则的效果最好。虽然每种规则的全部作业时间都是55天，但最短作业时间规则具有较低平均通过时间

7、，由于任务在系统中平均逗留的时间较短。故系统的在制品库存较低，以及顾客（零件）服务质量较高；又由于系统中平均任务数较少，使得系统较少出现堵塞现象；此外，平均延迟时间较短说明交货比较及时。最短作业时间规则具有较优越的排序效果，这不是本例中的一种偶然现象而是一种一般的特征。 第十五章第十五章 作业排序作业排序 2、作业排序1 n个工件在一台设备上加工 这是一种最简单的排序问题，排序规律是加工工时短的工件先加工。2n个工件需经过二台设备加工 比较简单的一种情况是所有工件在二台设备上加工的次序相同，此时用约翰逊法可以求解。排序规则：第一步，取出最小工时tmin，若该工时为第一工序的，则最先加工；反之，则放在最后加工。第二步，将该已排序工件划去。第三步，对余下的工件重复上述排序步骤，直至完毕。 例：有五个工件在二台设备上加工，加工顺序相同，先在设备1上加工，再在设备2加工，工时列于表，用约翰逊法排序。 工件作业工时tij设备1设备2ABCDE5374626534B C E D A B C E D A 2 4 6 8 10 11 12 14 16 18 20 22 24 26 28 加工周期为：27 第十五章第十五章 作业排序