一类典型成组作业生产优化调度的研究(1)

《一类典型成组作业生产优化调度的研究(1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一类典型成组作业生产优化调度的研究摘要成组作业生产优化调度在现代化生产中对提高生产效率，增加企业经济效益有重要意义，而它所涉及的组合优化问题大多数是NP-Hard问题。因此对该问题的研究具有广泛的应用背景和理论研究上的挑战性，成为目前国内外生产优化调度领域中的一个研究热点。本文简要介绍了研究成组作业生产优化调度常用的有效算法；针对作业有效、批有效和批量加工三类成组作业生产优化调度模式，系统分析了由不同的机器环境、作业加工特点和优化目标所构成的各种具体问题的计算复杂度及所提出的算法特点和最新研究进展：指出了一些至今尚未解决的问题。在此工作基础上，对作业有效的一类成组作业生产优化调度进行了深入的研

2、究，并分别对不同的具体优化调度问题，导出了一些优化性质，发展了有效的启发算法、遗传算法和分枝定界算法。本文主要创新是：针对优化目标是总流程时间的单机成组作业优化调度问题提出了一种启发算法。该算法计算量小，适合求解大规模优化调度问题。实验仿真表明该算法能够求得最优解或次优解，其性能明显优于已有的启发算法。针对优化目标是最大延迟的单机成组作业优化调度问题，我们通过分析问题优化必要条件发展了基本作业组理论，在此基础上提出了一种适合求解大规模优化调度问题的遗传算法。实验仿真显示该算法的有效性。针对优化目标是总流程时间的两机流水车间成组作业优化调度问题，仅考虑作业组和组内排序，提出了一种遗传算法。该遗传

3、算法分两层：一层优化组内作业排序，另一层优化作业组排序。针对天津钢管公司轧制钢管生产过程实际情况，选取了80个作业，在机器1(狄塞尔穿孔机)和机器2(定径机)上加工时间数据，根据不同的孔型和不同的成品尺寸分成8个作业组，每组有不同的在线准备时间(组设置时间)。就上述数据进行了仿真实验，遗传算法对初始最好解的平均改善率达7．7％。本文研究了优化目标是总流程时间的两机流水车间成组作业优化调度问题的几种特殊情况。对其中两种情况，分别找到了多项式时问可解的优化算法。对另外三种情况，分别导出了一些优化性质，在此基础上发展了启发算法和分枝定界算法。实验仿真表明，所提出的所有启发算法的解平均误差不超过2％，

4、所有分枝定界算法在合理时间内可求解30个作业的调度问题。本文对优化目标是最大作业延迟的两机流水车间成组作业优化调度问题进行研究。在假设作业分组已确定的情况下，导出了作业组和组内作业排序的三个优先原则，并利用这些优先规则发展了启发算法。把启发算法的解作为一个上界，同时利用优化性质，发展了分枝定界算法。大量实验仿真表明所提出的启发算法能够找到最优解或次优解，分枝定界算法在合理的计算时间内能够求解具有16个作业的优化调度问题。本文研究了具有No—wait机器环境的两机流水车间成组作业优化调度问题。在该问题的研究中，同时考虑作业分组、作业组和组内作业排序，发展了两个作业组合并规则，导出了三个排序优化性

5、质，在此基础上提出了启发算法。对大量随机生成的数据进行了实验仿真，仿真结果显示，启发式算法解的误差大多数在10％之内，并且该算法求解大规模调度问题的时间花费很小。通过对作业有效的一类成组作业生产优化调度的深入研究，我们认识到借鉴和利用传统生产优化调度的理论结果和方法是研究成组作业生产优化调度的重要途径：利用人们在现代智能计算上的最新研究成果是研究成组作业生产优化调度的重要手段。在理论上，成组作业生产优化调度作为一个重要的研究方向无论在研究的深度或者广度上都有待进一步发展：在应用上，如何把各种成组作业生产优化调度算法结合实际问题集成到管控一体化软件平台上，实现工业生产的智能调度是非常有意义的工作

6、。关键词：调度，成组作业，设置时间，启发算法，遗传算法，分枝定界算法STUDYONPRODUCTIONOPTIMIZINGSCHEDULINGFOR0NETYPICALGRoUPnⅥGJOBAbstractThestudyingonoptimizingproductionschedulingcharacterizedbygroupingjobhasbecomeasignificantinterestinthelastdecadebecauseofitsextensiveapplicationinindustriesanditsdifficultytodealwith．Thispaperbrie

7、flyintroducessomemainlyeffectiveapproachesforsolvingtheoptimizingschedulingproblemofgroupingjobs．Accordingtothecharacteristicsofprocessedjobs，thegroupingjobschedulingcanbeclassifiedtothreetypicalmodel