相关工件车间调度问题的拓扑算法  

Topology algorithm for job shop scheduling problem with correlative operations

作　　者：张淑丽[1] 刘胜辉[1] 

机构地区：[1]哈尔滨理工大学软件学院,哈尔滨150040

出　　处：《计算机工程与应用》2013年第3期251-254,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.69984002)

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]