基于候鸟优化算法的有限缓冲区流水车间调度优化研究

《基于候鸟优化算法的有限缓冲区流水车间调度优化研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学硕士学位论文1绪论1.1课题来源本课题来源于国家自然基金重点项目“离散车间制造系统高效低碳运行优化理论与关键技术”（项目编号：51035001），国家自然基金项目“机械加工系统基于实时信息反馈的稳健性调度优化理论、算法与应用”（项目编号：51275190）。1.2研究目的与意义随着全球市场竞争的加剧、客户需求越来越多样化和个性化，企业面临越来越多的压力和挑战。传统企业想要从全球范围的竞争中胜出，必须在有限的资源和时间约束下，制定出更好的生产调度决策方案，具备更先进的生产管理技术，以实现可持续发展的绿色制造过程，提升自身的竞争力。生产调度问题作

2、为生产管理领域被研究的最多的问题之一，在电力产业、石油化工产业、制药业、钢铁产业等制造产业都扮演着十分重要的角色。生产调度是一种决策过程，就是在有限资源和时间的约束下，制定出可以使计划任务目标最优的生产调度策略。有限资源包括生产产品所需的原材料，加工过程中使用的各种机床，机床之间的缓冲区，生产线上的工作人员等等，有限的时间包括制造企业必须在客户要求的交货期内交货，同时还要对客户紧急订单、机器故障等突发事件做出及时的反应和再调度决策。此外，调度问题通常需要考虑多个目标。制造企业考虑的较多的目标有最小化最大完工时间，最大化机器利用率，确保交货期，降低库存和成

3、本等。最近，最小化总碳排放量，机器故障发生的预测准确率等可持续性优化目标也开始引起制造企业的关注。置换流水车间调度问题(PermutationFlowShopSchedulingProblem,PFSSP)是通过对流水线特点的考察，抽取共性，建立的流水车间的一般数学模型。PFSSP主要研究多工件在多机器上按流水线方式加工时的调度决策问题。在实际生产制造系统中存在着大量的流水线，因此对PFSSP的研究具有重要的理论意义和工程价值。在食品加工、化工制药、炼钢连铸等行业的PFSSP中，由于缓冲空间的限制或是加工工艺的要求，相邻两台机器之间的缓冲区可能不存在或者

4、缓冲区大小是有限的，这类PFSSP被称为有限缓冲区流水车间调度问题(Limited-bufferFlowShopSchedulingProblem,LBFSSP)。由于缓冲区大小受到限制会对调度结果产生影响，所以近年来许多学者对LBFSSP进行了研究。1华中科技大学硕士学位论文LBFSSP是组合优化问题，也是典型的NP-hard问题。求解LBFSSP的方法可以分为三类：精确算法，启发式算法和元启发式算法。精确算法主要有分支界定法、动态规划法等，这些方法虽然能找到问题的最优解，但是一般需要很长的计算时间，因此精确算法不适合求解大规模组合优化问题。启发式算法

5、通过直观或经验方法能快速构造出可行解，但是解的质量往往不能令人满意。因此，寻找既能使计算时间尽量短，又能获得待优化问题的最优解或者近似最优解的方法显得尤为重要。元启发式算法如遗传算法、模拟退火和禁忌搜索算法等，由于其在较短时间内能获得较优的满意解，近年来得到了越来越深入的研究，并在许多组合优化问题中得到了广泛的应用。此外，通过模拟自然界现象或者生物生存规律，许多新的元启发式算法不断被提出，这些算法因各自独特的寻优方式，引起了许多研究人员的关注。候鸟优化(MigratingBirdsOptimization,MBO)算法是一种新兴的元启发式算法，该算法对候

6、鸟在迁徙过程中保持V字形飞行编队以减少能量损耗的行为进行模拟。MBO算法是一种基于邻域搜索技术的算法，算法优化思想简单、收敛速度快、鲁棒性好，非常适合求解流水车间调度问题。由于该算法提出时间较短，因此其算法设计和优化效果还有很大的改进和提升空间。本文将候鸟优化算法应用于LBFSSP，设计了单目标候鸟优化算法和多目标候鸟优化算法，深入研究了有限缓冲区流水车间调度问题，通过与不考虑缓冲区约束的PFSSP的结果比较，揭示缓冲区大小对流水车间调度问题的影响，并通过单目标、多目标LBFSSP计算结果分析，显示改进MBO算法的有效性和可行性。1.3流水车间调度问题及

7、其研究现状1.3.1置换流水车间调度问题研究现状[1]自上世纪50年代Johnson等人提出双机置换流水车间调度问题之后，各种求解置换流水车间问题的方法被提出。PFSSP问题最常见的三个优化目标分别是：最大完工时间(Makespan)，总拖期(TotalTardiness)和总流程时间(TotalFlowTime)。在这三个目标下[2-3]的置换流水车间问题均已被证明当机器数大于2时是NP-hard问题。[4]在精确算法方面，Ignall和Schrage设计了一种分支界定法来求解使平均完工时间[5]最小的双机PFSSP和三机PFSSP。Stafford提

8、出一种流水车间调度的混合整数线性规划模型，能求解最大规模为25工件10机器的PF