aal-制造业生产作业计划（PDF 27）

第11章制造业生产作业计划与控制第11章制造业生产作业计划与控制生产任务的最终落实生产任务的最终落实

MRPMRP确定各车间的零部件投入出产计划，确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间将全厂性的产品出产计划变成了各车间的生产任务。的生产任务。

各车间要将车间的生产任务变成各个班各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务，才组、各个工作地和各个工人的任务，才算落到实处。算落到实处。

将任务安排到工作地，牵涉到任务分配将任务安排到工作地，牵涉到任务分配和作业排序问题和作业排序问题编制作业计划要解决的问题编制作业计划要解决的问题

工厂里要对每个工人和工作地安排每天的生产工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间；任务，规定开始时间和完成时间；

医院要安排病人手术，为此要安排手术室、配医院要安排病人手术，为此要安排手术室、配备手术器械、手术医师和护士；备手术器械、手术医师和护士；

学校要安排上课时间表，使学生能按规定的时学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。间到规定的教室听事先安排的教师讲课。

项目计划管理，也是一个作业计划问题。项目计划管理，也是一个作业计划问题。

英文英文SchedulingScheduling可以译成编制作业计划或安排可以译成编制作业计划或安排日程计划日程计划((时间表时间表))。。

编制作业计划实质上是要将资源分配给不同的编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利任务，按照既定的优化目标，确定各种资源利用的时间问题。用的时间问题。有关的名词术语有关的名词术语

排序排序((Sequencing)Sequencing)是确定零件在机器上的加是确定零件在机器上的加工顺序。工顺序。

编制作业计划编制作业计划((Scheduling)Scheduling)则不仅包括确定加则不仅包括确定加工顺序，而且还包括加工任务的分配和加工每工顺序，而且还包括加工任务的分配和加工每个零件的开始时间和完成时间。个零件的开始时间和完成时间。

““调度调度””是作业计划编制后实施生产控制所采取是作业计划编制后实施生产控制所采取的一切行动，的一切行动，““编制作业计划编制作业计划””是加工制造发生是加工制造发生之前的活动。火车时刻表是作业计划。火车时之前的活动。火车时刻表是作业计划。火车时刻表制定后，对火车运行的安排，包括发生晚刻表制定后，对火车运行的安排，包括发生晚点后的处理，都属于调度。点后的处理，都属于调度。名词术语(续)名词术语(续)

““派派工工””(Dispatching)(Dispatching)是在作业计划制定以后是在作业计划制定以后，按照作业计划的要求，将具体生产任务通过，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人工票或施工单的形式下达到具体的机床和工人，属于通常所说的，属于通常所说的““调度调度””范围。范围。

““赶工赶工””((Expediting)Expediting)是在实际进度已落后于计是在实际进度已落后于计划进度时采取的行动，也属于通常所说的划进度时采取的行动，也属于通常所说的““调调度度””范围。范围。

““机器机器””，可以是工厂里的各种机床，也可以是，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入是电子的计算机中央处理单元、存贮器和输入、输出单元。表示、输出单元。表示““服务者服务者””。。名词术语(续)名词术语(续)

““零件零件””则代表则代表““服务对象服务对象””。零件可以是单。零件可以是单个零件，也可以是一批相同的零件个零件，也可以是一批相同的零件

““加工路线加工路线””是零件加工经过不同机器构是零件加工经过不同机器构成的路线。比如，某零件要经过车、铣成的路线。比如，某零件要经过车、铣、钻、磨的路线加工，我们可以用、钻、磨的路线加工，我们可以用MM11,M,M22,M,M33,M,M44来表示。来表示。

““加工顺序加工顺序””则表示每台机器加工则表示每台机器加工nn个零件个零件的先后顺序，是排序要解决的问题的先后顺序，是排序要解决的问题4参数表示法:4参数表示法:

n/m/A/Bn/m/A/B。。其中其中,,nn────零件数；零件数；mm────机器数；机器数；AA────作业类型；在作业类型；在AA的位置若标以的位置若标以““FF””，，则代表流水作业排序问题。若标以则代表流水作业排序问题。若标以““PP””，，则表示流水作业排列排序问题。若标以则表示流水作业排列排序问题。若标以““GG””，，则则表示一般单件作业排序问题。当表示一般单件作业排序问题。当mm＝＝11，则，则AA处处为空白为空白BB────目标函数，通常是使其值最小目标函数，通常是使其值最小。。流水作业计划问题流水作业计划问题

流水线是流水车间流水线是流水车间((Flowshop)Flowshop)典型的典型的代表，每个零件的加工路线都一致。代表，每个零件的加工路线都一致。

只要加工路线一致：只要加工路线一致：MM11，，MM22,,MM33，，……....，，MMmm,,不要求每个零件都经过每台机器加工不要求每个零件都经过每台机器加工最长流程时间Fmax的计算最长流程时间Fmax的计算

最长流程时间又称作加工周期最长流程时间又称作加工周期6/4/6/4/p/p/FFmaxmax问题，当按顺序问题，当按顺序SS＝＝((6,1,5,2,4,3)6,1,5,2,4,3)加工时，求加工时，求FFmaxmax..表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331

加工周期为加工周期为4646表11－2顺序S下的加工时间矩阵i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446n/2/F/Fmax问题的最优算法n/2/F/Fmax问题的最优算法

JohnsonJohnson算法：算法：①①从加工时间矩阵中找出最短的加工时从加工时间矩阵中找出最短的加工时间。间。②②若最短的加工时间出现在若最短的加工时间出现在MM11上，则对上，则对应的零件尽可能往前排；若最短加工时间出现应的零件尽可能往前排；若最短加工时间出现在在MM22上，则对应零件尽可能往后排。然后，从上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个若最短加工时间有多个，则任挑一个③③若所有零件都已排序，停止。否则，若所有零件都已排序，停止。否则，转步骤①。转步骤①。

求最优顺序求最优顺序表11－3加工时间矩阵i123456ai518534bi722474将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143最优加工顺序为S＝(2，5，6，1，4，3)。最优顺序下的Fmax=28。算法步骤的改进算法步骤的改进

把把JohnsonJohnson算法作些改变，改变后的算法算法作些改变，改变后的算法按以下步骤进行：按以下步骤进行：

①①将所有将所有aaii≤≤bbii的零件的零件按按aaii值不减值不减的顺序排成一个序列的顺序排成一个序列AA。。

②②将所有将所有aaii＞＞bbii的零件按的零件按bbii值不增值不增的顺序排成一个序列的顺序排成一个序列BB。。

③③将将AA放到放到BB之前，就构成了最优之前，就构成了最优加工顺序加工顺序

序列序列AA为为(2(2，，55，，66，，1)1)，序列，序列BB为为(4(4，，3)3)，构，构成最优顺序为成最优顺序为(2(2，，55，，66，，11，，44，，3)3)，与，与JohnsonJohnson算法结果一致。算法结果一致。表11-4改进算法i123456ai518534bi722474i256143ai134558bi274742

JohnsonJohnson法则只是一个充分条件，不是必法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例也可能是最优顺序。如对例1111--22顺序顺序(2(2，，55，，66，，44，，11，，3)3)不符合不符合JohnsonJohnson法则，法则，但它也是一个最优顺序但它也是一个最优顺序

对于对于33台机器的流水车间排序问题，只有台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。几种特殊类型的问题找到了有效算法。

对于一般的流水车间排列排序问题，可对于一般的流水车间排列排序问题，可以用分支定界法。以用分支定界法。求一般n/m/P/Fmax问题近优解(Nearoptimalsolution)的启发式算法求一般n/m/P/Fmax问题近优解(Nearoptimalsolution)的启发式算法

关键零件法关键零件法

CDSCDS法法

关键零件法求近优解举例关键零件法求近优解举例表11-5加工时间矩阵i1234Pi11263Pi28429Pi34582表11－6用关键零件法求解i1234Pi11263Pi28429Pi34582pi13111614CDS法CDS法

CampbellCampbell--DudekDudek--SmithSmith三人提出了三人提出了一个启发式算法一个启发式算法,,简称简称CDSCDS法。他们把法。他们把JohnsonJohnson算法用于一般的算法用于一般的n/m/P/n/m/P/FFmaxmax问题问题，得到，得到((ｍ－ｍ－1)1)个加工顺序，取其中优者个加工顺序，取其中优者

当ｌ＝当ｌ＝11时，按时，按JohnsonJohnson算法得到加工顺序算法得到加工顺序(1(1，，22，，33，，4)4)；；当ｌ＝当ｌ＝22时，得到加工顺序时，得到加工顺序(2(2，，33，，11，，4)4)。对于顺序。对于顺序(2(2，，33，，11，，4)4)，相应的，相应的FFmaxmax＝＝2929。。所以，取顺序所以，取顺序(1(1，，22，，33，，4)4)。我们。我们已经知道，这就是最优顺序。已经知道，这就是最优顺序。表11－7用CDS法求解i1234Pi11263l=1Pi34582Pi1+pi296812L=2Pi2+pi31291011单件作业排序问题单件作业排序问题

加工描述矩阵和加工时间矩阵加工描述矩阵和加工时间矩阵1,1,11,2,31,3,2241D＝T＝2,1,32,2,12,3,2345无延迟作业计划(non-delayschedule)的构成无延迟作业计划(non-delayschedule)的构成

我们称每安排一道工序称作一我们称每安排一道工序称作一““步步””，设，设{{SStt}}────tt步之前已排序工序构成的部步之前已排序工序构成的部分作业计划；分作业计划；{{OOtt}}────第第tt步可以排序的工序的集步可以排序的工序的集合；合；TTkk────{{OOtt}}中工序中工序OOkk的最早可能开的最早可能开工时间；工时间；TTkk’’────{{OOtt}}中工序中工序OOkk的最早可能的最早可能完工时间。完工时间。无延迟作业计划的构成步骤:无延迟作业计划的构成步骤:

①①设设tt＝＝11，，{S{S11}}为空集，为空集，{{OO11}}为各工件为各工件第一道工序的集合。第一道工序的集合。②②求求TT**＝＝min{min{TTkk}}，，并求出并求出TT**出现的机器出现的机器MM**。。如果如果