Preemptive scheduling with availability constraints to minimize total weighted completion times

Preemptive scheduling with availability constraints to minimize total weighted completion times

0.00 Avg rating0 Votes
Article ID: iaor20052123
Country: Netherlands
Volume: 133
Issue: 1
Start Page Number: 183
End Page Number: 192
Publication Date: Jan 2005
Journal: Annals of Operations Research
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.