11.作业排序.ppt

第11章 作业排序 目的和要求 了解作业排序的概念 理解作业排序的作用和目标 了解作业排序的分类和有限原则 掌握n/1作业排序问题 掌握n/2作业排序问题 了解n/m作业排序问题 了解服务业的作业排序问题 作业排序概念 作业排序(job sequencing)是指为每台设备、每位员工具体确定每天的工作任务和工作顺序的过程。 作业排序要解决不同工件在同一设备上的加工顺序问题、不同工件在整个生产过程中的加工顺序问题，以及设备和员工等资源的分配问题。 不同的作业排序，可能会导致差别很大的结果。 表10.1 4种部件的加工定额工时 如何具体地组织生产活动、安排作业顺序和及时反馈信息，对生产活动进行调整与控制，使各种资源得到合理利用，同时又能按期完成各项订单任务，是作业排序与控制所需要研究和解决的问题。 作业排序的主要目标包括: (1)满足交货日期的需要 (2)降低在制品库存，加快流动资金周转 (3)缩短提前期 (4)降低机器设备的准备时间和准备成本 (5)充分利用机器设备和劳动力 作业排序问题的分类 作业排序的优先规则 (1)最短加工时间规则——SPT (2)最早到期规则—— EDD (3)先到先服务规则——FCFS (4)最小关键比例规则——SCR (5)最少工作量规则——LWKR (6)最多工作量规则——MWKR 制造业中的n/m作业排序问题 1.n/1作业排序 n/1作业排序问题指n种工件在单台设备上加工的排序问题。 排序问题的难度随着工作地(或机器设备)数量的增加而增大，而并非随着需加工的工件种类数的增加而增大。 在评价作业排序方案时，工件流程时间、工件延期交货天数、时间跨度和平均工件库存数是几个主要的绩效评价指标。 例如，某加工车间要为2003年9月加工的6批 产品进行作业排序，每批的件数相同，都是1000件，公司对各种产品的加工时间都设定了定额工时，销售部门提出了各种产品的预定交货期，如表10. 2所示。 n/2排序问题 n/2排序问题是指n种工件在两台机器设备(或工作地)上进行加工的排序问题。 假设有n种工件的加工要经过两台设备，并且所有工件的加工路线都相同。 在这种情况下，全部完工时间是一个关键的评价标准，排序的目标是使全部完工时间最短。 约翰逊算法的适用条件是: (1)排序的目标函数是要使全部完工时间最小; (2)工件在两台设备上的加工顺序完全相同; (3)所有工件同时到达第一台设备等待加工; (4)每种工件在每台设备上的加工时间均已知。 约翰逊算法的基本思路在于:尽量减少第二台设备上的等待加工的时间，因此，在第二台设备上加工时间长的工件先加工，在第二台设备上加工时间短的工件后加工。 约翰逊算法的步骤如下: (1)先作n个工件在两台设备上的加工时间的工时矩阵M: 其中， aij为工件j（1, 2, …n）在设备i(1, 2)上的加工时间。 (2)在工时矩阵M中找出最小元素aij，若最小元素不止一个，可任选其一。 (3)如果最小元素aij在上行，即最短的加工时间出现在第一台设备上，则对应的工件应排在最前位置;如果最小元素向在下行，即最短的加工时间出现在第二台设备上，则对应的工件排在最后位置。 (4)从加工时间矩阵中划去已排序的工件，然后对余下的工件重复步骤(2) 和步骤(3) ，直到全部工件都被安排完。 例如，有6个产品(A、B、C、D、E、F)需要在车床和磨床上加工，加工顺序是先车后磨，每个产品所需的加工时间如表10. 8所示，管理者希望找到一个最优的排序方案。 运用约翰逊算法，首先作出6种工件在车床和磨床上的加工工时矩阵M: 在M中寻找到的最小值为2，对应的产品为B，对应的设备为磨床，因此，应 将产品B排在最后加工。在M中划去产品B，得余下的工时矩阵M1 : 在M1中寻找到的最小值为3，对应的产品为A，对应的设备为车床，因此应将产品A排在最早加工。在M1中划去产品A，得余下的工时矩阵M2: 在M2中找到的最小值为4，对应的产品分别为C和D，其对应的设备分别为车床和磨床，因此，应将产品C排在产品A之后加工，而将产品D排在产品B之前加工。在M2中划去户品C和D，得余下的工时矩阵M3: 在M3中找到的最小值为5，对应的产品为F，对应的设备为磨床，因此，应将F排在工件D之前加工，将E排在产品C之后加工。因此，加工排序为A-C-E-F-D-B，总的加工时间为39小时。 n /m排序问题 n/m(m≥3)的流水作业排序是一个复杂的问题。对于一般的流水作业排序问题，可以采用枚举法，保证得到n/m排序问题的最优解。 但当n和m的数值很大时，该问题的计算量相当大，为求最优解而付出的代价是不经济的。 CDS法和Palmer法是两种常用