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(nlogn) algorithm which, it is claimed, minimizes the sum of completion times. However, a counter-example is presented 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.
