制造业生产作业计划.ppt

《制造业生产作业计划.ppt》由会员分享，可在线阅读，更多相关《制造业生产作业计划.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1111章制造业生产作业计划章制造业生产作业计划华中科技大学管理学院陈荣秋生产任务的最终落实n nMRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。n n各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务，才算落到实处。n n将任务安排到工作地，牵涉到任务分配和作业排序问题编制作业计划要解决的问题n n工厂里要对每个工人和工作地安排每天的生产工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间；任务，规定开始时间和完成时间；n n医院要安排病人手术，为此要安排手术室、配医院要安排病人手术，为此要安排手术室、配备手术器械、手术医

2、师和护士；备手术器械、手术医师和护士；n n学校要安排上课时间表，使学生能按规定的时学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。间到规定的教室听事先安排的教师讲课。n n项目计划管理，也是一个作业计划问题。项目计划管理，也是一个作业计划问题。n n英文英文SchedulingScheduling可以译成编制作业计划或安排可以译成编制作业计划或安排日程计划日程计划(时间表时间表)。n n编制作业计划实质上是要将资源分配给不同的编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利任务，按照既定的优化目标，确定各种资源利用的时间问题。用的时

3、间问题。有关的名词术语n n排序排序(Sequencing)(Sequencing)是确定零件在机器上的加是确定零件在机器上的加工顺序。工顺序。n n编制作业计划编制作业计划(Scheduling)(Scheduling)则不仅包括确定加则不仅包括确定加工顺序，而且还包括加工任务的分配和加工每工顺序，而且还包括加工任务的分配和加工每个零件的开始时间和完成时间。个零件的开始时间和完成时间。n n“调度调度”是作业计划编制后实施生产控制所采是作业计划编制后实施生产控制所采取的一切行动，取的一切行动，“编制作业计划编制作业计划”是加工制造是加工制造发生之前的活动。火车时刻表是作业计划。火发生之前的活

4、动。火车时刻表是作业计划。火车时刻表制定后，对火车运行的安排，包括发车时刻表制定后，对火车运行的安排，包括发生晚点后的处理，都属于调度。生晚点后的处理，都属于调度。名词术语(续)n n“派工派工”(Dispatching)”(Dispatching)是在作业计划制定以是在作业计划制定以后，按照作业计划的要求，将具体生产任务通后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工过工票或施工单的形式下达到具体的机床和工人，属于通常所说的人，属于通常所说的“调度调度”范围。范围。n n“赶工赶工”(Expediting)”(Expediting)是在实际进度已落后是在实际

5、进度已落后于计划进度时采取的行动，也属于通常所说的于计划进度时采取的行动，也属于通常所说的“调度调度”范围。范围。n n“机器机器”，可以是工厂里的各种机床，也可以，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输以是电子的计算机中央处理单元、存贮器和输入、输出单元。表示入、输出单元。表示“服务者服务者”；名词术语(续)n n“零件”则代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件n n“加工路线”是零件加工经过不同机器构成的路线。比如，某零件要经过车、铣、占、磨的路线加工，我们

6、可以用M1,M2,M3,M4来表示。n n“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序要解决的问题 4参数表示法:n nn/m/A/Bn/m/A/B。其中其中,n,n 零件数；零件数；m m 机器数；机器数；A A 作业类型；在作业类型；在A A的位置若标以的位置若标以“F”“F”，则代表流水作业排序问题。若标以，则代表流水作业排序问题。若标以“P”“P”，则表示流水作业排列排序问题。若标，则表示流水作业排列排序问题。若标以以“G”“G”，则表示一般单件作业排序问题。当，则表示一般单件作业排序问题。当m m1 1，则，则A A处为空白处为空白 B B目标函数，通常是使其值最小。目标

7、函数，通常是使其值最小。流水作业计划问题n n流水线是流水车间(Flow shop)典型的代表，每个零件的加工路线都一致。n n只要加工路线一致：M1，M2,M3，.，Mm,不要求每个零件都经过每台机器加工最长流程时间Fmax的计算n n最长流程时间又称作加工周期最长流程时间又称作加工周期6/4/p/F6/4/p/Fmaxmax问题，当按顺序问题，当按顺序S S(6,1,5,2,4,3)6,1,5,2,4,3)加工时，求加工时，求F Fmaxmax.n n加工周期为46n/2/F/Fmax问题的最优算法n nJohnsonJohnson算法：算法：从加工时间矩阵中找出最短的加工时从加工时间矩阵

8、中找出最短的加工时间。间。若最短的加工时间出现在若最短的加工时间出现在M M1 1上，则对上，则对应的零件尽可能往前排；若最短加工时间出现应的零件尽可能往前排；若最短加工时间出现在在M M2 2上，则对应零件尽可能往后排。然后，从上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个若最短加工时间有多个，则任挑一个若所有零件都已排序，停止。否则，若所有零件都已排序，停止。否则，转步骤转步骤。n n求最优顺序算法步骤的改进n n把Johnson算法作些改变，改变后的算法按以下步骤进行：n n将所有aib

9、i的零件按ai值不减的顺序排成一个序列A。n n将所有aibi的零件按bi值不增的顺序排成一个序列B。n n将A放到B之前，就构成了最优加工顺序 n n序列序列A A为为(2(2，5 5，6 6，1)1)，序列，序列B B为为(4(4，3)3)，构，构成最优顺序为成最优顺序为(2(2，5 5，6 6，1 1，4 4，3)3)，与，与JohnsonJohnson算法结果一致。算法结果一致。n nJohnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序n n对于3台机器的

10、流水车间排序问题，只有几种特殊类型的问题找到了有效算法。n n对于一般的流水车间排列排序问题，可以用分支定界法。求一般n/m/P/Fmax问题近优解(Near optimal solution)的启发式算法 n n关键零件法n nCDS法 n n关键零件法求近优解举例CDS法n n Campbell-Dudek-Smith 三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(1)个加工顺序，取其中优者 n n当当1 1时，按时，按JohnsonJohnson算法得到加工顺序算法得到加工顺序(1(1，2 2，3 3，4)4)；当当2 2时，得

11、到加工顺序时，得到加工顺序(2(2，3 3，1 1，4)4)。对于顺序。对于顺序(2(2，3 3，1 1，4)4)，相应的，相应的F Fmaxmax2929。所以，取顺序。所以，取顺序(1(1，2 2，3 3，4)4)。我们已。我们已经知道，这就是最优顺序。经知道，这就是最优顺序。单件作业排序问题 n n加工描述矩阵和加工时间矩阵无延迟作业计划(non-delay schedule)的构成n n我们称每安排一道工序称作一“步”，设uuSSt ttt步步之之前前已已排排序序工工序序构构成成的的部部分作业计划；分作业计划；uu O Ot t 第第t t步步可可以以排排序序的的工工序序的的集集合；合

12、；uuT Tk k O Ot t 中中工工序序O Ok k的的最最早早可可能能开开工时间；工时间；uu T Tk k O Ot t 中中工工序序O Ok k的的最最早早可可能完工时间。能完工时间。无延迟作业计划的构成步骤:n n 设设t t1 1，SS1 1 为空集，为空集，OO1 1 为各工件为各工件第一道工序的集合。第一道工序的集合。求求T T*minTminTk k，并求出，并求出T T*出现的机器出现的机器M M*。如果。如果M M*有多台，则任选一台。有多台，则任选一台。从从OOt t 中挑出满足以下两个条件的工中挑出满足以下两个条件的工序序O Oj j：需要机器：需要机器M M*加

13、工，且加工，且T Tj jT T*。将确定的工序将确定的工序O Oj j放入放入SSt t，从，从 O Ot t 中消去中消去O Oj j，并将，并将O Oj j的紧后工序放入的紧后工序放入 O Ot t ，使，使t tt t1 1。若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否；否则，停止。则，停止。优先派工法则n n在在介介绍绍无无延延迟迟作作业业计计划划的的构构成成步步骤骤时时，其其中中第第步步的的两两个个条条件件一一般般都都有有多多个个工工序序可可以以满满足足。按按什什么么样样的的准准则则来来选选择择可可安安排排的的工工序序，对对作作业业计计划划的的优优劣劣有有很很大大影影响

14、响。为为了了得得到到所所希希望望的的作作业业计计划划，人人们们提提出出了了很很多多优优先先调调度度法法则则，按按优优先先调调度度法法则则挑挑选选工工序序比比随随意意挑挑选选一一道道工工序序的的方方法法更更能能符符合合计计划划编编制制者者的的要要求求，同同时时又又不不必必列列出所有可能的作业计划，从而计算量小。出所有可能的作业计划，从而计算量小。n n迄迄今今，人人们们已已提提出出了了100100多多个个优优先先调调度度法法则则，其中主要的有下其中主要的有下8 8个：个：n n SPT(Shortest SPT(Shortest Processing Processing Time)Time)法

15、法则优先选择加工时间最短的工序。则优先选择加工时间最短的工序。n n FCFS(First FCFS(First Come Come First First Served)Served)法法则优先选择最早进入可排工序集合的工件。则优先选择最早进入可排工序集合的工件。优先派工法则(续)n nEDD(Earliest EDD(Earliest Due Due Date)Date)法法则则优优先先选择完工期限紧的工件。选择完工期限紧的工件。n n MWKR(Most MWKR(Most Work Work Remaining)Remaining)法法则则优先选择余下加工时间最长的工件。优先选择余下加

16、工时间最长的工件。n nLWKR(Least LWKR(Least Work Work Remaining)Remaining)法法则则优先选择余下加工时间最短的工件。优先选择余下加工时间最短的工件。n nMOPNR(Most MOPNR(Most Operations Operations Remaining)Remaining)法则优先选择余下工序数最多的工件。法则优先选择余下工序数最多的工件。n nSCR(Smallest SCR(Smallest Critical Critical Ratio)Ratio)法法则则优优先先选选择择临临界界比比最最小小的的工工件件。临临界界比比为为工工件

17、件允允许停留时间与工件余下加工时间之比。许停留时间与工件余下加工时间之比。n nRANDOMRANDOM法则随机地挑一个工件法则随机地挑一个工件 随机抽样法n n用用穷穷举举法法或或分分支支定定界界法法求求一一般般单单件件车车间间排排序序问问题题的的最最优优解解时时，实实际际上上比比较较了了全全部部能能动动作作业业计计划划；采采用用优优先先调调度度法法则则求求近近优优解解时时，只只选选择择了了一种作业计划。一种作业计划。n n随机抽样法介于这两个极端之间。随机抽样法介于这两个极端之间。n n它从全部无延迟作业计划之中抽样，得出多个它从全部无延迟作业计划之中抽样，得出多个作业计划，从中选优。作业

18、计划，从中选优。n n应用随机抽样法时，实际上是对同一个问题多应用随机抽样法时，实际上是对同一个问题多次运用次运用RANDOMRANDOM法则来决定要挑选的工序，从而法则来决定要挑选的工序，从而得到多个作业计划。得到多个作业计划。概率调度法n n随机抽样法是从随机抽样法是从k k个可供选择的工序以等概率个可供选择的工序以等概率方式挑选，每个工序被挑选的概率为方式挑选，每个工序被挑选的概率为1 1k k，这，这种方法没有考虑不同工序的特点，有一定盲目种方法没有考虑不同工序的特点，有一定盲目性。性。n n例如，在构在无延迟作业计划的第例如，在构在无延迟作业计划的第步有步有3 3道道工序，工序，A

19、A、B B和和C C可挑选，这可挑选，这3 3道工序所需的时间道工序所需的时间分别为分别为3 3，4 4和和7 7。如果按。如果按RANDOMRANDOM法则，每道工法则，每道工序挑选上的概率都是序挑选上的概率都是1 13 3；如果按；如果按SPTSPT法则，法则，则只能挑选工序则只能挑选工序A A。现按目标函数的要求，选。现按目标函数的要求，选择了择了SPTSPT法则。按概率调度法，将这法则。按概率调度法，将这3 3道工序按道工序按加工时间从小到大排列，然后给每道工序从大加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率，比如到小分配一个被挑选的概率，比如A A、B B和和C C的的挑选概率分别为挑选概率分别为6 61414、5 51414和和3 31414。