考虑差异分批的复杂流水车间调度问题及其分布估计算法研究

Traditional flowshop scheduling problems have been examined extensively in the literature. This research considers the complex flowshop scheduling problems with arbitrary job sizes and batch processing machines, which is closer to real production flows and processing characteristics. A complex flowshop is comprised of several processing stages and each stage may comprise several parallel discrete machines or batch processing machines. Jobs have non-identical sizes. Batch processing machines have capacity limitations and a batch processing machine can process a number of jobs simultaneously as a batch. Two kinds of performance measures are considered in our research, including cost-related objectives such as makespan, total completion time etc., and customer satisfaction-related objectives such as earliness/tardiness, number of tardy jobs etc. This research formulates mathematic models for these scheduling problems, and analyses their computational complexity and character theories. Moreover, an estimation of distribution algorithm-based hybrid optimization framework is developed. Regarding the proposed algorithm, this research presents its probabilistic model and updating mechanism, hybrid strategies with other intelligence algorithms, batching heuristics and sequencing heuristics, embedded local search techniques and so on. Computational simulation is employed to demonstrate the effectiveness and efficiency of the proposed hybrid algorithm.

传统的流水车间调度问题已经得到了广泛的研究。本课题主要针对更贴近实际生产过程与加工特性的、考虑差异分批的复杂流水车间调度问题开展研究。复杂流水车间由多个加工阶段组成，每个加工阶段又包含若干台并行的单处理机器或批处理机器，工件的尺寸各不相同，批处理机具有容量限制，批处理机一次能够加工多个工件。我们拟考虑两类不同的评价指标，即考虑制造期、总完工时间等成本相关的优化目标，以及考虑提前/延迟、滞后工件数量等与客户满意度相关的优化目标。本课题拟分别对上述各类问题进行建模，在分析问题的计算复杂度和理论性质基础上，基于分布估计算法设计出一种混合优化算法框架。在提出的混合算法中，本课题将分别探讨概率模型的构建及其更新、与其它智能算法的融合策略、分批算法和调度批算法、嵌入的局部搜索算法等诸多方面，力求使所设计的方法在效率与效果两个方面表现优异性能。

在工业4.0时代，我国提出了《中国制造2025》规划，坚持创新驱动、结构优化、质量为先、绿色发展。为了实现这些规划，必须将先进制造技术引入到工业中去。本课题研究的就是工业中典型的复杂流水车间批调度问题，本课题通过改进智能调度算法来实现复杂流水车间的优化调度。我们为复杂的流水车间调度问题进行建模并且分析了问题的复杂度，考虑到这个问题是NP难问题，我们通过改进分布估计算法、蚁群算法等智能优化算法来解决流水车间调度问题。我们研究了两阶段流水车间上的并行批处理机调度问题，问题的目标是最小化总完工时间，工件动态到达，工件尺寸不等，且允许工件阻塞，工件的安装时间和机器的清洗时间都是常量。为了解决此问题，我们提出了两种混合蚁群优化算法，一种基于工件序列（JHACO）编码，另一种基于批序列（BHACO）编码。我们将max-min信息素限制规则和局部优化规则分别被嵌入到JHACO和BHACO中，以避免算法陷入局部最优。我们提出了模糊蚁群算法，解决工件加工时间不确定的问题。另外，我们还提出了基于量子启发式的蚁群算法，在算法中，所有的蚂蚁被均匀的分成两组，一组选择尺寸最大的工件作为初始工件批，另一组选择尺寸最小的工件作为初始工件批，每组蚂蚁信息素矩阵相对独立。我们又研究了流水车间调度问题中的多目标优化问题，在该问题中，工件动态到达、工件尺寸不等、流水车间由两台并行批处理机器组成、机器速度可变，目标是最小化最大完工时间和能源消耗。我们利用分时电价策略在总能源消耗和总完工时间两个目标之间进行权衡。我们提出了一个多目标混合蚁群算法，我们在该算法中嵌入了最大/最小信息素规则来避免陷入局部最优。实验结果表明，与NSGA-Ⅱ算法相比，在帕累托解的质量、数量和分布上，该算法相对较优，但计算时间更多。我们还进行了分布估计算法的相关研究。我们采用了基于copula函数的分布估计算法来解决两阶段流水车间调度中的资源消耗最小化问题。考虑到文献中相关的进化算法难以表征各种复杂类型的相关性，我们还提出了基于马尔可夫链的方案来改进分布估计算法。我们取得成果的价值主要体现在学术研究和应用方面。首先，在学术研究方面，我们提出的改进的蚁群算法以及分布估计算法相比文献中的算法拥有更好的性能，可以为同侪提供启发。其次，在应用方面，我们改进的算法可以为生产决策者提供更优的调度方案，从而提高生产企业的生产效率。