流水作业生产线上工件的加工问题.doc
约18页DOC格式手机打开展开
流水作业生产线上工件的加工问题,页数 18字数 7484摘要作为经典排序问题的推广, 处理机的排序问题具有广泛的实际背景.对于目标函数是极小化排序时间表长度的情况,可以采用多种的讨论方式。此文中根据所提的问题分别采用了各种不同的方法，对问题进行描述与解答，力求通过算法的多样性对问题能够得到最优解或近似最优解。 第一问为n...
内容介绍
此文档由会员 猛龙 发布
流水作业生产线上工件的加工问题
页数 18 字数 7484
摘要
作为经典排序问题的推广, 处理机的排序问题具有广泛的实际背景.对于目标函数是极小化排序时间表长度的情况,可以采用多种的讨论方式。
此文中根据所提的问题分别采用了各种不同的方法，对问题进行描述与解答，力求通过算法的多样性对问题能够得到最优解或近似最优解。
第一问为n/2排序问题，利用JOHNSON法则，最优子结构定理和递归算法给出一组最优排序，在JOHNSON法则的基础上可以用遗传算法和模拟退火算法综合利用，最终确定最优的排序。
第二问对于当m=3,m=4即机器数为3和4时，对机器数为3采用分支定界法、整数规划法求解，对于机器数为4时，实际生产中的排序问题可以采用启发式算法。对于此问题，在此采用了Palmer算法。同时也能用CDS法进行求解。
第三问m/n排序问题，确定给定的任意一个工件序，用递归算法，随机产生一组顺序S={S1,S2,……,Sn}集合,按顺序S={S1,S2,……,Sn}列出加工矩阵，对于第一行第一列，只需把加工时间的数值作为完工时间标在加工时间的右上角，对于第一行元素，只需从左到右依次将前一列右上角的数字加上计算列的加工时间，将其结果填在计算列加工时间的右上角。对于从第2行到第m行，第一列的算法相同。只要把上一行右上角的数字和本行的加工时间相加，将结果填在本行加工时间的右上角；从第2列到第n列，则要从本行前一列右上角和本上一行的右上角数字取最大者，再和本列加工时间相加，将结果填在本列加工时间得右上角，这样计算下去，最后一行的最后一列右上角数字即是Cmsn 。
关键字 JOHNSON法则，CDS法，最优子结构，遗传算法，模拟退火算法 Gantt图，递归算法 蚂蚁算法 分支定界
参考文献
1、生产计划与控制 潘尔顺 上海交通大学出版社 2003
2、数学模型 洪毅 林健良 陶志穗 高等教育出版社 2004
3、并行分布计算中的调度算法理论与设计 何炎祥 朱福喜 武汉大学出版社 2003
4、生产主管一日通 吴少平 广东经济出版社 2004
5、Production and Operations Management (Manufacturing and Services) Richard B.Chase Nicholas J.aquilano F.Robert Jacobs McGraw-Hill
页数 18 字数 7484
摘要
作为经典排序问题的推广, 处理机的排序问题具有广泛的实际背景.对于目标函数是极小化排序时间表长度的情况,可以采用多种的讨论方式。
此文中根据所提的问题分别采用了各种不同的方法，对问题进行描述与解答，力求通过算法的多样性对问题能够得到最优解或近似最优解。
第一问为n/2排序问题，利用JOHNSON法则，最优子结构定理和递归算法给出一组最优排序，在JOHNSON法则的基础上可以用遗传算法和模拟退火算法综合利用，最终确定最优的排序。
第二问对于当m=3,m=4即机器数为3和4时，对机器数为3采用分支定界法、整数规划法求解，对于机器数为4时，实际生产中的排序问题可以采用启发式算法。对于此问题，在此采用了Palmer算法。同时也能用CDS法进行求解。
第三问m/n排序问题，确定给定的任意一个工件序，用递归算法，随机产生一组顺序S={S1,S2,……,Sn}集合,按顺序S={S1,S2,……,Sn}列出加工矩阵，对于第一行第一列，只需把加工时间的数值作为完工时间标在加工时间的右上角，对于第一行元素，只需从左到右依次将前一列右上角的数字加上计算列的加工时间，将其结果填在计算列加工时间的右上角。对于从第2行到第m行，第一列的算法相同。只要把上一行右上角的数字和本行的加工时间相加，将结果填在本行加工时间的右上角；从第2列到第n列，则要从本行前一列右上角和本上一行的右上角数字取最大者，再和本列加工时间相加，将结果填在本列加工时间得右上角，这样计算下去，最后一行的最后一列右上角数字即是Cmsn 。
关键字 JOHNSON法则，CDS法，最优子结构，遗传算法，模拟退火算法 Gantt图，递归算法 蚂蚁算法 分支定界
参考文献
1、生产计划与控制 潘尔顺 上海交通大学出版社 2003
2、数学模型 洪毅 林健良 陶志穗 高等教育出版社 2004
3、并行分布计算中的调度算法理论与设计 何炎祥 朱福喜 武汉大学出版社 2003
4、生产主管一日通 吴少平 广东经济出版社 2004
5、Production and Operations Management (Manufacturing and Services) Richard B.Chase Nicholas J.aquilano F.Robert Jacobs McGraw-Hill
