SCHEDULING 2 JOB CLASSES ON A SINGLE-MACHINE

The problem of scheduling n jobs on a single machine is considered, where the jobs are partitioned into two classes and a set-up time is necessary between jobs of different classes. Gupta proposes an O(n log n) algorithm which, he claims, minimizes the sum of completion times. However, we present a counter-example which shows it can fail to generate an optimal schedule. Nevertheless, this problem is solvable in O(n2) time by a well-known dynamic programming algorithm. An O(n3) dynamic programming algorithm to minimize the sum of weighted completion times is also derived.