Abstract: According to the characteristics of the actual production in discrete manufacturing assembly enterprises, a new class of job shop scheduling problem is proposed. It is called job shop scheduling problem with correlative operations. Job shop scheduling problem with correlative operations can express the partial order which is processing constraint among jobs and operations. In order to use existing algorithms for traditional job shop scheduling problem with a linear order to solve job shop scheduling problem with correlative operations, a topology algorithm for job shop scheduling problem with correlative operations is designed. The topology algorithm can change the partial order of the operations of a job to a linear order; promptly change the job shop scheduling problem with correlative operations to a traditional job shop scheduling problem. The feasibility and efficiency of the topology algorithm are verified through examples.

Key words: job shop scheduling, collaborative relationship, correlative operations, topology algorithm

摘要： 针对加工装配型离散制造企业实际生产的特点，提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题，设计了一种拓扑算法，该算法能够将工序之间的偏序关系转化为线序关系，将相关工件车间调度问题转化为传统的车间调度问题，通过实证研究，结果表明了拓扑算法是可行和高效的。

关键词: 车间调度, 协作关系, 相关工件, 拓扑算法