搜索
制造业生产作业计划华中科技大学管理学院陈荣秋生产任务的最终落实MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务，才算落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题编制作业计划要解决的问题工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间；医院要安排病人手术，为此要安排手术室、配备手术器械、手术医师和护士；学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。项目计划管理，也是一个作业计划问题。英文Scheduling可以译成编制作业计划或安排日程计划(时间表)。编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。有关的名词术语排序(Sequencing)是确定零件在机器上的加工顺序。编制作业计划(Scheduling)则不仅包括确定加工顺序，而且还包括加工任务的分配和加工每个零件的开始时间和完成时间。“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动。火车时刻表是作业计划。火车时刻表制定后，对火车运行的安排，包括发生晚点后的处理，都属于调度。名词术语(续)“派工”(Dispatching)是在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人，属于通常所说的“调度”范围。“赶工”(Expediting)是在实际进度已落后于计划进度时采取的行动，也属于通常所说的“调度”范围。“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。表示“服务者”；名词术语(续)“零件”则代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工路线”是零件加工经过不同机器构成的路线。比如，某零件要经过车、铣、占、磨的路线加工，我们可以用M1,M2,M3,M4来表示。“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序要解决的问题4参数表示法:n/m/A/B。其中,n──零件数；m──机器数；A──作业类型；在A的位置若标以“F”，则代表流水作业排序问题。若标以“P”，则表示流水作业排列排序问题。若标以“G”，则表示一般单件作业排序问题。当m＝1，则A处为空白B──目标函数，通常是使其值最小。流水作业计划问题流水线是流水车间(Flowshop)典型的代表，每个零件的加工路线都一致。只要加工路线一致：M1，M2,M3，…..，Mm,不要求每个零件都经过每台机器加工最长流程时间Fmax的计算最长流程时间又称作加工周期6/4/p/Fmax问题，当按顺序S＝(6,1,5,2,4,3)加工时，求Fmax.表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331加工周期为46表11－2顺序S下的加工时间矩阵i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446n/2/F/Fmax问题的最优算法Johnson算法：①从加工时间矩阵中找出最短的加工时间。②若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个③若所有零件都已排序，停止。否则，转步骤①。求最优顺序表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。算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：①将所有ai≤bi的零件按ai值不减的顺序排成一个序列A。②将所有ai＞bi的零件按bi值不增的顺序排成一个序列B。③将A放到B之前，就构成了最优加工顺序序列A为(2，5，6，1)，序列B为(4，3)，构成最优顺序为(2，5，6，1，4，3)，与Johnson算法结果一致。表11-4改进算法i123456ai518534bi722474i256143ai134558bi274742Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题，可以用分支定界法。求一般n/m/P/Fmax问题近优解(Nearoptimalsolution)的启发式算法关键零件法CDS法关键零件法求近优解举例表11-5加工时间矩阵i1234Pi11263Pi28429Pi34582表11－6用关键零件法求解i1234Pi11263Pi28429Pi34582pi13111614CDS法Campbell-Dudek-Smith三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(ｍ－1)个加工顺序，取其中优者当ｌ＝1时，按Johnson算法得到加工顺序(1，2，3，4)；当ｌ＝2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1，4)，相应的Fmax＝29。所以，取顺序(1，2，3，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)的构成我们称每安排一道工序称作一“步”，设{St}──t步之前已排序工序构成的部分作业计划；{Ot}──第t步可以排序的工序的集合；Tk──{Ot}中工序Ok的最早可能开工时间；Tk’──{Ot}中工序Ok的最早可能完工时间。无延迟作业计划的构成步骤:①设t＝1，{S1}为空集，{O1}为各工件第一道工序的集合。②求T*＝min{Tk}，并求出T*出现的机器M*。如果M*有多台，则任选一台。③从{Ot}中挑出满足以下两个条件的工序Oj：需要机器M*加工，且Tj＝T*。④将确定的工序Oj放入{St}，从{Ot}中消去Oj，并将Oj的紧后工序放入{Ot}，使t＝t＋1。⑤若还有未安排的工序，转步骤②；否则，停止。表11-11无延迟计划的构成t{Ot}TkTkT*M*Oj11.1.12.1.3002300M1M31.1.121.2.32.1.320630M32.1.331.2.32.2.1337733M3M11.2.341.3.22.2.173873M12.2.151.3.22.3.27781277M2M22.3.262.3.281312M21.3.21,1,11,2,31,3,2241D＝T＝2,1,32,2,12,3,2345机器M11，1，12，2，1237M22.3.21.3.271213M32.1.31.2.3370时间图11－2无延迟作业计划优先派工法则在介绍无延迟作业计划的构成步骤时，其中第③步的两个条件一般都有多个工序可以满足。按什么样的准则来选择可安排的工序，对作业计划的优劣有很大影响。为了得到所希望的作业计划，人们提出了很多优先调度法则，按优先调度法则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。迄今，人们已提出了100多个优先调度法则，其中主要的有下8个：①SPT(ShortestProcessingTime)法则优先选择加工时间最短的工序。②FCFS(FirstComeFirstServed)法则优先选择最早进入可排工序集合的工件。优先派工法则(续)③EDD(EarliestDueDate)法则优先选择完工期限紧的工件。④MWKR(MostWorkRemaining)法则优先选择余下加工时间最长的工件。⑤LWKR(LeastWorkRemaining)法则优先选择余下加工时间最短的工件。⑥MOPNR(MostOperationsRemaining)法则优先选择余下工序数最多的工件。⑦SCR(SmallestCriticalRatio)法则优先选择临界比最小的工件。临界比为工件允许停留时间与工件余下加工时间之比。⑧RANDOM法则随机地挑一个工件随机抽样法用穷举法或分支定界法求一般单件车间排序问题的最优解时，实际上比较了全部能动作业计划；采用优先调度法则求近优解时，只选择了一种作业计划。随机抽样法介于这两个极端之间。它从全部无延迟作业计划之中抽样，得出多个作业计划，从中选优。应用随机抽样法时，实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划。概率调度法随机抽样法是从k个可供选择的工序以等概率方式挑选，每个工序被挑选的概率为1／k，这种方法没有考虑不同工序的特点，有一定盲目性。例如，在构在无延迟作业计划的第③步有3道工序，A、B和C可挑选，这3道工序所需的时间分别为3，4和7。如果按RANDOM法则，每道工序挑选上的概率都是1／3；如果按SPT法则，则只能挑选工序A。现按目标函数的要求，选择了SPT法则。按概率调度法，将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率，比如A、B和C的挑选概率分别为6／14、5／14和3／14。