A posterior competitiveness for list scheduling algorithm on machines with eligibility constraints

Abstract

We consider the on-line problem of scheduling n independent jobs on m identical machines under the machine eligibility constraints, where each job has its own specified subset of machines which are eligible for processing it. We investigate a greedy algorithm LS and prove its posterior competitiveness ratio is log(2) 4/lambdam - 1/lambda, where lambda is the number of machines eligible for processing the job with the latest completion time.