Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time

Abstract In this paper we consider the single machine serial-batching scheduling problem to minimize total weighted completion time with the restriction that each batch contains exactly k jobs. We show that this problem is strongly NP-hard even when the batch size is 3 and the weight of each job is equal to its processing time. We also give O ( n log n ) time algorithms for the following two special cases: (1) the jobs are inversely agreeable, i.e., p i p j implies w i ⩾ w j ; (2) the batch size is 2 and the weights of the jobs are proportional to their processing times, i.e., w j = α p j for a constant α > 0 .