A New Heuristic for a Single Machine Scheduling Problem with Set-up Times
研究单机调度问题，其中作业分属不同类别，切换类别需设置时间。基于已知必要条件提出多项式时间启发式算法，并与现有算法比较性能。
This paper examines the problem of scheduling jobs on a single machine with set-up times. The jobs are divided into mutually exclusive classes and a set-up task is required when processing switches from a job of one class to a job of another class. The set-up times are assumed to be sequence independent. A number of necessary conditions for a schedule to minimize mean flow time have previously been stated, but do not uniquely define the optimal solution, and the problem is apparently NP-complete. We propose a new polynomial-time heuristic, based on these conditions, and compare its performance with some existing heuristics.