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

J. J. Yuan, Y. X. Lin, Edwin Tai Chiu Cheng, Chi To Ng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

19 Citations (Scopus)

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., pi< pjimplies wi≥ wj; (2) the batch size is 2 and the weights of the jobs are proportional to their processing times, i.e., wj= α pjfor a constant α > 0.
Original languageEnglish
Pages (from-to)402-406
Number of pages5
JournalInternational Journal of Production Economics
Volume105
Issue number2
DOIs
Publication statusPublished - 1 Feb 2007

Keywords

  • Batch size
  • Batching
  • Scheduling

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this