第六章生产与运作管理(生产作业排序).ppt

1、2020/7/31,第六章 生产作业排序,2020/7/31,一、作业排序的概念 作业排序就是确定工件在设备上的加工顺序，使预定的目标得以实现的过程。 二、作业排序的目标 1、总流程时间最短 流程时间=加工时间+等待时间+运输时间 2、平均流程时间最短 3、平均在制品占用量最小 4、最大延迟时间最短 5、平均延迟时间最短 6、延迟工件最少,2020/7/31,三、排序问题的分类 （一）按照机器数目的不同 1、单台机器的排序问题 2、多台机器的排序问题 按照工件加工路线的不同，又可以分为： 流水型（flow shop)的排序问题 所有工件的工艺路线都相同 非流水型（job shop)的排序问题

2、每个工件的工艺路线各不相同 （二）按照工件的到达情况的不同 1、静态排序当排序时，所有的工件都已到达，并已准备就绪，可以对全部工件进行一次性排序。 2、动态排序若工件陆续到达，要随时安排它们的加工顺序。,2020/7/31,（三）按照目标函数的不同 1、平均流程时间最少 2、延期工件最少,2020/7/31,四、单台设备上的作业排序方法,排序规则： （1）最短加工时间优先规则SPT(Shortest processing time) （2）最短交货期优先规则EDD(Earliest due date) （3）先到先加工规则FCFS(First come first served) （4）最小松

3、动时间优先规则STR(Slack time remaining)（松动时间=交货期-加工时间） （5）临界比率最小优先规则SCR(Smallest critical ratio) 交货期当前日期 作业时间 （6）综合规则（综合使用两种规则，如先按照交货期优先排序，然后按照最短加工时间优先的原则排序） （7）后到先加工规则 （8）随机规则 （9）延迟工件最少的规则（Moore法则）,CR=,2020/7/31,以上这些规则各有其特点，不同的规则适用于不同的目标。例如，FCFS规则比较公平；SPT规则可使平均流程时间最短，从而减少在制品数量；EDD规则可使工件的最大延迟时间最小、平均延误时间最小；

4、Moore法则可使延迟的工件数最少等。,FCFS、SPT、EDD优先规则的应用,【例6-1】下表是在某工作中心等待加工的6项作业的加工时间（包含换产时间）与预定日期，假设工作的到达顺序与表中顺序相符 。根据以下规则来决定其作业顺序：FCFSSPTEDD并对它们分别进行评价。,按FCFS规则排序,排序的结果是A-B-C-D-E-F。,按SPT规则,作业顺序是A-C-E-B-D-F,按EDD规则,作业顺序是C-A-E-B-D-F,不同排序规则的结果分析,2020/7/31,排序规则的比较： 1、SPT规则，可以使作业流程时间最短，使滞留在加工过程的平均在制品占用量最少，有利于节约流动资金，节约厂房

5、、仓库面积和保管费用。但是，由于未考虑交货期，所以可能发生交货延期。 2、EDD规则，平均延迟天数最少，减少违约罚款损失，但缺点是平均流程时间增加，不利于节约在制品占用资金。 3、FCFS规则，主要问题是加工时间过长。但其使用简单，且体现公平，常用于服务业的排队系统。,2020/7/31,五、流水生产线作业排序方法 1、 Flow-shop排序问题的描述,假设： （1）一个工件不能同时在不同机器上加工。 （2）工件在加工过程中采用平行移动方式（当上一道工序完成后立即进入下道工序）。 （3）不允许中断，工件一旦进入加工状态，一直加工完成为止，中途不插入其他工件。 （4）每道工序只在一台设备上加工

6、。 （5）工件数、机器数与加工时间已知。 （6）每台设备同时只能加工一个工件。,2020/7/31,2、多项作业、两台机器的排序- Johnson方法,N项作业，2台机器，所有工件的加工路线都相同。（S.M.Johnson，1954，）,A,B,目标：使全部完工时间最小。 条件：每种工件在每台机器上的加工时间均为已知。,2020/7/31,Johnson方法,步骤： 1.选择最短的作业时间； 2.如果最短时间的作业在第1个加工中心，则安排在最前面，若在第2个加工中心，则安排在最后； 3.在等待的队列中，取消第2步安排了的作业； 4.重复1，2，3步。,2020/7/31,【例6-2】五台仪器修

7、复作业排序,某公司在一次火灾中损坏了5台仪器，这些仪器的修复需要经过如下2道工序： （1）将损坏的仪器运至修理车间，拆卸开； （2）清洗仪器部件，更换报废部分，装配，测试，并送回原车间。 每台仪器在两个工序的各自所需时间如表所示。两道工序分别由不同的人担当。由于原车间没有这5台仪器就无法恢复生产，所以希望找到一个较好的排序方案，使全部修理时间尽可能短。,仪器,工序1 工序2,Y1 Y2 Y3 Y4 Y5,12 4 5 15 10 22 5 3 16 8,2020/7/31,解：,原则： 1.找min，前道工序-最前 后道工序-最后 2.若多个min,任选。 Y3 Y2-Y3 Y2- Y5-Y3

8、 Y2-Y1- Y5-Y3 Y2-Y1-Y4- Y5-Y3,仪器,工序1 工序2,Y1 Y2 Y3 Y4 Y5,12 4 5 15 10 22 5 3 16 8,2020/7/31,仪器,工序1 工序2,Y1 Y2 Y3 Y4 Y5,12 4 5 15 10 22 5 3 16 8,Y2-Y1-Y4-Y5-Y3,作业排序结果的图示：,机器空闲,Y2,Y2,Y1,4,Y1,4,38,Y4,16,31,Y4,54,Y5,41,Y3,46,Y5,62,9,Y3,65,16,0,0,工序1,工序2,机器空闲,2020/7/31,【例6-3】某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在

9、设备上的加工时间如下表所示。求总加工周期最短的作业顺序。,2020/7/31,解：由约翰逊法可知，表5-8中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得： J4 - * - * - * - * 去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J

10、3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后得 J4 - J2 - J3- J5 - J1,2020/7/31,(a) J1 - J2 - J3- J4 - J5,(b) J4 - J2 - J3- J5 - J1,可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业顺序总加工周期是26，显然后者的结果优于前者。,服务作业计划,人员班次计划,将服务员工安排到不同的服务需求时间上的作业计划是服务员工轮班问题。 1、单班次问题：每天只有一个班次，部门每天都要营业 （1）启发方法: 如循环排序法 （2）最优化方法:如整数线性规划法 (3）解析法 2、多班次问题：每天有

11、多班，一般为两班或三班,（1）循环排序法,循环排序法是一种既简单又实用的启发式方法，其基本步骤如下： 1、从每周的员工需求人数中找到所需员工数量之和最小的连续两个工作日,安排一名员工在这两天中休息。 若有相同的两个最小总需求量，则可任选其一；或按照预先约定好的方法选择其一，如优先选择周六周日。 2、使该两天的需求人数保持不变, 其他日期的需求人数减1(如果是0不变) 3、在新一行中找出所需员工数量最少的连续两天，并再次循环。将下一名员工分配到剩余的工作日中。 4、重复上述过程（步骤2和3），直到所有的人员需求得到满足。,【例6-4】邮局一周内每天的员工需求如表6-1所示。工会要求每名员工连续工

12、作五天，然后连续休息两天。试制定排班计划。,表6-1 一周内每天的员工需求量,解：,表6-2 每周员工安排表（循环排序法）,（2）线性规划法,（3）单班次问题的解析法 (Brownell and Lowerre,1976) 求解以下问题的单班次人员安排问题： 1、保证每人每周休息两天 2、保证每人每周连休两天 3、保证每人每周休息两天 ，隔一周在周末休息 4、保证每人每周连休两天，隔一周在周末休息,1、保证每人每周休息两天 设某单位每周工作7天，每天一班，平常日需要N人，周末需要n人。 W表示所需劳动力下限。 求解步骤： （1）Wi = max n , N+ 2n / 5 （2）安排Wi n

13、名工人在周末休息； （3）对余下的n名工人从1到n编号，1号至Wi N号工人周一休息； （4）安排紧接着的Wi N名工人第二天休息，这里，工人1紧接着工人n ； （5）如果5 Wi 5N + 2n ，则有多余的休息日供分配，此时可按需要调整班次计划，只要保证每名工人一周休息两天，平日有N人当班即可。,工人1,工人9,工人8,工人7,工人6,工人5,工人4,工人3,工人2,日,六,五,四,三,二,一,日,六,五,四,三,二,一,【例1】 设N=5，n = 8，求班次安排。 （1）W1= max 8 , 5+ 28 / 5 = 9， （2）W1-n=9-8=1名工人在周末休息 ； （3）W1-N=

14、9-5=4名工人在周一休息,解,2、保证每人每周连休两天,求解步骤： W2 = max n , N + 2n / 5 , ( 2N + 2 n ) / 3 （1）利用上式计算W2，给W2名工人编号； （2）取k = max 0 , 2N +n - 2 W2 ； （3）1至k号工人（五，六）休息，（k + 1 ） 2 k号工人（日，一）休息，接下来的 W2 n k 名工人周末（六，日）休息； （4）对余下的工人，按（一，二），（二，三），（三，四），（四，五）的顺序安排连休，保证有N名工人在平常日当班。,【例2】 对于N=6，n=5，求班次安排。 1、W2 =max 5 , 6 + 25 / 5

15、 , ( 26 + 2 5 ) / 3 =8 2、k = max 0 , 26 +5 - 2 8 =1。 3、1k（1）号工人（五、六）休息；k+12k（2）号（日、一）休息；接下来W2-n-k（8-5-1=2）名工人（六、日）休息 4、余下的工人按（一、二）,（二、三）, （三、四）, （四、五）,工人1,工人8,工人7,工人6,工人5,工人4,工人3,工人2,日,六,五,四,三,二,一,日,六,五,四,三,二,一,解,3、保证每人每周休息两天 ，隔一周在周末休息,求解步骤： W3 = max 2n , N + 2n / 5 ： 1、将W3 - 2 n 名工人安排周末休息； 2、将余下的2

16、n名工人A、B两组，每组 n名工人，A组的工人第一周周末休息，B组的工人第二周周末休息； 3、按照条件一 每周休息两天的步骤（3）和（4），给A组工人分配第二周的休息日。如果5 W35N + 2n ，可以先安排1至W3 N 号工人周五休息，按周五、周四、周一的顺序安排休息日； 4、B组的n名工人第一周的班次计划与A组的第二周安排计划相同。,【例3】 N=7，n = 4，求班次安排。 解：W3 = 9，W3 - 2n = 1名工人周末休息， 剩下 2n（8）名分成A、B两组，A组第1个周末休息，B组第2个周末休息。,工人1,工人9,工人8,工人7,工人6,工人5,工人4,工人3,工人2,日,六,五,四,三,二,一,日,六,五,四,三,二,一,4、保证每人每周连休两天，隔一周在周末休息,求解步骤： W4 = max 2n , N + 2n / 5 ，（4N + 4 n）/ 5 （1）将W4名工人分成A、B两组：A组W4 / 2名工人，第一周周末休息；B组（W4 W4 / 2 ）名工人，第二周周末休息。 （2）k = max 0 , 4N + 2n 4 W4 ，A组中k/2名工人（五2，六2）休息，k/2名工人（日2，一3）k/2名工人；B组中k/2名工人（五1，六1）休息，k/2名工人（日1，一2）休息。 （3）在保证周末有n人当班，平日有N人当班的前提下，对A组