Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time [An article from: International Journal of Production Economics]

This digital document is a journal article from International Journal of Production Economics, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
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(nlogn) time algorithms for the following two special cases: (1) the jobs are inversely agreeable, i.e., p"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=@ap"j for a constant @a>0.