Single facility multi-class job scheduling (Q917435)

Considered is the problem of scheduling jobs belonging to different classes on a single facility. Jobs are differentiated on the basis of their set-up times. Further, jobs belonging to the same class may differ from each other by their processing times. The problem is to find a schedule that minimizes mean flow time. The authors propose two approaches. The first, enumerative one, is based on a dynamic programming method. The second, heuristic one, is analyzed from the viewpoint of its worst-case and mean behavior.