《生产计划管理与控制.pptx》由会员分享，可在线阅读，更多相关《生产计划管理与控制.pptx（119页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、重点掌握重点掌握本章内容n排序规则和评价标准排序规则和评价标准n不同移动方式下的生产周期计算不同移动方式下的生产周期计算n生产作业排序（约翰逊算法）生产作业排序（约翰逊算法）n项目作业计划项目作业计划第一节第一节第一节第一节 生产作业计划概述生产作业计划概述生产作业计划概述生产作业计划概述第二节第二节第二节第二节 排序问题概述排序问题概述排序问题概述排序问题概述第三节第三节第三节第三节 作业排序的规则作业排序的规则作业排序的规则作业排序的规则第四节第四节第四节第四节 制造业中的排序问题制造业中的排序问题制造业中的排序问题制造业中的排序问题第五节第五节第五节第五节 生产作业控制生产作业控制生产作
2、业控制生产作业控制第六节第六节第六节第六节 项目作业计划项目作业计划项目作业计划项目作业计划第1页/共119页第一节第一节 生产作业计划概述生产作业计划概述一、什么是生产作业计划？一、什么是生产作业计划？作业计划就是安排零部件（作业、活动）的加工顺序、出产数量、设备及人工使作业计划就是安排零部件（作业、活动）的加工顺序、出产数量、设备及人工使用、投入时间及出产时间的计划。用、投入时间及出产时间的计划。第2页/共119页在空间上把生产任务细在空间上把生产任务细分到车间、工段、班组、分到车间、工段、班组、机台和个人；机台和个人；在时间上把年、季较长在时间上把年、季较长计划期的任务细分到月、计划期的
3、任务细分到月、旬、周、日、轮班和小旬、周、日、轮班和小时时在计划单位上把产品细在计划单位上把产品细分到零件和工序分到零件和工序第3页/共119页二、编制作业计划与排序二、编制作业计划与排序由于编制作业计划的主要问题是确定各台机器由于编制作业计划的主要问题是确定各台机器上工件的加工顺序，因此上工件的加工顺序，因此“排序排序”很多时候等很多时候等同于同于“编制作业计划编制作业计划”作业计划常涉及到另外几个概念：作业计划常涉及到另外几个概念：派工派工赶工赶工调度调度控制控制排程排程工艺路线工艺路线第4页/共119页“排序排序排序排序”，确定工件在机器上的加工顺序，确定工件在机器上的加工顺序，确定工件
4、在机器上的加工顺序，确定工件在机器上的加工顺序“编制作业计划编制作业计划编制作业计划编制作业计划”，确定每个工件在机器上的加工顺序，确定每个工件在机器上的加工顺序，确定每个工件在机器上的加工顺序，确定每个工件在机器上的加工顺序，同时确定机器加工每个工件的开始时间和完工时间。同时确定机器加工每个工件的开始时间和完工时间。同时确定机器加工每个工件的开始时间和完工时间。同时确定机器加工每个工件的开始时间和完工时间。“派工派工派工派工”，是按作业计划的要求，将具体生产任务安排，是按作业计划的要求，将具体生产任务安排，是按作业计划的要求，将具体生产任务安排，是按作业计划的要求，将具体生产任务安排到具体的
5、机床上加工。到具体的机床上加工。到具体的机床上加工。到具体的机床上加工。“赶工赶工赶工赶工”，是实际进度已落后于计划进度时采取的行动。，是实际进度已落后于计划进度时采取的行动。，是实际进度已落后于计划进度时采取的行动。，是实际进度已落后于计划进度时采取的行动。“加工路线加工路线加工路线加工路线”是工件加工的工艺过程决定的，是工件加是工件加工的工艺过程决定的，是工件加是工件加工的工艺过程决定的，是工件加是工件加工的工艺过程决定的，是工件加工在技术上的约束。比如，工件要经过车、铣、刨、磨、工在技术上的约束。比如，工件要经过车、铣、刨、磨、工在技术上的约束。比如，工件要经过车、铣、刨、磨、工在技术上
6、的约束。比如，工件要经过车、铣、刨、磨、钻的路线加工，我们可以用钻的路线加工，我们可以用钻的路线加工，我们可以用钻的路线加工，我们可以用M1M1M1M1、M2M2M2M2、M3M3M3M3、M4M4M4M4、M5M5M5M5来表来表来表来表示。加工顺序则表示每台机器加工示。加工顺序则表示每台机器加工示。加工顺序则表示每台机器加工示。加工顺序则表示每台机器加工n n n n个工件的先后顺序，个工件的先后顺序，个工件的先后顺序，个工件的先后顺序，是排序、编制作业计划、派工等要解决的问题。是排序、编制作业计划、派工等要解决的问题。是排序、编制作业计划、派工等要解决的问题。是排序、编制作业计划、派工等
7、要解决的问题。第5页/共119页第二节第二节 排序问题概述排序问题概述一、为什么会出现排队现象？一、为什么会出现排队现象？一、为什么会出现排队现象？一、为什么会出现排队现象？二、一个排序的例子二、一个排序的例子二、一个排序的例子二、一个排序的例子三、排序的目标三、排序的目标三、排序的目标三、排序的目标四、排序问题的分类和表示四、排序问题的分类和表示四、排序问题的分类和表示四、排序问题的分类和表示第6页/共119页等待是日常生活的一部分等待是日常生活的一部分第7页/共119页什么时候需什么时候需要排队？要排队？第8页/共119页第9页/共119页一、为什么会出现排队现象？一、为什么会出现排队现象
8、？假定每小时平均有假定每小时平均有假定每小时平均有假定每小时平均有4 4 4 4个工件到达，机器加工每个工件的平均个工件到达，机器加工每个工件的平均个工件到达，机器加工每个工件的平均个工件到达，机器加工每个工件的平均时间为时间为时间为时间为15151515分钟。如果工件到达的间隔时间正好是分钟。如果工件到达的间隔时间正好是分钟。如果工件到达的间隔时间正好是分钟。如果工件到达的间隔时间正好是15151515分钟，而分钟，而分钟，而分钟，而机器加工每个工件的时间也正好是机器加工每个工件的时间也正好是机器加工每个工件的时间也正好是机器加工每个工件的时间也正好是15151515分钟，那么，就只需要分钟
9、，那么，就只需要分钟，那么，就只需要分钟，那么，就只需要一台机器，工件也根本用不着等待。一台机器，工件也根本用不着等待。一台机器，工件也根本用不着等待。一台机器，工件也根本用不着等待。在以下情况将出现排队现象：在以下情况将出现排队现象：在以下情况将出现排队现象：在以下情况将出现排队现象：平均到达率（工件平均到达率（工件平均到达率（工件平均到达率（工件/小时）高于平均服务率（工件小时）高于平均服务率（工件小时）高于平均服务率（工件小时）高于平均服务率（工件/小小小小时时时时)工件到达的间隔时间不一样工件到达的间隔时间不一样工件到达的间隔时间不一样工件到达的间隔时间不一样 机器加工时间不一样机器加
10、工时间不一样机器加工时间不一样机器加工时间不一样工件工件工件工件到达到达到达到达 机器设备机器设备机器设备机器设备工件工件工件工件排队排队排队排队工件工件工件工件离开离开离开离开第10页/共119页二、一个排序的例子二、一个排序的例子四种型号的电视机的装配工时定额型号型号部装定额工时部装定额工时（小时）（小时）总装定额工总装定额工时（小时）时（小时）A A A AB B B BC C C CD D D D151515158 8 8 86 6 6 6121212124 4 4 4101010105 5 5 57 7 7 7第11页/共119页第12页/共119页第13页/共119页第14页/共1
11、19页部部装装B B B B（8 8 8 8）C(6)C(6)C(6)C(6)D D D D（12121212）总总装装 A(4)A(4)A(4)A(4)B B B B（10101010）C(5)C(5)C(5)C(5)D(7)D(7)D(7)D(7)（a a）装配顺序为A AB BC CD D，总装配时间为4848小时部部装装C C C C（6 6 6 6）B B B B（8 8 8 8）总总装装 C(5)C(5)C(5)C(5)B B B B（10101010）D D D D（7 7 7 7）（b b）装配顺序为C CB BD DA A，总装配时间为4545小时部部装装C C C C（6
12、6 6 6）B B B B（8 8 8 8）总总装装 D D D D（7 7 7 7）C(5)C(5)C(5)C(5)B(10)B(10)B(10)B(10)（c c）装配顺序为D DC CA AB B，总装配时间为5151小时A A A A（15151515）A A A A（15151515）A A A A（15151515）A(4A(4A(4A(4)A(4)A(4)A(4)A(4)D D D D（12121212）D(12)D(12)D(12)D(12)第15页/共119页三、排序的目标三、排序的目标第16页/共119页第17页/共119页排序的目标排序的目标满足交货期满足交货期缩短生产周
13、期缩短生产周期降低准备成本降低准备成本降低在制品库存降低在制品库存充分利用资源充分利用资源作业排序作业排序作业排序作业排序第18页/共119页四、排序问题的分类和表示四、排序问题的分类和表示（一）分类（一）分类（一）分类（一）分类排排排排序序序序问问问问题题题题的的的的分分分分类类类类服务业的排序问题服务业的排序问题服务业的排序问题服务业的排序问题流水作业排序问题流水作业排序问题流水作业排序问题流水作业排序问题制造业的排序问题制造业的排序问题制造业的排序问题制造业的排序问题服务者排序问题服务者排序问题服务者排序问题服务者排序问题服务对象排序问题服务对象排序问题服务对象排序问题服务对象排序问题多
14、服务者排序问题多服务者排序问题多服务者排序问题多服务者排序问题单服务者排序问题单服务者排序问题单服务者排序问题单服务者排序问题非流水作业排序问题非流水作业排序问题非流水作业排序问题非流水作业排序问题静态作业排序问题静态作业排序问题静态作业排序问题静态作业排序问题动态作业排序问题动态作业排序问题动态作业排序问题动态作业排序问题排序对象排序对象排序对象排序对象行业行业行业行业服务者数量服务者数量服务者数量服务者数量加工路线加工路线加工路线加工路线服务对象到达服务对象到达服务对象到达服务对象到达第19页/共119页（二）排序问题的表示（二）排序问题的表示（二）排序问题的表示（二）排序问题的表示n/m
15、/A/Bn/m/A/Bn/m/A/Bn/m/A/Buu n n n n工件数工件数工件数工件数uu mmmm机器数机器数机器数机器数uu AAAA车间类型（车间类型（车间类型（车间类型（m=1m=1m=1m=1为空白）：为空白）：为空白）：为空白）：pp A=FA=FA=FA=F代表流水作业排序代表流水作业排序代表流水作业排序代表流水作业排序pp A=PA=PA=PA=P代表流水作业排列排序代表流水作业排列排序代表流水作业排列排序代表流水作业排列排序pp A=GA=GA=GA=G代表单件作业排序代表单件作业排序代表单件作业排序代表单件作业排序uu BBBB目标函数目标函数目标函数目标函数第20
16、页/共119页研究排序问题，一般要做以下假设研究排序问题，一般要做以下假设研究排序问题，一般要做以下假设研究排序问题，一般要做以下假设 1 1 1 1、一个工件不能同时在几台不同的机器上加工、一个工件不能同时在几台不同的机器上加工、一个工件不能同时在几台不同的机器上加工、一个工件不能同时在几台不同的机器上加工 2 2 2 2、工件在加工过程中采取平行移动方式，即当上道、工件在加工过程中采取平行移动方式，即当上道、工件在加工过程中采取平行移动方式，即当上道、工件在加工过程中采取平行移动方式，即当上道工序完工后，立即送下道工序加工工序完工后，立即送下道工序加工工序完工后，立即送下道工序加工工序完工
17、后，立即送下道工序加工 3 3 3 3、不允许中断。当一个工件一旦开始加工，必须一、不允许中断。当一个工件一旦开始加工，必须一、不允许中断。当一个工件一旦开始加工，必须一、不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止加入其它工件。直进行到完工，不得中途停止加入其它工件。直进行到完工，不得中途停止加入其它工件。直进行到完工，不得中途停止加入其它工件。4 4 4 4、每道工序只在一台机器上完成、每道工序只在一台机器上完成、每道工序只在一台机器上完成、每道工序只在一台机器上完成 5 5 5 5、工件数、机器数和加工时间已知，加工时间与加、工件数、机器数和加工时间已知，加工时间
18、与加、工件数、机器数和加工时间已知，加工时间与加、工件数、机器数和加工时间已知，加工时间与加工顺序无关。工顺序无关。工顺序无关。工顺序无关。6 6 6 6、每台机器同时只能加工一个工件。、每台机器同时只能加工一个工件。、每台机器同时只能加工一个工件。、每台机器同时只能加工一个工件。第21页/共119页第三节第三节 作业排序的规则作业排序的规则一、作业排序的评价标准一、作业排序的评价标准一、作业排序的评价标准一、作业排序的评价标准二、作业排序的优先规则二、作业排序的优先规则二、作业排序的优先规则二、作业排序的优先规则第22页/共119页一、作业排序的评价标准一、作业排序的评价标准作业排序作业排序
19、作业排序作业排序评价标准评价标准评价标准评价标准使用率最大化使用率最大化使完成时间最短使完成时间最短在制品库存量最小化在制品库存量最小化使顾客等待时间最少使顾客等待时间最少使顾客等待时间最少使顾客等待时间最少第23页/共119页作业流动时间作业流动时间作业流动时间作业流动时间实际加工时间；实际加工时间；等待加工时间；等待加工时间；各操作之间的运送时间各操作之间的运送时间与设备故障、不可用零件、质量等问题有关的等候时间。与设备故障、不可用零件、质量等问题有关的等候时间。作业系统作业系统作业系统作业系统工件到达工件到达工件到达工件到达工件离开工件离开工件离开工件离开1 1 1 1、使完成时间最短、
20、使完成时间最短、使完成时间最短、使完成时间最短作业平均流动时间作业平均流动时间作业平均流动时间作业平均流动时间作业流动时间是指作业从到达车间、工作区或工作作业流动时间是指作业从到达车间、工作区或工作作业流动时间是指作业从到达车间、工作区或工作作业流动时间是指作业从到达车间、工作区或工作中心开始，到离开时结束的时间长度中心开始，到离开时结束的时间长度中心开始，到离开时结束的时间长度中心开始，到离开时结束的时间长度。第24页/共119页2 2 2 2、使用率最大化。、使用率最大化。、使用率最大化。、使用率最大化。由该工作系统的有效工作时间占总流动时间的由该工作系统的有效工作时间占总流动时间的由该工
21、作系统的有效工作时间占总流动时间的由该工作系统的有效工作时间占总流动时间的百分比来表示。百分比来表示。百分比来表示。百分比来表示。作业流动时间作业流动时间作业流动时间作业流动时间作业系统作业系统作业系统作业系统工件到达工件到达工件到达工件到达工件离开工件离开工件离开工件离开等待时间等待时间等待时间等待时间加工时间加工时间加工时间加工时间第25页/共119页3 3 3 3、在制品库存量（、在制品库存量（、在制品库存量（、在制品库存量（Inventory on handInventory on handInventory on handInventory on hand）最小化。）最小化。）最小化
22、。）最小化。由该系统的平均工作数量（由该系统的平均工作数量（由该系统的平均工作数量（由该系统的平均工作数量（Average number of Average number of Average number of Average number of jobsjobsjobsjobs）来评价。）来评价。）来评价。）来评价。系统中工作数量与在制品库存量高度相关，工作数量越系统中工作数量与在制品库存量高度相关，工作数量越系统中工作数量与在制品库存量高度相关，工作数量越系统中工作数量与在制品库存量高度相关，工作数量越少，在制品存量也越少。少，在制品存量也越少。少，在制品存量也越少。少，在制品存量也越
23、少。第26页/共119页4 4 4 4、使顾客等待时间最少、使顾客等待时间最少、使顾客等待时间最少、使顾客等待时间最少 这可由作业延期时间（这可由作业延期时间（这可由作业延期时间（这可由作业延期时间（Job latenessJob latenessJob latenessJob lateness）来表示）来表示）来表示）来表示 作业延期时间是指作业的实际完成时间与预定日期之差作业延期时间是指作业的实际完成时间与预定日期之差作业延期时间是指作业的实际完成时间与预定日期之差作业延期时间是指作业的实际完成时间与预定日期之差第27页/共119页二、作业排序的优先规则二、作业排序的优先规则（Priori
24、ty Priority Priority Priority RulesRulesRulesRules）FCFS-First-Come-First-FCFS-First-Come-First-ServedServed 先到先服务先到先服务先到先服务先到先服务根据任务到达的先后次序安根据任务到达的先后次序安根据任务到达的先后次序安根据任务到达的先后次序安排加工顺序，先到先加工排加工顺序，先到先加工排加工顺序，先到先加工排加工顺序，先到先加工SPT-SPT-Shortest Processing Shortest Processing Shortest Processing Shortest Pro
25、cessing TimeTimeTimeTime最短作业时间优先最短作业时间优先最短作业时间优先最短作业时间优先按加工时间大小的次序，加按加工时间大小的次序，加按加工时间大小的次序，加按加工时间大小的次序，加工时间最小者最先加工工时间最小者最先加工工时间最小者最先加工工时间最小者最先加工.EDD-Earliest Due DateEDD-Earliest Due Date交货期最早交货期最早交货期最早交货期最早按照交货期从早到晚排序，按照交货期从早到晚排序，按照交货期从早到晚排序，按照交货期从早到晚排序，优先安排交货期最早的任务优先安排交货期最早的任务优先安排交货期最早的任务优先安排交货期最早
26、的任务.SST SST shortest Slack Timeshortest Slack Timeshortest Slack Timeshortest Slack Time最短松弛时间最短松弛时间最短松弛时间最短松弛时间在保证按期交货的前提下，在保证按期交货的前提下，在保证按期交货的前提下，在保证按期交货的前提下，当前时点距离任务开始加工当前时点距离任务开始加工当前时点距离任务开始加工当前时点距离任务开始加工时点的时间时点的时间时点的时间时点的时间紧急优先紧急优先紧急优先紧急优先优先安排紧急任务的加工优先安排紧急任务的加工优先安排紧急任务的加工优先安排紧急任务的加工随机安排（随机安排（随机
27、安排（随机安排（RandonRandon）第28页/共119页你觉得应以怎样的准则排队？你觉得应以怎样的准则排队？你觉得应以怎样的准则排队？你觉得应以怎样的准则排队？超市收银超市收银超市收银超市收银 订单交货期不同时订单交货期不同时订单交货期不同时订单交货期不同时 病人看病病人看病病人看病病人看病 第29页/共119页例：一个车间有一台加工中心，现有例：一个车间有一台加工中心，现有例：一个车间有一台加工中心，现有例：一个车间有一台加工中心，现有5 5 5 5个个个个工件需要该机器加工。相关的加工时间工件需要该机器加工。相关的加工时间工件需要该机器加工。相关的加工时间工件需要该机器加工。相关的加
28、工时间和要求完成时间（交货期）如下表所示。和要求完成时间（交货期）如下表所示。和要求完成时间（交货期）如下表所示。和要求完成时间（交货期）如下表所示。任务任务任务任务(到达次序到达次序到达次序到达次序)加工时间加工时间加工时间加工时间交货期交货期交货期交货期（从现在算起）（从现在算起）（从现在算起）（从现在算起）松弛时间松弛时间松弛时间松弛时间A A3 35 52 2B B4 48 84 4C C2 27 75 5D D5 56 61 1E E1 14 43 3第30页/共119页第31页/共119页第32页/共119页第33页/共119页第34页/共119页 SPTSPTSPTSPT准则一般
29、是作业通过时间最少和工作中心作业平均准则一般是作业通过时间最少和工作中心作业平均准则一般是作业通过时间最少和工作中心作业平均准则一般是作业通过时间最少和工作中心作业平均数最少及利用率最大的最好方法。其主要缺点是让耗时数最少及利用率最大的最好方法。其主要缺点是让耗时数最少及利用率最大的最好方法。其主要缺点是让耗时数最少及利用率最大的最好方法。其主要缺点是让耗时长的作业等待，特别当新的时间短的作业不断添加到系长的作业等待，特别当新的时间短的作业不断添加到系长的作业等待，特别当新的时间短的作业不断添加到系长的作业等待，特别当新的时间短的作业不断添加到系统中时，等待的时间可能会相当长。统中时，等待的时
30、间可能会相当长。统中时，等待的时间可能会相当长。统中时，等待的时间可能会相当长。FCFSFCFSFCFSFCFS主要局限在于加工时间过长，常会使其它作业延期。主要局限在于加工时间过长，常会使其它作业延期。主要局限在于加工时间过长，常会使其它作业延期。主要局限在于加工时间过长，常会使其它作业延期。SSTSSTSSTSST考虑到了各任务在完成过程中的松紧缓急考虑到了各任务在完成过程中的松紧缓急考虑到了各任务在完成过程中的松紧缓急考虑到了各任务在完成过程中的松紧缓急 EDDEDDEDDEDD会造成有的作业等待加工的时间很长，使在加工存会造成有的作业等待加工的时间很长，使在加工存会造成有的作业等待加工
31、的时间很长，使在加工存会造成有的作业等待加工的时间很长，使在加工存货与车间的拥挤程度增加。货与车间的拥挤程度增加。货与车间的拥挤程度增加。货与车间的拥挤程度增加。第35页/共119页第四节第四节 制造业中的排序问题制造业中的排序问题一、一、一、一、n n n n种工件在单台设备上加工的排序种工件在单台设备上加工的排序种工件在单台设备上加工的排序种工件在单台设备上加工的排序二、二、二、二、n n n n个工件在两台机器的排序问题个工件在两台机器的排序问题个工件在两台机器的排序问题个工件在两台机器的排序问题三、相同零件、不同移动方式下加工周期的计三、相同零件、不同移动方式下加工周期的计三、相同零件
32、、不同移动方式下加工周期的计三、相同零件、不同移动方式下加工周期的计算算算算第36页/共119页一、一、一、一、n n n n种工件在单台设备上加工的排序种工件在单台设备上加工的排序种工件在单台设备上加工的排序种工件在单台设备上加工的排序J J1 1J J2 2J J3 3J Jn n机器机器到达系统工到达系统工件的集合件的集合离开系统离开系统（机器）（机器）为实现任务总等待时间最短的目标，保证尽可能为实现任务总等待时间最短的目标，保证尽可能为实现任务总等待时间最短的目标，保证尽可能为实现任务总等待时间最短的目标，保证尽可能多的对象早日加工出来，加速资金周转，只需根多的对象早日加工出来，加速资
33、金周转，只需根多的对象早日加工出来，加速资金周转，只需根多的对象早日加工出来，加速资金周转，只需根据最短加工时间准则对加工对象排序即可。据最短加工时间准则对加工对象排序即可。据最短加工时间准则对加工对象排序即可。据最短加工时间准则对加工对象排序即可。第37页/共119页二、二、n n个工件在两台机器的排序问题个工件在两台机器的排序问题 n n n n个工件都必须经过机器个工件都必须经过机器个工件都必须经过机器个工件都必须经过机器1 1 1 1和机器和机器和机器和机器2 2 2 2的加工，即工艺路线是一致的。的加工，即工艺路线是一致的。的加工，即工艺路线是一致的。的加工，即工艺路线是一致的。机器
34、机器1 1到达系统工到达系统工件的集合件的集合离开系统离开系统（机器）（机器）J J1 1J J2 2J J3 3J Jn n机器机器2 2第38页/共119页1 1 两台机器排序问题的目标两台机器排序问题的目标 两台机器排序的目标是使最大完成时间（总两台机器排序的目标是使最大完成时间（总两台机器排序的目标是使最大完成时间（总两台机器排序的目标是使最大完成时间（总加工周期）加工周期）加工周期）加工周期）F F F Fmaxmaxmaxmax最短。最短。最短。最短。F F F Fmaxmaxmaxmax的含义见如下的甘的含义见如下的甘的含义见如下的甘的含义见如下的甘特图特图特图特图(Gantt
35、Chart)(Gantt Chart)(Gantt Chart)(Gantt Chart)。多台机器排序的目标一般也是使最大完成时间（总加工多台机器排序的目标一般也是使最大完成时间（总加工多台机器排序的目标一般也是使最大完成时间（总加工多台机器排序的目标一般也是使最大完成时间（总加工周期）周期）周期）周期）F F F Fmaxmaxmaxmax最短。最短。最短。最短。F Fmax max 时间时间 机器机器 A A B B在机器在机器A A上的作业时间上的作业时间总加工周期总加工周期第39页/共119页2 2 2 2 两台机器排序问题的算法两台机器排序问题的算法两台机器排序问题的算法两台机器排
36、序问题的算法 实现两台机器排序的最大完成时间实现两台机器排序的最大完成时间实现两台机器排序的最大完成时间实现两台机器排序的最大完成时间F F F Fmaxmaxmaxmax最短的目标最短的目标最短的目标最短的目标优化算法就是著名的约优化算法就是著名的约优化算法就是著名的约优化算法就是著名的约翰逊法翰逊法翰逊法翰逊法(Johnson(Johnson(Johnson(Johnson s Law)s Law)s Law)s Law)。约翰逊法解决这种问题分为约翰逊法解决这种问题分为约翰逊法解决这种问题分为约翰逊法解决这种问题分为4 4 4 4个步骤：个步骤：个步骤：个步骤：列出所有工件在两台设备上的
37、作业时间。列出所有工件在两台设备上的作业时间。列出所有工件在两台设备上的作业时间。列出所有工件在两台设备上的作业时间。找出作业时间最小者。找出作业时间最小者。找出作业时间最小者。找出作业时间最小者。如如如如果果果果该该该该最最最最小小小小值值值值是是是是在在在在设设设设备备备备1 1 1 1上上上上，将将将将对对对对应应应应的的的的工工工工件件件件排排排排在在在在前前前前面面面面，如如如如果果果果该该该该最最最最小小小小值值值值是在设备是在设备是在设备是在设备2 2 2 2上，则将对应的工件排在后面。上，则将对应的工件排在后面。上，则将对应的工件排在后面。上，则将对应的工件排在后面。排除已安排
38、好的工件，在剩余的工件中重复步骤排除已安排好的工件，在剩余的工件中重复步骤排除已安排好的工件，在剩余的工件中重复步骤排除已安排好的工件，在剩余的工件中重复步骤(2)(2)(2)(2)和和和和(3)(3)(3)(3)，直到所有，直到所有，直到所有，直到所有工件都安排完毕。工件都安排完毕。工件都安排完毕。工件都安排完毕。第40页/共119页例：某一班组有例：某一班组有例：某一班组有例：某一班组有A A A A、B B B B两台设备，要完成两台设备，要完成两台设备，要完成两台设备，要完成5 5 5 5个工件的个工件的个工件的个工件的加工任务。每个工件在设备上的加工时间如下表加工任务。每个工件在设备
39、上的加工时间如下表加工任务。每个工件在设备上的加工时间如下表加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。所示。求总加工周期最短的作业顺序。所示。求总加工周期最短的作业顺序。所示。求总加工周期最短的作业顺序。工件在两台设备上的加工时间工件在两台设备上的加工时间工件在两台设备上的加工时间工件在两台设备上的加工时间工件编号工件编号工件编号工件编号 J1 J2 J3 J4 J5 J1 J2 J3 J4 J5 J1 J2 J3 J4 J5 J1 J2 J3 J4 J5设备设备设备设备A A A A 3 6 7 1 5 3 6 7 1 5 3 6 7 1 5 3 6 7 1
40、 5设备设备设备设备B B B B 2 8 6 4 3 2 8 6 4 3 2 8 6 4 3 2 8 6 4 3第41页/共119页解解解解：由由由由约约约约翰翰翰翰逊逊逊逊法法法法可可可可知知知知，表表表表中中中中最最最最小小小小加加加加工工工工时时时时间间间间值值值值是是是是1 1 1 1个个个个时时时时间间间间单单单单位位位位，它它它它又又又又是是是是出出出出现现现现在在在在设设设设备备备备A A A A上上上上，根根根根据据据据约约约约翰翰翰翰逊逊逊逊法法法法的的的的规规规规则则则则，应应应应将将将将对对对对应应应应的的的的工工工工件件件件4 4 4 4排排排排在在在在第第第第一一一
41、一位位位位，即即即即得：得：得：得：J4J4-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*去去去去掉掉掉掉J4J4J4J4，在在在在剩剩剩剩余余余余的的的的工工工工件件件件中中中中再再再再找找找找最最最最小小小小值值值值，不不不不难难难难看看看看出出出出，最最最最小小小小值值值值是是是是2 2 2 2个个个个时时时时间间间间单单单单位位位位，它它它它是是是是出出出出现现现现在在在在设设设设备备备备B B B B上上上上的的的的，所所所所以以以以应应应应将将将将对对对对应应应应的的的的工工工工件件件件J1J1J1J1排排排排在在在在最最最最后后后后一一一一位位位位，即：即：即：
42、即：J4J4-*-*-*-*-*-*-*-*-*-*-*-*-J1J1 再再再再去去去去掉掉掉掉J1J1J1J1，在在在在剩剩剩剩余余余余的的的的J2J2J2J2、J3J3J3J3、J5J5J5J5中中中中重重重重复复复复上上上上述述述述步骤，求解过程为：步骤，求解过程为：步骤，求解过程为：步骤，求解过程为：J4J4-*-*-*-*-*-*-*-*-J5J5-J1J1 J4J4-J2J2-*-*-*-*-J5J5-J1J1 J4J4-J2J2-J3J3-J5J5-J1J1 当同时出现多个最小值时，可从中任选一个。当同时出现多个最小值时，可从中任选一个。当同时出现多个最小值时，可从中任选一个。当
43、同时出现多个最小值时，可从中任选一个。最后得最后得最后得最后得 J4-J2-J3-J5-J1 J4-J2-J3-J5-J1 J4-J2-J3-J5-J1 J4-J2-J3-J5-J1第42页/共119页30AB0316922175323302717 J1-J2-J3-J4-J5J1-J2-J3-J4-J5J1-J2-J3-J4-J5J1-J2-J3-J4-J5 A 3 6 7 1 5A 3 6 7 1 5A 3 6 7 1 5A 3 6 7 1 5B 2 8 6 4 3B 2 8 6 4 3B 2 8 6 4 3B 2 8 6 4 3第43页/共119页26AB J4-J2-J3-J5-J1
44、J4-J2-J3-J5-J1 A 1 6 7 5 3 A 1 6 7 5 3 B 4 8 6 3 2 B 4 8 6 3 211751419221572124 26第44页/共119页(a)J1-J2-J3-J4-J526AB(b)J4-J2-J3-J5-J1可以看出，初始作业顺序的总加工周期是可以看出，初始作业顺序的总加工周期是可以看出，初始作业顺序的总加工周期是可以看出，初始作业顺序的总加工周期是30303030，用约，用约，用约，用约翰逊法排出的作业顺序总加工周期是翰逊法排出的作业顺序总加工周期是翰逊法排出的作业顺序总加工周期是翰逊法排出的作业顺序总加工周期是26262626，显然后者，
45、显然后者，显然后者，显然后者的结果优于前者。的结果优于前者。的结果优于前者。的结果优于前者。30AB0第45页/共119页习题假设有假设有A A，B B，C C，D D，E E五种零件，每种零件均五种零件，每种零件均需先在甲设备上加工，再在乙设备上加工。甲、需先在甲设备上加工，再在乙设备上加工。甲、乙设备各一台，零件加工时间如下表所示。问乙设备各一台，零件加工时间如下表所示。问如何加工使总加工时间最短？最短时间是多少如何加工使总加工时间最短？最短时间是多少？整个加工过程中甲乙两台设备的空闲时间是？整个加工过程中甲乙两台设备的空闲时间是多少？多少？ABCDE甲甲681237乙乙119534第46
46、页/共119页 加工一批相同工件时时，制品在生产过程中的移动方式对生产周期有直接的影响。制品在生产过程中的移加工一批相同工件时时，制品在生产过程中的移动方式对生产周期有直接的影响。制品在生产过程中的移动方式有三种：动方式有三种：顺序移动方式顺序移动方式平行移动方式平行移动方式平行顺序移动方式平行顺序移动方式三、相同零件、不同移动方式下加工周期的计算三、相同零件、不同移动方式下加工周期的计算第47页/共119页1、顺序移动、顺序移动一一批批零零件件在在上上道道工工序序全全部部加加工工完完毕毕后后才才整整批批转移到下道工序继续加工。转移到下道工序继续加工。t1t4t2t3时间工工序序第第第第1 1
47、 1 1道工序道工序道工序道工序第第第第2 2 2 2道工序道工序道工序道工序第第第第3 3 3 3道工序道工序道工序道工序第第第第4 4 4 4道工序道工序道工序道工序第48页/共119页优点：组织管理容易，设备集中使用，设备没有间断性优点：组织管理容易，设备集中使用，设备没有间断性停歇现象，可以减少设备调整停歇现象，可以减少设备调整缺点：加工对象等待时间长，延长生产周期，减缓资金缺点：加工对象等待时间长，延长生产周期，减缓资金周转周转适用对象：批量不大，工序时间较短和加工体积小的情适用对象：批量不大，工序时间较短和加工体积小的情况况第49页/共119页t1t4t2t3时间工序按顺序移动方式
48、加工完这一批按顺序移动方式加工完这一批零件需要多长时间？零件需要多长时间？第50页/共119页一批零件的加工周期为：一批零件的加工周期为：第51页/共119页t1t4t2t3例：已知n=4，t1=10分，t25分钟，t315分钟，t410分钟，求T顺:解：T顺4(10+5+15+10)=160（分钟）时间工序4060120160第52页/共119页2 2、平行移动方式、平行移动方式 每每个个零零件件在在前前道道工工序序加加工工完完毕毕后后，立立即即转转移移到下道工序继续加工，形成前后交叉作业。到下道工序继续加工，形成前后交叉作业。t1t3时间工序t4t2第53页/共119页优点：加工对象没有等
49、待，生产周期短优点：加工对象没有等待，生产周期短缺点：运输工作量大而频繁，且在工序时间不均衡时造缺点：运输工作量大而频繁，且在工序时间不均衡时造成许多工作地人机负荷不足，设备会出现间断性停歇成许多工作地人机负荷不足，设备会出现间断性停歇适用对象：工序单件加工时间比较协调（如接近或成整适用对象：工序单件加工时间比较协调（如接近或成整数倍），加工对象体积较大数倍），加工对象体积较大第54页/共119页t1t3时间工序t4t2按平行移动方式，加工完这一批零按平行移动方式，加工完这一批零件需要多长时间？件需要多长时间？第55页/共119页一批零件的加工周期为：一批零件的加工周期为：第56页/共119页
50、t1t3时间工序t4t2T平（1051510）（4-1)15 =85(分钟）307585例：已知n=4，t1=10分，t25分钟，t315分钟，t410分钟，求T平:第57页/共119页3 3、平顺移动方式、平顺移动方式当当titi+1titi+1时，零件按平行移动方式转移；时，零件按平行移动方式转移；当当tititi+1ti+1时，只有当前道工序上完工的零件数时，只有当前道工序上完工的零件数量足以保证后道工序连续加工时，才开始将完工量足以保证后道工序连续加工时，才开始将完工的零件转入后道工序。这样既可以避免后道工序的零件转入后道工序。这样既可以避免后道工序发生工作时断时续的现象，又可以集中利