SAGA算法在差异工件平行机批调度问题中的应用研究(1)

《SAGA算法在差异工件平行机批调度问题中的应用研究(1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要摘要调度问题是组合优化领域中一类重要的问题，它广泛地应用在制造业、现代物流和网络通信等领域，本文主要研究的是生产调度问题，有效的调度能够提高机器利用率、降低成本、增加利润和提升客户满意度。本文的研究目标是最小化差异工件平行机批调度问题的制造时间跨度Cmax，在调度问题的研究中，Cmax经常被用来衡量调度的性能，与差异工件单机批调度问题相比，差异工件平行机批调度问题更接近现实生产活动，而且目前关于该问题的研究仍然较少。本文首先简述了调度问题的概念、研究意义、分类和参数表示、经典调度与现代调度的区别以及差异工件批调度问题的概念。同时，我们也简单介绍了组合优化问题的概念与

2、计算复杂性的相关基础知识。由于差异工件批调度问题是一类典型的NP-hard问题，所以解决该类问题的关键在于寻求有效的优化算法。目前，求解差异工件批调度问题的主要方法有两种：（1）数学规划方法；（2）启发式方法。前者虽然可以求得问题的最优解，但是只适用在小规模问题中，后者虽然在大多数情况下不能得到最优解，但是它能有效地解决大规模问题，在一定时间内给出一个在可以接受范围内的近似最优解，具有更强的实际可操作性。本文介绍了目前求解差异工件批调度问题的主要的数学规划方法和启发式方法及其研究情况。根据问题的特性，本文设计了一种面向差异工件平行机批调度问题的模拟退火遗传算法（Simu

3、latedAnnealingGeneticAlgorithm，SAGA）。SAGA算法集合了模拟退火算法（SimulatedAnnealing，SA）和遗传算法（GeneticAlgorithm，GA）在局部搜索与全局搜索能力方面的优势，并改进了遗传算法的交叉方式和适应函数的标定方式。仿真实验表明，SAGA算法的性能优于现有文献中的两个经典启发式规则FFLPT和BFLPT以及GA算法。最后，我们总结了本文的主要工作和创新点，并提出了未来可以继续进行研究的方向。关键词：调度差异工件批处理机模拟退火遗传算法组合优化IAbstractABSTRACTSchedulingiso

4、neofthemostimportantcombinatorialoptimizationproblems.Itiswidelyappliedinmanufacturing,modernlogistics,networkcommunicationandotherfields,thispapermainlystudiesproductionschedulingproblem,effectiveschedulingoperationcanimprovetheutilizationofmachines,reducethecosts,increasetheprofitsandi

5、mprovecustomers’satisfaction.Minimizingmakespanonparallelbatchingmachineswithnon-identicaljobsizesistheaimofthispaper,makespanisusuallyusedtomeasuretheperformanceofschedulingoperationintheresearchofschedulingproblem,comparedwithsinglebatchingprocessingmachineschedulingproblemswithnon-ide

6、nticaljobsizes,schedulingonparallelbatchingprocessingmachinewithnon-identicaljobsizesismorewidelyusedinindustrialproduction,andsofar,therearelessresearchesonthisproblem.Atfirst,theconceptofschedulingproblem,significanceoftheresearch,classificationandparameterrepresentationoftheproblem,th

7、edifferencesbetweenclassicschedulingproblemandmodernschedulingproblemandtheconceptofschedulingbatchingmachineswithnon-identicaljobsizeswereintroduced.Atthesametime,wealsosimplyintroducedtheconceptofcombinatorialoptimizationproblemandtherelatedbasicknowledgeofcomputational