Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time

Chou Jung Hsu, Edwin Tai Chiu Cheng, Dar Li Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

41 Citations (Scopus)

Abstract

Zhao et al. (2009) [24] study the m identical parallel-machine scheduling problem with rate-modifying activities to minimize the total completion time. They show that the problem can be solved in O(n2m+3) time. In this study we extend the scheduling environment to the unrelated parallel-machine setting and present a more efficient algorithm to solve the extended problem. For the cases where the rate-modifying rate is (i) larger than 0 and not larger than 1, and (ii) larger than 0, we show that the problem can be solved in O(nm+3) and O(n2m+2) time, respectively.
Original languageEnglish
Pages (from-to)4799-4803
Number of pages5
JournalInformation Sciences
Volume181
Issue number20
DOIs
Publication statusPublished - 15 Oct 2011

Keywords

  • Rate-modifying activity
  • Scheduling
  • Total completion time
  • Unrelated parallel machines

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Cite this