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

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

0.00 Avg rating0 Votes
Article ID: iaor20072847
Country: Netherlands
Volume: 105
Issue: 2
Start Page Number: 402
End Page Number: 406
Publication Date: Jan 2007
Journal: International Journal of Production Economics
Authors: , , ,
Keywords: batch size
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(nlogn) time algorithms for the following two special cases: (1) the jobs are inversely agreeable, i.e., pi<pj implies wi≥wj; (2) the batch size is 2 and the weights of the jobs are proportional to their processing times, i.e., wj=αpj for a constant α>0.

Reviews

Required fields are marked *. Your email address will not be published.