第十四章作业排序.pptVIP

第十四章 作业排序 当多项任务（零件）排队等候某个工作中心加工时，哪项任务应当优先安排？这就是作业优先次序安排（简称为作业排序）要解决的问题。 1、排序规则 常用的排序规则有； ①先到先服务规则(FCFS 排序)：即任务的处理顺序是按照其到达工作中心的先后次序依次进行。 ②最短作业时间规则(SPT 排序)：即在所有排队等候某个工作中心加工的任务中，选择作业时间（准备时间十加工时间）最短的那一件最先加工。 第十五章 作业排序 ③超限最短加工时间规则：即事先设定一个排队等候时间限度．对于等候时间超过此时间限度的任务，优先安排其中作业时间最短的任务。如果没有哪项任务的排队等候时间超限，则按最短作业时间规则排序。 ④最早到期规则：即在所有排队等候某个工作中心加工的任务中，按照计划交货期从早到晚的顺序，最先安排计划交货期最早的任务，而不管该项任务何时到达该工作中心。 　⑤最短松弛时间规则：所谓松弛时间，等于某项任务距离计划交货期的剩余时间与该项任务的作业时间之差。而最短松弛时间规则，是将最高优先级分派给具有最短松弛时间的任务，而不管其计划交货期的早晚。 第十五章 作业排序 例： 假设任务是按字母顺序依次同时到达某个工作中心的．即A任务第1个到达；其次是B任务；等等。顾客要求的交货日期（或计划交货日期）和各项任务的作业时间均列示于表中。表还列出了每项任务的通过时间，所谓通过时间是任务在系统中的排队等候时间与作业时间之和。 　　　下面我们以平均通过时间、系统中每天的平均任务数（包括等候的任务和正处于加工中的任务）和任务的平均延迟时间三项指标，分别对先到先服务、按最短作业时间规则和按最短松弛时间规则的排序结果进行评价。 ①按先到先服务规则排序 a.全部完成时间为55天。 b.平均通过时间为31．8天。其计算过程如下： （4＋21＋35＋44＋55）÷5= 31．8（天） c.系统中每天的平均任务数为2．89。 [5×4+4×17+3×14+2×9+1×11] ÷55 = 2．89（件／天） d.任务的平均延迟时间为18.6天。 （0十1＋17十32十43）÷5＝18．6（天） ② 按最短作业时间规则对其排序结果如表所示 a.全部完成时间为55天。 b.平均通过时间计算过程如下： （4＋13＋24＋38＋55）÷5= 26.8（天） c.系统中每天的平均任务数计算方法如下： 　 [5×4+4×9+3×11+2×14+1×17]÷55=2.44（件／天） d. 任务的平均延迟时间计算如下： 　﹝0+1+12+20+35﹞÷5=13.6﹝天﹞ ③按最短松弛时间规则排序其结果如表所示 a.全部完成时间为55天。 b.平均通过时间计算过程如下： （11＋15＋32＋41＋55）÷5= 30.8（天） c.系统中每天的平均任务数计算方法如下： [5×11+4×4+3×17+2×9+1×14]÷55=2.8（件／天） d. 任务的平均延迟时间计算如下： 　﹝0+9+12+29+37﹞÷5=17.4﹝天﹞ 第十五章 作业排序 通过比较三种规则的排序结果，我们发现最短作业时间规则的效果最好。虽然每种规则的全部作业时间都是55天，但最短作业时间规则具有较低平均通过时间，由于任务在系统中平均逗留的时间较短。故系统的在制品库存较低，以及顾客（零件）服务质量较高；又由于系统中平均任务数较少，使得系统较少出现堵塞现象；此外，平均延迟时间较短说明交货比较及时。 　　　最短作业时间规则具有较优越的排序效果，这不是本例中的一种偶然现象．而是一种一般的特征。 第十五章 作业排序 2、作业排序 　﹝1﹞??n个工件在一台设备上加工 这是一种最简单的排序问题，排序规律是加工工时短的工件先加工。 　﹝2﹞　n个工件需经过二台设备加工 比较简单的一种情况是所有工件在二台设备上加工的次序相同，此时用约翰逊法可以求解。 　排序规则： 　第一步，取出最小工时tmin，若该工时为第一工序的，则最先加工；反之，则放在最后加工。　 　第二步，将该已排序工件划去。 　第三步，对余下的工件重复上述排序步骤，直至完毕。 例：有五个工件在二台设备上加工，加工顺序相同，先在设备1上加工，再在设备2加工，工时列于表，用约翰逊法排序。  第十五章 作业排序 ﹝3﹞n个工件在三台设备上加工 随着设备数量的增加，优化难度加大。在三台设备上加工，当满足一定条件时有优化方法。如果n个工件的加工顺序相同，且满足以下两条件中的任何一条，可用约翰逊法求解。 Min｛