谢志强，郑付萍，朱天浩，周含笑

(哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080)

1 概述

产品制造调度问题是NP难问题[1]，目标是在满足约束条件的前提下，使产品的加工时间尽可能少。以往对大批量相同产品采用流水线方式生产制造的调度方法主要是纯加工调度[2-3]和纯装配调度[4-5]，但随着社会对产品多样化的需求，多产品小批量的生产计划越来越多。对多品种小批量产品，特别是单件复杂产品，如果按以往先加工后装配的方式制造，必然要割裂产品内在的加工与装配的并行关系，文献[6]提出产品制造的第3种调度方式：加工和装配一同处理的综合调度。随着综合调度研究的深入，目前有关综合调度的研究已解决了一般综合调度问题[7]、工序间存在特殊约束关系[8]、柔性产品[9]、存在相同设备[10]和存在批处理设备[11]等的综合调度问题，但所解决的综合调度问题仅限于设备资源在单车间的情况，目前还无人考虑单件复杂产品在相同设备资源两车间制造的分布式综合调度的实际问题。

对于单件复杂产品在两车间分布式制造的调度问题，主要的研究目标是设计使产品尽早完成的调度方案。为了使产品尽早完成，需要解决以下问题：(1)两车间充分并行处理，即让两车间工序加工的时间差尽量小；(2)工序在两车间移动的次数尽量少。

对于问题(1)，考虑到叶节点工序为可同时加工工序[12]，即叶节点工序可充分并行处理，本文首先将原始叶节点工序成批调度处理，再将每次动态生成的叶节点工序分批处理，即可调度工序分批处理。……