Single facility scheduling with multiple job classes (Q1105481)

The one-machine scheduling problem aiming at minimizing the mean flow time is considered. The jobs set is divided into K classes. The processing of a job from class s immediately after the processing of a job from class r requires switching time \(\alpha_{rs}>0\) \((\alpha_{rr}=0)\). A heuristic \(O(nK+n\) log n) algorithm is proposed, where n is the number of jobs. The author failed to establish the worst- case bound for the algorithm. The results of numerical experiments are reported.