论文部分内容阅读
随着科技的进步和经济的发展，当今企业之间竞争日益激烈，生产调度问题是企业生产管理的核心和关键，合理有效的调度方案能够提升企业核心竞争力，为企业以及社会带来良好的经济效益。生产调度问题涉及面广、种类多样，包含多约束、多目标、不确定性等。考虑调度问题的不同约束以及不确定性有利于贴近实际制定合理的调度方案，但同时增加了问题的求解难度。这类问题的NP-hard特性决定了即使针对小规模问题，也不存在有限时间内得到最优解的多项式算法。上世纪80年代以来，通过模拟生物进化和种群行为的元启发式算法吸引了国内外学者的广泛关注，这类算法具有搜索效率高、对问题依赖度小的特点，为求解调度问题提供了新的思路。Dan Simon在2008年提出的生物地理学优化算法(Biogeography-Based Optimization，BBO)，是在生物地理学模型迁移规律的基础上，借鉴其他仿生学算法的框架而形成。作为一种新的进化算法，它具有全局搜索能力强、设置参数少、计算简单等特点。本文深入研究了几类带有复杂约束的调度问题，建立相应的调度模型，使用不同的策略改进BBO算法，用于求解调度问题。 本研究主要内容包括：⑴针对混合流水车间调度问题(Hybrid Flow Shop Scheduling Problem，HFSP)，建立混合流水车间调度模型，提出一种变迁移率和突变率的BBO算法(MBBO)。MBBO算法改进了BBO算法的迁移和变异概率模型，以增强算法的全局搜索能力;在生成初始种群时，使用NEH启发式规则生成较优个体，加快算法的收敛速度。通过仿真验证了MBBO算法求解HFSP的有效性。⑵针对产品加工时间不确定条件下带阻塞的流水车间调度问题(Blocking FlowShop Scheduling Problem，BFSP)，采用梯形模糊数描述加工时间的不确定性，根据模糊规划理论，建立了以最小化最大完成时间为目标的模糊调度模型，采用一种改进的BBO算法(IBBO)求解此类问题。IBBO算法在连续多代最优解没有发生改变的情况下，对最优解执行破坏重建的操作，并借鉴模拟退火算法，以一定概率接收劣解，增强算法的全局搜索能力。最后通过仿真实验，并与其他算法进行对比，验证了IBBO算法求解模糊带阻塞流水车间调度问题的有效性。⑶针对加工时间不确定的作业车间调度问题(Job Shop Scheduling Problem，JSP)，采用钟型模糊数描述工件加工时间的不确定性，以模糊规划理论为基础，建立了以最小化最大完成时间为调度目标的模糊调度模型，使用文化BBO算法求解该类问题。文化算法的种群空间采用BBO算法，通过文化算法的双层协同进化模式，增强了BBO算法的搜索性能，并加快了算法的收敛速度。通过仿真对比，验证了文化BBO算法求解模糊作业车间调度问题的优越性。