改进区块遗传算法解决分布式车间调度问题

裴小兵，孙志卫

（天津理工大学 管理学院，天津 300384）

随着生产全球化和制造规模化，大型制造企业为降低成本、提高生产柔性与生产效率以快速满足全球市场需求，生产方式正由集中性单车间生产向分布式车间生产转变。但是相关文献研究还主要集中在单个车间生产调度[1]。近年来，分布式车间调度问题(distributed job-shop scheduling problem，DJSP)在车间调度研究领域逐渐受到关注，如对关键路径的二车间综合调度问题[2]、分布式流程车间问题[3]、多工序同时结束的多车间逆序综合调度[4]和分布式工作车间问题[5-6]等。

经典的单车间调度问题[7](job-shop scheduling problem, JSP)中所有的工件都在同一车间内加工完成的，DJSP是将工件分配到更多的车间共同加工完成。DJSP是对JSP的扩展，结合了工件在分布式车间的分配和单个车间内调度两种问题，并且允许任何一个车间拥有加工完成任何一个工件的能力。

由于分布式车间调度需要考虑分配和排序两个阶段，因而DJSP更加复杂[8]：第一阶段将待加工的零件分配到f家车间中；第二阶段对已经分配到同一车间的工件进行排序(即单个车间调度问题)。第一阶段的工件分配很大程度上决定了多车间之间的工作量协同程度，对算法的结果具有至关重要的影响。为了更好地解决DJSP，Wagner[9]提出了DJSP模型，经过不断的改进能够准确地描述出分布式工作车间调度问题的特征，该模型的建立对求解DJSP具有重要意义。在该数学模型被提出之前，研究者一般使用标准遗传算法来解决分布式车间调度问题[10]，之后的研究也是在标准遗传算法的基础上进行的局部改进，以解决中小规模的分布式车间调度问题[11]。……