Group scheduling with controllable setup and processing times: Minimizing total weighted completion time

Chi To Ng, Edwin Tai Chiu Cheng, Adam Janiak, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

46 Citations (Scopus)

Abstract

The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming.
Original languageEnglish
Pages (from-to)163-174
Number of pages12
JournalAnnals of Operations Research
Volume133
Issue number1-4
DOIs
Publication statusPublished - 1 Jan 2005

Keywords

  • Controllable setup and processing times
  • Group technology
  • Single machine scheduling
  • Total weighted completion time

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Cite this