An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)


We consider the m parallel-machine scheduling problem that process service requests from various customers who are entitled to different levels of grade of service (GoS). The objective is to minimize the makespan. We give a fully polynomial-time approximation scheme for the case where m is fixed.
Original languageEnglish
Pages (from-to)171-174
Number of pages4
JournalInformation Processing Letters
Issue number4
Publication statusPublished - 31 Oct 2008


  • Eligibility
  • Grade of service
  • Makespan
  • Scheduling

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this