Preemptive scheduling with availability constraints to minimize total weighted completion times

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

55 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)183-192
Journal / PublicationAnnals of Operations Research
Volume133
Issue number1-4
Publication statusPublished - Jan 2005
Externally publishedYes

Abstract

In this paper we study the problem of scheduling n jobs on a single machine with availability constraints. The objective is to minimize total weighted job completion times. We show that the problem is NP-hard in the strong sense. Then we consider two intractable special cases, namely, proportional weight case, and single availability constraint case. We propose two heuristics for these cases and analyze their worst-case error bounds. © 2005 Springer Science + Business Media, Inc.