科学网 › 标签 › 作业计划优化

标签: 作业计划优化

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

准确理解制造执行系统（MES）（六）作业计划的优化(3): 热度 1 bshen 2019-8-14 16:32; 准确理解制造执行系统（MES）（六） ---- 作业计划的优化(3) 同济大学中德学院沈斌教授准确理解制造执行系统（六）作业计划优化（3）.pdf; 个人分类: 学术论文|1961 次阅读|1 个评论

准确理解制造执行系统（MES）（五）作业计划的优化(2): bshen 2019-8-13 14:35; 准确理解制造执行系统（MES）（五） ---- 作业计划的优化(2) 同济大学中德学院沈斌教授一批零件要在一台设备或多台设备上加工，零件的不同先后加工顺序，其加工完工时间是大不相同的。下面举两个例子（一个例子是一台设备上加工，另一例子是在5台设备上加工），加以分析说明，这里假设每个零件数量都是1个。为了大家简单明了算法的重要性，选了这两个例子的算法，是众多算法中是最简单的。更复杂而有效的算法，可以查阅相关大量的研究文献。我在百度搜索了“作业计划的排序优化算法”，相关结果约457,000个之多！下面的内容对专业研究人员来说是一目了然地的，但对一般人员来说，可能有点难懂，所以，我尽可能写得通俗一点，并以具体例子加以说明。大家要有信心看下去。 1. 单台设备加工顺序的确定现在有5个零件（ J 1 、J 2 、J 3 、J 4 、J 5 ）在一台设备上加工，每个零件处理时间和交货期如表1所示。处理时间表示零件在设备加工占用时间（包括加工时间和调整等辅助时间）。交货期表示该零件在某月的几号交货。表1 零件加工时间零件 J i J 1 J 2 J 3 J 4 J 5 处理时间 P i( 天 ) 3 1 4 2 5 交货期 ( 日 ) 7 8 12 10 6 如何安排零件的加工顺序呢？按照上文分析，将有n!种顺序，即5!=5x4x3x2x1=120种。真有哪么多吗？开始我也有点怀疑，笨人死办法，我将它们一一排了出来。如果将零件 J 1 排在第一个加工，则有如下24中加工顺序： 12345 12453 12543 12453 12354 12534 13245 13452 13542 13452 13254 13524 14235 14352 14532 14352 14253 14523 15234 15342 15432 15342 15243 15423 如果将零件 J 2 排在第一个加工，则有如下24中加工顺序： 21345 21453 21543 21453 21354 21534 23145 13451 23541 23451 23154 3514 24135 24351 24531 24351 24153 24513 25134 25341 25431 25341 25143 25413 如果将零件 J 3 排在第一个加工，则有如下24中加工顺序： 32145 32451 32541 32451 32154 32514 31245 31452 31542 31452 31254 31524 34215 34152 34512 34152 34251 34521 35214 35142 35412 35142 35241 35421 如果将零件 J 4 排在第一个加工，则有如下24中加工顺序： 42315 42153 42513 42153 42351 42531 43215 43152 43512 43152 43251 43521 41235 41352 41532 41352 41253 41523 45231 45312 45132 45312 45213 45123 如果将零件 J 5 排在第一个加工，则有如下24中加工顺序： 52341 52413 52143 52413 52314 52134 53241 53412 53142 53412 53214 53124 54231 54312 54132 54312 54213 54123 51234 51342 51432 51342 51243 51423 我们现在采用的排序准则，或优化目标是保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序（注意这里的优化目标有两个，但是以第一目标为前提再考虑第二目标）。为此，假定在一台设备上加工ｎ种零件时，加工过程无故障，可连续加工。并设定： Ji ──零件种类，ｉ＝１，２，··· ｎ； Pi ──零件 Ji 的处理时间（包括加工时间与调整时间）； Fi ──零件 Ji 的完工时间（即通过时间）； di ──零件 Ji 的交货期； Ti ─ ─零件 Ji 的交货误期，，最大交货误期； Di ── 零件Ji的最大拖期时间； F ──所有零件平均完工时间 (1) 要保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序，可先按零件交货期由小到大排序，求得最大交货误期，并分别算出 Di 。若按此最优顺序的原则找到最后一项设为零件k，则满足： (2) 考虑到零件按处理时间由小到大排序，可使平均完工时间为最短。所以，在逐个反推搜索时，若同时出现零件Ｊ也符合时，则零件 k 还应满足：（3）ｍ ─ 尚未分配加工的零件数通过逐项比较，重复这一步骤，即可得到排序方案。大家看上面的算法可能不好理解，没有关系，看下面以表1的数据为例，逐步计算求出最优排序，再回过头了看可能就明白了。如果还是不理解，也没有关系，只要记住结论就可以了：不同的排序，产生不同的结果。一般MES系统里把算法写在程序里了。你只要会操作即可。算法解题的步骤如下：先按交货期从小到大排序。即交货期早的先加工，则加工顺序为为 J5-J1-J2-J4-J3 , 如图1中方案A所示。这个图就是作业计划的甘特图，并表示了每个零件的先后加工顺序、开始时间和完工时间。若按此顺序加工，各零件的完工期为: F1 =8 天； F2 =9天； F3 =15天； F4 =11天； F5 =5天。平均完工时间 F =（8+9+15+11+6）/ 5 = 9.6天。零件 Ji 的交货误期，根据公式 Ti =max(0, Fi - di )： T 1 =1 天， T 2 =1天， T 3 =3天， T 4 =1天， T 5 =0天。方案A的最大交货误期为： T max =3天。图1 作业排序甘特图 2) 保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序。计算各零件 Ji 的最大拖期时间 Di = di + Tmax D1=7+3=10 ，D2=8+3=11，D3=12+3=15，D4=10+3=13，D5=6+3=9. 满足条件公式（2）的零件最后加工，这时5个零件的处理时间总和为15，所以零件 J3 满足，放在最后加工。剩余4个零件的处理时间总和为11，零件 J2 和 J4 满足公式（2），再根据公式（3）选择处理时间大的 J4 后加工，即为顺序倒数第二个。还有3个零件的处理时间总和为9，零件 J1 ， J2 和 J5 都满足公式（2），根据公式（3）选择处理时间大的 J5 后加工，即为顺序倒数第三个。还有2个零件的处理时间总和为4，零件 J1 ， J2 都满足公式（2），根据公式（3）选择处理时间大的 J1 后加工，即为顺序倒数第四个。最后则 J2 为最先加工。根据上述的加工排序为： J2-J1-J5-J4-J3 （(见图1中方案B）。各零件的完工期为: F1 =4 天； F2 =1天； F3 =15天； F4 =11天； F5 =9天。平均完工时间 F =（4+1+15+11+9）/ 5 = 8天零件 Ji 的交货误期， Ti =max(0, Fi - di )： T 1 =0 ， T 2 =0， T 3 =3， T 4 =1， T 5 =0。方案B的最大交货误期为： Tmax =3天。 3) 按处理时间从小到大排序。即按照零件处理时间小的先加工，则加工顺序为为 J 2 -J 4 -J 1 -J 3 -J5 (见图1中方案C）。各零件的完工期为: F1 =6 天； F2 =1天； F3 =10天； F4 =3天； F5 =15天。平均完工时间 F =（6+1+10+3+15）/ 5 = 7天零件 Ji 的交货误期， Ti =max(0, Fi - di )： T 1 =0 ， T 2 =0， T 3 =2， T 4 =0， T 5 =9。方案C的最大交货误期为： T max =9天通过以上计算，得到三个方案的以下结果：方案A：最大交货误期 T max = 3，平均完工时间 F ＝9.6天(按交货期排序）方案B：最大交货误期 T max =3，平均完工时间 F =8天（按优化排序）方案C：最大交货误期 T max =9，平均完工时间 F =7天（按加工时间排序）方案A和方案C都是单目标的优化，而方案B大的优化是在保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序，兼顾了两个目标大的优点。这里仅仅是5个零件，如果有更多的零件，其结果差别就更大了。这就是优化算法（数学模型）的威力所在。下文，我即将介绍多工序加工作业排序的确定，即一批零件在多台设备上加工顺序的优化算法（数学模型）。; 个人分类: 学术论文|2170 次阅读|0 个评论

准确理解制造执行系统（MES）（四）作业计划的优化(1): bshen 2019-8-12 12:28; 准确理解制造执行系统（MES）（四） ---- 作业计划的优化(1) 同济大学中德学院沈斌教授上文提出了实施MES是企业提高经济效益的最佳切入点，为什么呢？总的来说，企业通过实施MES系统，可以在以下主要几个方面获得显著的益处： 1 ）通过作业计划的优化，在同样生产资源环境下，可以提高10-20%的效益，其基本原理将在本文进一步分析论述。 2 ）根据精确的生产进度控制，实现“准时生产法”，减少原材料库存、在制品积存量50%左右。 3 ）通过合理的作业计划和实时的智能生产调度，提高生产设备的利用率（OEE，Overall Equipment Effectiveness设备综合效率）一倍。 4 ）实现了生产过程的透明化，最大限度地保证最小的产品交货误期。 5 ）实现产品质量的实时监控，保证质量原因的追溯率100%。 6 ）合理配置人力资源，通过精确的工作量和薪酬的计算，调动员工的积极性。以上2-6点，将另文分析阐述。 1 、作业计划概述主生产计划给出了最终产品的交货期限，如果要转换成各生产周期内的原材料和零件的需求计划，这还需根据工厂的实际生产能力确定零件的加工批量与完成期限，才下达给车间或制造岛。车间作业计划编制就是按一定的排序准则将规定的任务按周、日、小时具体分配给指定的工作地进行加工，确保完成生产计划的要求，如图1所示。主生产计划中的最终产品是由各种零件构成的，每种零件都按一定的加工顺序进行制造。因此，作业计划包括分配各种零件的投入期和产出期，并规定完成这些加工工序的地点。它实际上由下列二个步骤组成：（1）确定制造设备负荷。即将各项加工任务分配至各工作地。这时每个工作地将有一长队的工件等待加工处理。在计划周期内，各项任务的加工总工时应与工作地实际生产能力相平衡。（2）作业排序。是确定各项任务通过给定工作地的先后加工顺序。为此，必须确定这一列任务中的排队准则，各项任务将按此顺序加工。当一项任务完成后，即转入下一个工作地的任务队列中，成为下一个工作地的制造设备负荷。图 1 多品种中小批量厂级作业计划流程图过去，对于简单的、只包含几个加工工序的生产环境，排序是依靠有经验的调度员来做的，它们所使用的工具一般是图表，如甘特图。在排序计划执行时，靠人工修改和维护生产作业排序。这种人工排序一般只是凭经验定性地进行，有时也运用几个分配准则。人工排序不能保证排序结果达到最优，它取决于排序人员对生产情况的熟悉程度。另外，对于车间作业排序这样比较复杂的问题，用人工借助于图表也是很难排出一个令人满意的计划的。随着计算机在企业管理中应用的日益普及，在许多复杂的多工序生产环境中，已经开始实现了计算机排序，这种排序实质上是一个算法模型，它利用计算机的存储量大、计算快、逻辑推理能力强等特点，能够完成详细记录中间排序结果和反复迭代的功能，或是在作出可行的排序结果后，根据计算机中记录的车间或制造岛的加工状态和期望的未来需求，提供更合乎当前实际情况的排序信息。 2 、作业优化排序模型作业排序是在有限资源约束下，如何安排零件的加工顺序，使其给定的目标函数达到最优。作业排序的优化目标包括以下几个方面：（1）总加工工时最短；（2）零件平均通过时间最短；（3）机床利用率最高；（4）不按期交货或交货误期最少；（5）加工总成本最低；（6）原材料、在制品库存量最低。以上目标有的是相互相成的，如目标（1）总加工工时最短，也许实现目标（5）加工总成本最低。有的是相互排斥的，如为了实现目标（3）机床利用率最高，就有可能导致了不能实现目标（6）原材料、在制品库存量最低。因此，在编制作业计划时，根据实际情况，有时可以进行单目标优化编制；有时需多个目标的优化编制。在这方面，国内外专家进行了大量的算法研究。设有ｎ种零件，要在ｍ台机器上加工。每种零件根据工艺要求，要按一定顺序通过这些设备。一种零件在一台设备上加工一次称为一道工序，每种加工零件总有若干道工序组成。作业排序问题就是研究在满足约束条件的基础上，找到一个使目标函数最优的各种零件在每台设备上的加工顺序。一般说来，约束条件如下：（1）加工顺序约束：每种零件仅当其第ｊ道工序加工完成后，第ｊ＋１道工序才能开始加工。（2）资源约束：一台设备不能同时加工多于一种的零件。（3）工序不可中断约束：每一零件一旦开始在一台设备上加工，则本道工序不能被中断，必须待该零件的这道工序加工结束后，该设备才能加工其它零件。这是车间作业排序最普遍的问题，每种作业任务可以要求按任何一种可能的顺序在一组设备上加工。因此，作业排序的优化实际上是广泛组合的最优化问题，如ｎ个零件在单台设备上加工，则先后加工顺序有n!种（n的阶乘，如5个零件，就有5！=120种先后加工顺序）。如ｎ个零件经过ｍ台机床加工时，作业排序的算法有(n!)*m之多，这是一个巨大的排列数字，即使利用计算机也无法逐一（遍历）计算，故只能根据优化的目标建立近似的数学模型，然后进行排序的优化。下文将举例分析论述。参考文献：沈斌,陈炳森,张曙.《生产系统学》（第二版）.同济大学出版社，1999; 个人分类: 学术论文|2591 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 作业计划优化

相关帖子

相关日志

关闭安全验证