重入排序问题综述

A review of re-entrant scheduling problems

重入排序问题打破传统假设:工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题.重入的特点源于半导体生产,并广泛存在于其他领域.对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同,对内容和方法进行分类介绍和总结:包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题.最后展望未来的趋势和研究方向.

In contrast to the classical scheduling assumption that each job visits each machine once at most, jobs with reentrant style are of a new type of scheduling problems. The basic characteristic of a re-entrant problem is that a job visits certain machines more than once. Re-entrance is usually found in semiconductor manufacturing, and also many other fields. Recently many papers have dealt with the re-entrant scheduling problems. Results and contributions of these references are presented and analyzed in this paper. The contents and methods are classified and introduced according to the machine environments, including single machine, flow shop, flexible flow shop and others. Research directions and trends of re-entrant scheduling problems in the future are presented at last.