车间作业计划与控制

1、讲授：赵林讲授：赵林时间：时间：2012.52012.5 在生产计划与控制系统中，生产作业在生产计划与控制系统中，生产作业计划是将物料需求的结果转换成可以执行计划是将物料需求的结果转换成可以执行的作业活动。的作业活动。 生产计划是以订单的形式下达到生产生产计划是以订单的形式下达到生产车间。在执行订单的过程中，还必须对执车间。在执行订单的过程中，还必须对执行订单的情况进行跟踪控制，这就是生产行订单的情况进行跟踪控制，这就是生产控制的主要任务。控制的主要任务。l8.1 基本概念基本概念l8.2 车间作业排序车间作业排序l8.3 车间调度车间调度l8.4 车间控制车间控制l生产作业计划内容生产作业计

2、划内容生产作业计划的主要任务是将主生产计划或生产作业计划的主要任务是将主生产计划或MRP中的零部件投入出产计划细化，他是中的零部件投入出产计划细化，他是MRP的具体执行计划。生产作业计划具体、详细地规的具体执行计划。生产作业计划具体、详细地规定了各车间、工段、班组以至每个工作中心在较定了各车间、工段、班组以至每个工作中心在较短的时间内（月、旬、周、日、轮班、小时）的短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。生产运作任务。l生产作业计划工作由生产作业计划工作由作业计划编制作业计划编制与与作业作业计划控制计划控制两部分组成。两部分组成。车间作业计划是安排零部件（作业、活动）的出车间作

3、业计划是安排零部件（作业、活动）的出产数量、设备，以及人工使用、投入时间及产出产数量、设备，以及人工使用、投入时间及产出时间。时间。生产控制是以生产计划和作业计划为依据，检查、生产控制是以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，落实计划执行情况，发现偏差即采取纠正措施，保证实现各项计划目标。保证实现各项计划目标。l 车间作业的功能：车间作业的功能：决定订单顺序，即建立订单优先级，排序；决定订单顺序，即建立订单优先级，排序；对应经排序的作业安排生产，调度；对应经排序的作业安排生产，调度；输入输入/输出的车间作业控制。输出的车间作业控制。l 车间的控制功能：车间的

4、控制功能：作业进行过程中，检查其状态和控制作业的进度；作业进行过程中，检查其状态和控制作业的进度；加速迟缓的和关键的作业。加速迟缓的和关键的作业。l 目标：目标：满足交货期的要求；满足交货期的要求；使在制品库存最小；使在制品库存最小；使平均流程时间最短；使平均流程时间最短；提供准确的作业状态信息；提供准确的作业状态信息；提高机器提高机器/人工的利用率；人工的利用率；减少调整准备时间；减少调整准备时间；使生产和人工成本最低。使生产和人工成本最低。l基本架构基本架构物料需求计划物料需求计划作作 业业 排排 序序作作 业业 调调 度度输入输入/输出控制输出控制细能力计划细能力计划派派 工工生产活动及

5、反馈生产活动及反馈l 排序：排序：就是要将不同的工作任务安排一个执行的顺序，使就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力分配给不同工作任务，使预定目标最将有限的人力、物力分配给不同工作任务，使预定目标最优化的问题。优化的问题。l 调度：调度：是作业计划编制以后是好似生产控制的一切行动。是作业计划编制以后是好似生产控制的一切行动。l 派工：派工：在作业计划制定以后，按照作业计划的要求，将具在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体

6、的机床和体生产任务通过工票或施工单的形式下达到具体的机床和工人。工人。l信息源：信息源：车间作业计划与控制主要来自于车间作业计划与控制主要来自于车间计划文件车间计划文件和和车间控制文件车间控制文件。计划文件包括：计划文件包括：l项目主文件，用来记录全部零件的信息；项目主文件，用来记录全部零件的信息；l工艺路线文件，用来记录零件的加工顺序；工艺路线文件，用来记录零件的加工顺序；l工作中心文件，用来记录工作中心的数据。工作中心文件，用来记录工作中心的数据。l信息源：信息源：车间作业计划与控制主要来自于车间作业计划与控制主要来自于车间计划文件车间计划文件和和车间控制文件车间控制文件。控制文件包括：控

7、制文件包括：l车间任务主文件，为每个生产中的任务提供一条记录；车间任务主文件，为每个生产中的任务提供一条记录；l车间任务详细文件，记录每个车间任务所需的工序；车间任务详细文件，记录每个车间任务所需的工序；l从工作人员得到信息。从工作人员得到信息。l基本术语：基本术语：加工单：加工单：l也称车间订单，面向加工作业说明物料需求计划文件。也称车间订单，面向加工作业说明物料需求计划文件。l加工订单反映：加工工序，工具、材料、能力和提前加工订单反映：加工工序，工具、材料、能力和提前期等加工工艺信息。期等加工工艺信息。派工单：派工单：l也叫调度单，是一种面向工作中心说明加工优先级的也叫调度单，是一种面向工

8、作中心说明加工优先级的文件。文件。l说明工作在一个周期内要完成哪些任务，包括：哪些说明工作在一个周期内要完成哪些任务，包括：哪些工作完成，哪些工作正在加工，物料到达时间，加工工作完成，哪些工作正在加工，物料到达时间，加工开始时间，加工完成时间，加工天数等等。开始时间，加工完成时间，加工天数等等。l基本术语：基本术语：工作中心的特征和重要性。工作中心的特征和重要性。有限负荷方法和无限负荷方法。有限负荷方法和无限负荷方法。前向排序和后向排序：前向排序和后向排序：l前向排序：是指系统接受一个订单后，对订单所需作业前向排序：是指系统接受一个订单后，对订单所需作业按照从前往后的顺序进行排序。前向排序可以

9、告诉我们按照从前往后的顺序进行排序。前向排序可以告诉我们订单能够完成的最早时间。订单能够完成的最早时间。l后向排序：从未来的某个日前（交货期）开始，从后向后向排序：从未来的某个日前（交货期）开始，从后向前安排所需作业工作。后向排序告诉我们，为了按规定前安排所需作业工作。后向排序告诉我们，为了按规定日期完成一个作业所必须的最晚开工时间。日期完成一个作业所必须的最晚开工时间。l 排序：在某机器上或工作中心决定哪个工作先开排序：在某机器上或工作中心决定哪个工作先开始，哪个工作后开始的过程。始，哪个工作后开始的过程。l 目标：目标：满足顾客或下一道作业的交货期；满足顾客或下一道作业的交货期；极小化流程

10、时间；极小化流程时间；极小化准备时间或成本；极小化准备时间或成本；极小化的在制品库存；极小化的在制品库存；极大化设备或劳动利用。极大化设备或劳动利用。l 编制作业计划与排序的关系编制作业计划与排序的关系 一般来说，编制作业计划一般来说，编制作业计划（Scheduling）与与排序排序（Sequencing）不是同义语不是同义语 。排序只是确定。排序只是确定工件在机器上的加工顺序，可以通过一组工件的工件在机器上的加工顺序，可以通过一组工件的代号的一种排列来表示该组工件的加工顺序。而代号的一种排列来表示该组工件的加工顺序。而编制作业计划，则不仅包括确定工件的加工顺序，编制作业计划，则不仅包括确定工

11、件的加工顺序，而且还包括确定机器加工每个工件的开始时间和而且还包括确定机器加工每个工件的开始时间和完成时间。完成时间。 l 排序问题的分类和表示法排序问题的分类和表示法按机器种类和数量分类：按机器种类和数量分类：l单台机器排序问题和多台机器排序问题。单台机器排序问题和多台机器排序问题。按零件加工路线特征分类：按零件加工路线特征分类：l单件作业排序问题：零件加工路线不同；单件作业排序问题：零件加工路线不同；l流水作业排序问题：零件加工路线相同。流水作业排序问题：零件加工路线相同。按零件到达车间的情况分类：按零件到达车间的情况分类：l静态排序：进行排序时，所有零件已经抵达，可以一次性静态排序：进行

12、排序时，所有零件已经抵达，可以一次性对它们排序；对它们排序；l动态排序：零件陆续抵达，要随时安排它们的加工顺序。动态排序：零件陆续抵达，要随时安排它们的加工顺序。l排序问题的分类和表示法排序问题的分类和表示法按目标函数的性质不同分类：按目标函数的性质不同分类：l单目标排序问题和多目标排序问题。单目标排序问题和多目标排序问题。按参数的性质分类：按参数的性质分类：l确定型排序问题：指加工时间和其他相关参数是已知确定型排序问题：指加工时间和其他相关参数是已知的确定量；的确定量；l随机型排序问题：加工时间和有关参数为随机变量。随机型排序问题：加工时间和有关参数为随机变量。Ji 零件零件i， i =1,

13、 2, 3, . , n。Mj机器机器j， j =1, 2, 3, . , n。pij Ji在在Mj上加工时间，上加工时间，Ji的总加工时间的总加工时间Pi= pij。ri Ji的到达时间，指的到达时间，指Ji从外部进入车间，可以开始加工的最早时间。从外部进入车间，可以开始加工的最早时间。wij Ji在进行第在进行第j道前的等待时间，道前的等待时间，Ji的总等待时间的总等待时间Wi= wij。di Ji的完工期限。的完工期限。Ci Ji的完工时间，的完工时间， Ci = ri + （ wij + pij）= ri + Wi + Pi 。Cmax最长完工时间，最长完工时间， Cmax =maxC

14、i 。Fi Ji的流程时间，即零件在车间的实际停留时间，的流程时间，即零件在车间的实际停留时间， Fi = Ci- ri =Wi + Pi 。Fmax 最长流程时间，最长流程时间，Fmax =maxFi 。Li Ji的延迟时间，的延迟时间，Li = Ci di。当。当Li 0，说明实际完工时间超过完工期限；，说明实际完工时间超过完工期限； 当当Li 0，说明提前完工；当，说明提前完工；当Li =0，说明按期完工。，说明按期完工。Lmax 最长延迟时间，最长延迟时间，Lmax =maxLi 。l Conway的表示方法：的表示方法： 其中：其中：n零件数；零件数； m机器数；机器数； A车间类型

15、，若标以车间类型，若标以“F”，代表流水作业排序问题；若，代表流水作业排序问题；若标以标以“P”，代表流水作业排列排序问题；若标以，代表流水作业排列排序问题；若标以“G”，代表一般，代表一般单件作业排序问题。单件作业排序问题。 B目标函数。目标函数。例如：例如：n/3/P/Cmax表示表示n个零件经过个零件经过3台机器加工的流水作业排列排序台机器加工的流水作业排列排序问题，目标函数是使最长完工时间最短。问题，目标函数是使最长完工时间最短。l8.2.4 n个作业单台工作中心的排序个作业单台工作中心的排序n/1/B，即，即 n/1问题。问题。J1J2J3JnM1l排序目标：排序目标：平均流程时间最

16、短。平均流程时间最短。 假设以排定顺序，则任何一个作业，假设其假设以排定顺序，则任何一个作业，假设其排在第排在第k位，其流程时间：位，其流程时间：相应的目标函数为相应的目标函数为 ， 。npinnpnFFniinkkiinkk1111) 1(kiikpF1FminFn/1/l排序目标：排序目标：最低延迟时间、总延迟时间（或平均延迟时间）最低延迟时间、总延迟时间（或平均延迟时间）最小。最小。l最大延迟时间最小，目标函数为：最大延迟时间最小，目标函数为： ；l总延迟时间最小，目标函数为：总延迟时间最小，目标函数为： ；maxmin LniiL1minl排序规则：排序规则：1.先到先服务（先到先服务

17、（First Come First Served, FCFS）根据订单达到加工中心的先后顺序执行加工作业，先到先加工。根据订单达到加工中心的先后顺序执行加工作业，先到先加工。2.最短作业时间（最短作业时间（Shortest Operation Time, SOT）也称最短加工时间，先安排加工时间最短的，其次安排第二短的，也称最短加工时间，先安排加工时间最短的，其次安排第二短的，依次类推。依次类推。3.剩余松弛时间（剩余松弛时间（Slack Time Remained, STR）l剩余松弛时间是指交货期前所剩余的时间减去剩余的加工剩余松弛时间是指交货期前所剩余的时间减去剩余的加工时间所得的差值，

18、剩余松弛时间越小，越有可能延期，时间所得的差值，剩余松弛时间越小，越有可能延期，故故STR最短的任务应最先加工最短的任务应最先加工。4.每个作业的剩余松弛时间（每个作业的剩余松弛时间（STR/OR）l 排序规则：排序规则：5.最早到期日（最早到期日（Earliest Due Date, EDD）根据订单交货期的先后安排顺序，交货期最早应最先加工。根据订单交货期的先后安排顺序，交货期最早应最先加工。6.紧迫系数（紧迫系数（Critical Ratio, CR）CR=（到期日（到期日-现在日期）现在日期）/正常制造所剩余的提前期正常制造所剩余的提前期CR的值得情况：的值得情况：1、 CR0，说明已

19、经延期；，说明已经延期；2、 CR1，说明剩余时间不够；，说明剩余时间不够；3、 CR = 1，说明剩余时间刚好够用；，说明剩余时间刚好够用；4、 CR1，说明剩余时间有富余。，说明剩余时间有富余。l 排序规则：排序规则：7.最少作业数（最少作业数（Fewest Operations, FO）l 根据剩余的作业数来安排订单顺序，逻辑：较少的根据剩余的作业数来安排订单顺序，逻辑：较少的作业意味着有较少的等待时间。作业意味着有较少的等待时间。8.后到先服务（后到先服务（ Last Come First Served, LCFS ）l 后来的订单放在上面，操作人员通常先处理上面的后来的订单放在上面，

20、操作人员通常先处理上面的订单。订单。l 例例8.1 现有现有5个订单需要在一台机器上加工，个订单需要在一台机器上加工，5个订单到达个订单到达顺序为顺序为A、B、C、D、E，相关数据如表所示，进行作业，相关数据如表所示，进行作业排序。排序。订单订单交货期交货期加工时间（天）加工时间（天）剩余的制造提前期（天）剩余的制造提前期（天）作业数作业数A7155B52.563C64.564D8572E92111lFCFS订单按照到达先后顺序安排加工顺序，因此，加订单按照到达先后顺序安排加工顺序，因此，加工顺序为工顺序为ABCDE。订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间

21、（天）流程时间（天）延迟时间延迟时间（天）（天）A7151-6B52.531+2.5=3.5-1.5C64.543.5+4.5=82D8528+5=135E92113+2=156l FCFS订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间（天）流程时间（天）延迟时间（天）延迟时间（天）A7151-6B52.531+2.5=3.5-1.5C64.543.5+4.5=82D8528+5=135E92113+2=156)( 1 . 85/5 .40, )(5 .40天天FF)(6max),(6 . 25/13, )(13天天天LLLl最短作业时间，最短作业时间，SOT订单

22、加工时间短着优先安排；订单加工时间短着优先安排；加工顺序为加工顺序为AEBCD。订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间（天）流程时间（天）延迟时间延迟时间（天）（天）A7151-6E9211+2=3-6B52.533+2.5=5.50.5C64.545.5+4.5=104D85210+5=157l 最短作业时间，最短作业时间，SOT)(9 . 65/5 .34, )(5 .34天天FF)(7max),(3 . 25/5 .11, )(5 .11天天天LLL订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间（天）流程时间（天）延迟时

23、间（天）延迟时间（天）A7151-6E9211+2=3-6B52.533+2.5=5.50.5C64.545.5+4.5=104D85210+5=157l最早到期日，最早到期日，EDD交货期最早的优先安排；交货期最早的优先安排；加工顺序为加工顺序为BCADE。订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间（天）流程时间（天）延迟时间延迟时间（天）（天）B52.532.5-2.5C64.542.5+4.5=71A7157+1=81D8528+5=135E92113+2=156l 最早到期日，最早到期日，EDD)( 1 . 95/5 .45, )(5 .45天天FF)

24、(6max),(6 . 25/13, )(13天天天LLL订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间（天）流程时间（天）延迟时间（天）延迟时间（天）B52.532.5-2.5C64.542.5+4.5=71A7157+1=81D8528+5=135E92113+2=156l 剩余松弛时间，剩余松弛时间，STR剩余松弛时间短者优先安排；剩余松弛时间短者优先安排；剩余松弛时间剩余松弛时间=交货期交货期-加工时间加工时间加工顺序为加工顺序为CBDAE。订单订单交货期交货期加工时间（天）加工时间（天）剩余松弛时间（天）剩余松弛时间（天）A716B52.52.5C64.

25、51.5D853E927l 剩余松弛时间，剩余松弛时间，STR)(3 .105/5 .51, )(5 .51天天FF)(6max),(6 . 35/18, )(18天天天LLL订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）松弛时间松弛时间（天）（天）流程时间（天）流程时间（天）延迟时间（天）延迟时间（天）C64.51.54.5-1.5B52.52.54.5+2.5=72D8537+5=124A71612+1=136E92713+2=156l 每个作业剩余松弛时间，每个作业剩余松弛时间，STR/OR每个作业短着优先安排；每个作业短着优先安排；每个作业剩余松弛时间每个作业剩余松弛时间=剩

26、余松弛时间剩余松弛时间/作业数作业数加工顺序为加工顺序为CBADE。订单订单交货期交货期加工时间加工时间（天）（天）剩余松弛时剩余松弛时间（天）间（天）作业数作业数每个作业剩余松每个作业剩余松弛时间（天）弛时间（天）A71651.2B52.52.530.83C64.51.540.375D85321.5E92717l 每个作业剩余松弛时间，每个作业剩余松弛时间，STR/OR订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）每个作业剩余松每个作业剩余松弛时间（天）弛时间（天）流程时间（天）流程时间（天）延迟时间（天）延迟时间（天）C64.50.3754.5-1.5B52.50.834.5+2

27、.5=72A711.27+1=81D851.58+5=135E92713+2=156)(5 . 95/5 .47, )(5 .47天天FF)(6max),(8 . 25/14, )(14天天天LLLl 紧迫系数，紧迫系数，CRCR=（到期日（到期日-现在日期）现在日期）/正常制造所剩余的提前期正常制造所剩余的提前期；加工顺序为加工顺序为EBCDA。订单订单顺序顺序交货期交货期 加工时间（天）加工时间（天）剩余的制造提前剩余的制造提前期（天）期（天）紧迫系数紧迫系数A7151.4B52.560.83C64.561D8571.14E92110.82l 紧迫系数，紧迫系数，CR订单订单顺序顺序交货期

28、交货期加工时间加工时间（天）（天）紧迫系数紧迫系数流程时间（天）流程时间（天）延迟时间（天）延迟时间（天）E920.822-7B52.50.832+2.5=4.5-0.5C64.514.5+4.5=93D851.149+5=146A711.414+1=158)(9 . 85/5 .44, )(5 .44天天FF)(8max),(4 . 35/17, )(17天天天LLLl最少作业数，最少作业数，FO作业数最少着优先安排；作业数最少着优先安排；加工顺序为加工顺序为EDBCA。订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间（天）流程时间（天）延迟时间延迟时间（天）（天

29、）E9212-7D8522+5=7-1B52.537+2.5=9.54.5C64.549.5+4.5=148A71514+1=158l 最少作业数，最少作业数，FO)(5 . 95/5 .47, )(5 .47天天FF)(8max),(3 . 21 . 4/5 .20, )(5 .20天天天LLL订单订单顺序顺序交货期交货期加工时间加工时间（天）（天）作业数作业数流程时间（天）流程时间（天）延迟时间（天）延迟时间（天）E9212-7D8522+5=7-1B52.537+2.5=9.54.5C64.549.5+4.5=148A71514+1=158排序规则排序规则订单顺序订单顺序平均流程时间（天

30、）平均流程时间（天）平均延迟时间（天）平均延迟时间（天）FCFSABCDE8.12.4SOTAEBCD6.92.3EDDBCADE9.12.6STRCBDAE10.33.6STR/ORCBADE9.52.8CREBCDA8.93.4FOEDBCA9.54.1 定理定理1 对于单机进度计划问题，如从加工时间最短的工件对于单机进度计划问题，如从加工时间最短的工件开始顺序排序开始顺序排序最短加工时间（最短加工时间（SOT）规则）规则，则平均流程，则平均流程时间最小。时间最小。 定理定理2 对于单机进度计划问题，如从交货期最短的工件开对于单机进度计划问题，如从交货期最短的工件开始顺序进行排序始顺序进行

31、排序最早交货期（最早交货期（EDD）规则）规则，则最大交货，则最大交货期延迟期延迟Lmax或最大交货期延误或最大交货期延误Tmax最小。最小。n/2/A/B，即，即 n/2问题。问题。J1J2J3JnM1M2l n个作业在两台机器上排序的目标是使最大完成个作业在两台机器上排序的目标是使最大完成时间（总加工周期）最短。时间（总加工周期）最短。l 对于对于n/2问题，问题，Johnson算法。算法。MT0M1的作业时间的作业时间M2的作业时间的作业时间总加工周期总加工周期FmaxlJohnson法则法则： 如果以如果以pi1表示零件表示零件Ji机器机器M1上加工时间，以上加工时间，以pi2表示上表

32、示上M2加工时间，每个零件都按照加工时间，每个零件都按照M1 M2的路线加工，的路线加工， 如果如果min(pi1, pj2) min(pj1, pi2), 则零件则零件Ji应该排在工件应该排在工件Jj之前。如果中间是之前。如果中间是等号，则可以随意安排。等号，则可以随意安排。l Johnson算法：算法： （1）从加工时间矩阵中找出最短的加工时间。）从加工时间矩阵中找出最短的加工时间。 （2）若最短的加工时间出现在）若最短的加工时间出现在M1上，则对应的工件尽可上，则对应的工件尽可能往前排；若最短加工时间出现在能往前排；若最短加工时间出现在M2上，则对应工件尽上，则对应工件尽可能往后排。然后

33、，从加工时间矩阵中划去已排序工件的可能往后排。然后，从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。加工时间。若最短加工时间有多个，则任挑一个。 （3）若所有工件都已排序，停止。否则，转步骤（）若所有工件都已排序，停止。否则，转步骤（1）。）。l 例例8.2 现有现有5个订单，每个订单在两台工作中心上个订单，每个订单在两台工作中心上的作业时间如表所示，求的作业时间如表所示，求5/2/F/Fmax问题的最优解问题的最优解。i12345pi141525pi232436i12345pi141525pi232436步骤步骤pij最小值最小值排序结果排序结果1p21=1 ，

34、， ， ， ，2p41=2 ， ， ， ， ，3p12=3 ， ， ， ， ，4p32=4 ， ， ， ， ，5p51=5 ， ， ， ， ，22422244411133522445533115101520TMM1M20ln/2问题，需注意以下问题：问题，需注意以下问题：（1）M1为连续安排作业，无须等待时间，故闲置时间为零；为连续安排作业，无须等待时间，故闲置时间为零；（2）M1的排序结果和的排序结果和M2的排序结果相同；的排序结果相同；（3）M2的闲置时间是造成总时间增加的因素，应尽量缩短的闲置时间是造成总时间增加的因素，应尽量缩短这种闲置浪费时间；这种闲置浪费时间；（4）最小所有作业完成

35、总时间有时不一定是唯一的一中排）最小所有作业完成总时间有时不一定是唯一的一中排序结果。序结果。l 如果需要如果需要n个作业在个作业在m台工作中心上加工，就是台工作中心上加工，就是“n/m”排序问题。排序问题。l 当当m大于大于2时，就很难找到最优解，计算也比较复时，就很难找到最优解，计算也比较复杂，计算量也大，往往要借助计算机计算。杂，计算量也大，往往要借助计算机计算。l “n/m/F/Fmax”排序问题启发式算法：排序问题启发式算法： Palmer算算法、法、 CDS算法。算法。l “n/m/P/Fmax”排序问题可用分支定界法得到最优排序问题可用分支定界法得到最优解。解。l Palmer算

36、法算法Palmer于于1965年对流水作业排序问题提出了按年对流水作业排序问题提出了按斜度指标排列工件的启发式算法，该算法先定义斜度指标排列工件的启发式算法，该算法先定义工件的斜度指标，然后将各工件按其斜度指标不工件的斜度指标，然后将各工件按其斜度指标不增进行排序。增进行排序。mkpmkmkiki,.,2 , 1,)21(1l 例例8.3 有一个有一个4/3/F/Fmax问题，其加工时间如表所问题，其加工时间如表所示，试用示，试用Palmer法求解。法求解。i1234pi11263pi28429pi34582解：计算解：计算 ， 按照按照不增进行排序，得到最优顺序为不增进行排序，得到最优顺序为

37、：（：（1,2,3,4）或）或（2,1,3,4），），Fmax=28。i1234pi11263pi28429pi345823 , 2 , 1,)2(31kpkkiki31iiipp 34113111pp35223212pp28633313pp12343414ppl CDS算法算法Campbell等人于等人于1970年对流水作业排序问题提年对流水作业排序问题提出了一个基于出了一个基于Johnson算法的启发式算法，该算算法的启发式算法，该算法先产生法先产生m-1个排列，然后从中选优。个排列，然后从中选优。依次令依次令j=1,2,3,.,m-1,，可以得到，可以得到m-1组组j和和j，将，将每一组

38、值看成是分别在两个机器上的加工时间，每一组值看成是分别在两个机器上的加工时间，根据根据Johnson算法可以求得一个排序，共可得到算法可以求得一个排序，共可得到m-1个排序，从中选优。个排序，从中选优。1,.,2 , 1;,.,2 , 1,11mjnippmjmkikjjkikj和l 例例8.4 有一个有一个4/3/F/Fmax问题，其加工时间如表所问题，其加工时间如表所示，试用示，试用CDS法求解。法求解。i1234pi11263pi28429pi34582解：首先求解：首先求 j和和j ，结果如表下表所示，结果如表下表所示 i1234pi11263pi28429pi34582i1234j=

39、11pi112631pi34582j=22pi1+ pi2968122pi3+ pi212910111,.,2 , 1;,.,2 , 1,11mjnippmjmkikjjkikj 当当j=1时，根据时，根据Johnson算法得到加工顺序算法得到加工顺序（1,2,3,4）；当）；当j=2时，得到加工顺序（时，得到加工顺序（2,3,1,4）,这时这时Fmax为为29；所以，取顺序（；所以，取顺序（1,2,3,4）。）。i1234j=11pi112631pi34582j=22pi1+ pi2968122pi3+ pi21291011l加工周期的计算加工周期的计算“n/m”排序问题的加工周期（最长流程

40、时间），是指排序问题的加工周期（最长流程时间），是指从第一个零件在第一台机器上开始加工算起，直到最从第一个零件在第一台机器上开始加工算起，直到最后一个零件在最后一台机器上完成加工时所经过的时后一个零件在最后一台机器上完成加工时所经过的时间。间。假设零件到达时间假设零件到达时间ri=0，所以，所以Fmax等于排在末位加工的等于排在末位加工的零件在车间的停留时间，也等于一批零件的最长完工零件在车间的停留时间，也等于一批零件的最长完工时间时间Cmax。l加工周期的计算加工周期的计算设设n个零件的加工顺序为个零件的加工顺序为S=（S1, S2, ., Sn）,其中其中Si为排为排在第在第i位的零件代号

41、。以位的零件代号。以Cksi表示零件表示零件Si在机器在机器Mk上的完上的完工时间，工时间，PSik表示零件表示零件Si在机器在机器Mk上的加工时间，上的加工时间，k=1, 2, ., m；i=1, 2, ., n；则；则Cksi可以按以下公式计算：可以按以下公式计算：ksiisksiksiksiissipCCCpCC,)1(,),1(,1 ,)1(, 1, 1,maxl 例例8.5 有一个有一个4/3/F/Fmax问题，其加工时间如表所问题，其加工时间如表所示，示，得到最优顺序为得到最优顺序为：（：（1,2,3,4） ，求加工周期。，求加工周期。i1234pi11263pi28429pi34

42、582l 解：按解：按（1,2,3,4）顺序列出加工时间矩阵，按公式递推）顺序列出加工时间矩阵，按公式递推计算，将每个零件的完工时间列在加工时间的右上角。计算，将每个零件的完工时间列在加工时间的右上角。 i1234pi1112369312pi289413215924pi3413518826228l指派问题：也称为指派问题：也称为“任务分配任务分配”，将，将n个零个零件安排在件安排在n各机器上的加工的问题。各机器上的加工的问题。l问题的关键：问题的关键：n个零件如何在个零件如何在n个机器上分个机器上分配，而不是加工的先后顺序。配，而不是加工的先后顺序。l求解的目标：使任务和资源得到最佳匹配。求解

43、的目标：使任务和资源得到最佳匹配。具体就是极小化或极大化效率指标。具体就是极小化或极大化效率指标。 n！l 指派法适用问题特征：指派法适用问题特征：1. 有有n个个“事项事项”要分配到要分配到n个个“目的地目的地”；2. 每个事项必须被指派且唯一指派到某个目的地；每个事项必须被指派且唯一指派到某个目的地；3. 只有一个目标：最小成本、最大利润或最少完只有一个目标：最小成本、最大利润或最少完成时间等。成时间等。l例例8.6 有有4个零件可以分配给个零件可以分配给4个机器加工，其个机器加工，其所需加工时间如表所示，如何分配使总加工时所需加工时间如表所示，如何分配使总加工时间最少。间最少。M1M2M

44、3M4J19735J2781211J34687J46111310l指派法的求解步骤指派法的求解步骤：（匈牙利算法）：（匈牙利算法）1.从加工时间（费用）矩阵每一行所有元素减去该行最小的元素，使每从加工时间（费用）矩阵每一行所有元素减去该行最小的元素，使每一行至少出现一个零元素；一行至少出现一个零元素；2.从实施第从实施第1步得到的矩阵中的每一列所有元素减去该列最小元素，使每步得到的矩阵中的每一列所有元素减去该列最小元素，使每一列至少出现一个零元素；一列至少出现一个零元素；3.从实施第从实施第2步得到的矩阵中，划出能覆盖尽可能多的零元素的直线，如步得到的矩阵中，划出能覆盖尽可能多的零元素的直线，

45、如果线条数等于矩阵行数，则已找到最优矩阵，转第果线条数等于矩阵行数，则已找到最优矩阵，转第6步；否则，转第步；否则，转第4步；步；4.从矩阵中未被线条穿过的元素中减去这些元素中的最小数，并将这个从矩阵中未被线条穿过的元素中减去这些元素中的最小数，并将这个最小数加到直线交叉的元素上，其他元素不变；最小数加到直线交叉的元素上，其他元素不变；5.重复步骤重复步骤3和步骤和步骤4，直到获得最优矩阵；，直到获得最优矩阵；6.从仅有一个零的行或列开始，找出零元素对应的分配方案，每行梅列从仅有一个零的行或列开始，找出零元素对应的分配方案，每行梅列仅能确定一个元素，最后使每行和每列都有一个零元素。零元素对应仅

46、能确定一个元素，最后使每行和每列都有一个零元素。零元素对应的就是最优方案。的就是最优方案。l对于例对于例8.4求解：求解：M1M2M3M4每行最小数每行最小数J197353J27812117J346874J461113106M1M2M3M4J16402J20154J30243J40574M1M2M3M4J16402J20154J30243J40574每列最每列最小数小数0102M1M2M3M4J16300J20052J30141J40472M1M2M3M4J16300J20052J30141J40472M1M2M3M4J16300J20052J30030J40361M1M2M3M4J17300

47、J21052J30030J40361M1M2M3M4J17300J21052J30030J40361最优分配结果：最优分配结果： J1M3； J2M2； J3M4； J4M1；l作业调度，又称为等候线管理。所谓等候作业调度，又称为等候线管理。所谓等候线是指若干作业到达某个工作中心时处于线是指若干作业到达某个工作中心时处于等待的一种状态。等待的一种状态。l等候线管理的目的：降低在制品的数量和等候线管理的目的：降低在制品的数量和缩短制造提前期，同时使瓶颈的工作中心缩短制造提前期，同时使瓶颈的工作中心能够充分利用。能够充分利用。l按照限制力量，其排序的顺序应当是首先按照限制力量，其排序的顺序应当是首

48、先安排关键工作中心任务，然后再安排他工安排关键工作中心任务，然后再安排他工作中心任务。作中心任务。l为了缩短制造的提前期，可以采取的策略为了缩短制造的提前期，可以采取的策略有分批作业和作业分割。有分批作业和作业分割。l8.3.1 分批作业分批作业分批作业即把原来一张加工单的数量分成几批，分批作业即把原来一张加工单的数量分成几批，由几张加工单来完成，以缩短加工周期。由几张加工单来完成，以缩短加工周期。l每批数量可以不同；每批数量可以不同；l只有在几组工作中心能完成同样的工作时才有可能。只有在几组工作中心能完成同样的工作时才有可能。l每组工作中心都需要准备时间，因此，准备时间增加；每组工作中心都需

49、要准备时间，因此，准备时间增加；l工艺设备增加会带来成本的增加。工艺设备增加会带来成本的增加。l 8.3.1 分批作业分批作业 假设有一个订单，需要在加工中心假设有一个订单，需要在加工中心AB上完成。设上完成。设Q，为批量；，为批量；SA ，为在工作中心，为在工作中心A上准备时间；上准备时间；SB，为在工作中心，为在工作中心B上准备时间；上准备时间；TAB，为由工作中心，为由工作中心A上移至工作中心上移至工作中心B上的转移时间；上的转移时间；PA，为在工作中心，为在工作中心A上每单位的加工时间；上每单位的加工时间；PB，为在工作中心，为在工作中心B上每单位的加工时间。上每单位的加工时间。l8.

50、3.1 分批作业分批作业1、如果是一个批次：、如果是一个批次：L=SA+QPA+TAB+SB+QPB准备准备准准 备备一批次的加工时间一批次的加工时间一批次的加工时间一批次的加工时间工作中心工作中心T0总的提前期总的提前期工作中心工作中心A工作中心工作中心B转移时间转移时间l8.3.1 分批作业分批作业1、如果是一个批次：工作中心、如果是一个批次：工作中心B提前做好准备；提前做好准备；L=SA+QPA+TAB+QPB准备准备准准 备备一批次的加工时间一批次的加工时间一批次的加工时间一批次的加工时间工作中心工作中心T0总的提前期总的提前期工作中心工作中心A工作中心工作中心B转移时间转移时间l 8

51、.3.1 分批作业分批作业 将订单分成两个批次，即将订单分成两个批次，即Q=Q1+Q2，具体步骤：，具体步骤：1、一批作业分为两个批次；、一批作业分为两个批次；2、在第一个工作中心完成第一个批次时，直接将他转移到、在第一个工作中心完成第一个批次时，直接将他转移到第二个工作中心；第二个工作中心；3、当第一个工作中心执行第二个批次的作业时，第二个工、当第一个工作中心执行第二个批次的作业时，第二个工作中心开始执行第一个批次的作业；作中心开始执行第一个批次的作业；4、当第一个工作中心完成第二个批次时，立即将他转移到当第一个工作中心完成第二个批次时，立即将他转移到第二个工作中心；第二个工作中心；l8.3

52、.1 分批作业分批作业2、二个批次：、二个批次：准备准备准准 备备第一批次第一批次工作中心工作中心T0总的提前期总的提前期工作中心工作中心A工作中心工作中心B转移时间转移时间第二批次第二批次第一批次第一批次第二批次第二批次转移时间转移时间l8.3.1 分批作业分批作业2、二个批次：、二个批次：准备准备准准 备备第一批次第一批次工作中心工作中心T0总的提前期总的提前期工作中心工作中心A工作中心工作中心B转移时间转移时间第二批次第二批次第一批次第一批次第二批次第二批次转移时间转移时间l8.3.1 分批作业分批作业Q=Q1+Q2；Q1PB+TAB+SBQ2PA+TAB； Q1（QPA-SB）/（PB

53、+PA）；）；缩短的提前期：缩短的提前期：LS= （SA+SB+TAB+QPA+QPB）（）（SA+QPA+TAB+Q2PB）例例8.8 若若Q为为100单位，单位，PA为为10min/单位单位，PB为为5min/单位单位，SA为为50min，SB为为40min，转移时间，转移时间TAB为为30min，安排作业，安排作业。解：首先计算批量：解：首先计算批量：Q1（QPA-SB）/（PB+PA）=（10010-40）/（5+10）=64；分批前的提前期：分批前的提前期：L=SA+SB+TAB+QPA+QPB=50+40+30+10010+1005=1620（min）分配后的提前期：分配后的提前期

54、：L= SA+QPA+TAB+Q2PB=50+10010+30+365=1260 （min）缩短的提前期：缩短的提前期：LS=1620-1260=360 （min）l8.3.2 分批分割分批分割作业分割是将作业分成两个或两个以上的批次，作业分割是将作业分成两个或两个以上的批次，多个批次同时作业。多个批次同时作业。作业分割也是为了缩短提前期，通常会在每个工作业分割也是为了缩短提前期，通常会在每个工作中心上都有准备时间。作中心上都有准备时间。适用于：作业时间较短、一人多工位操作、重复适用于：作业时间较短、一人多工位操作、重复性设备闲置等情况下。性设备闲置等情况下。l8.3.2 分批分割分批分割作业

55、分割为两批后，如果同时开始作业，需要增加一作业分割为两批后，如果同时开始作业，需要增加一名操作人员。如果不想增加操作人员，该如何分割？名操作人员。如果不想增加操作人员，该如何分割？准备准备加工时间加工时间准备准备准备准备加工时间加工时间加工时间加工时间分批前分批前分批后分批后缩短的提前期缩短的提前期l8.3.2 分批分割分批分割准备准备加工时间加工时间准备准备准备准备加工时间加工时间加工时间加工时间分批前分批前分批后分批后缩短的提前期缩短的提前期l串行作业串行作业并行作业并行作业QSRMQSRMQSRM工作中心工作中心1工作中心工作中心2工作中心工作中心3提前期提前期QSRMQSRMQSRM工

56、作中心工作中心1工作中心工作中心2工作中心工作中心3Q：排队时间；：排队时间；S：准备时间；：准备时间；R：加工时间；：加工时间；M：转移时间。：转移时间。l时间组织：使加工对象在各个生产单位间时间组织：使加工对象在各个生产单位间的运动相互配合和衔接，实现有节奏的生的运动相互配合和衔接，实现有节奏的生产，达到提高劳动生产效率的目的。产，达到提高劳动生产效率的目的。l零件在加工过程中的移动有三种零件在加工过程中的移动有三种：（：（1）顺）顺序移动；（序移动；（2）平行移动；（）平行移动；（3）顺序平行）顺序平行移动。移动。l加工周期是从劳动对象原材料投入加工开加工周期是从劳动对象原材料投入加工开

57、始变成成品为业所经过的时间。始变成成品为业所经过的时间。l与生产过程概念相同，区别仅是此处不考与生产过程概念相同，区别仅是此处不考虑前期准备工作。虑前期准备工作。l 为分析方便，只计算零件的加工时间，不为分析方便，只计算零件的加工时间，不计算零件的搬运时间。计算零件的搬运时间。l当一次只生产一个零件时，零件只能顺次地经过各道工序加工，而不可能同时在不同的工序上加工。如某一个零件(即n=1)需经过车、刨、磨、钻四道工序(即m=4)加工，工序时间分别为10、5、15和5分钟。加工时，这个零件只能按车、刨、磨、钻顺序进行，所需时间如图所示。设： 一批零件数，n=3；工序数，m=4；则，共有三种移动方

58、式：（1）顺序移动；）顺序移动；（2）平行移动：）平行移动：（3）顺序平行移动。）顺序平行移动。2.平平行行移移动动方方式式(原理图) 保证劳动对象连续加工-一批零件中的每个零件在前道工序加工结束后，立即转移到后道工序去继续加工。 工序(分) 10 15 25 30 40 10 10 15 25 30 40 45 5 15 30 45 60 15 30 38 45 53 60 68 8 分 平行移动方式平行移动方式（操作图） (保证劳动对象连续加工) 工序 (分) 10 20 30 10 10 15 20 25 30 35 5 15 30 45 60 15 30 38 45 53 60 68

59、8 分 计算公式： 平行移动方式一批零件的加工周期平行移动方式一批零件的加工周期 =各道工序单件时间之和各道工序单件时间之和+(一批零件数量一批零件数量-1)各道工序中最大的工序单件时间各道工序中最大的工序单件时间 优点：生产过程时间最短； 缺点： 生产率高(工序时间短)的工序上设备有停顿现象，当各工序时间相等时，则设备可连续加工，运输工作量大且频繁。 加工对象： 大批量， 零件的加工时间长的产品。 6815) 13(38) 1(max1tntTmii平3.平行顺序移动方式平行顺序移动方式首先保证工作地连续加工，又尽量保证劳动对象连续加工，缩短劳动对象停歇时间，是顺序与平行相结合的劳动方式。工

60、序(分) 10 20 30 10 20 25 30 35 5 25 40 55 70 15 54 62 70 78 8 分计算公式： 平行顺序移动方式一批零件的加工周期平行顺序移动方式一批零件的加工周期 =各道工序单件时间之和一批零件数量各道工序单件时间之和一批零件数量- (一批一批零件数量零件数量-1)两相邻工序中单件时间较小者之和两相邻工序中单件时间较小者之和 =338-(3-1)(5+5+8)=78 分 优缺点：介于顺序-平行之间。 111)1(mimiitntnT较小平顺l 8.4.1 作业控制的基本概念作业控制的基本概念 美国生产与库存控制协会（美国生产与库存控制协会（APICS）对