We consider the following online appointment scheduling problem: Jobs of different processing times and weights arrive online step-by-step. Upon arrival of a job, its (future) starting date has to be determined immediately and irrevocably before the next job arrives, with the objective of minimizing the average weighted completion time. In this type of scheduling problem it is impossible to achieve non-trivial competitive ratios in the classical, adversarial arrival model, even if jobs have unit processing times. We weaken the adversary and consider random order of arrival instead. In this model the adversary defines the weight processing time pairs for all jobs, but the order in which the jobs arrive online is a permutation drawn uniformly at random.
For the case of jobs with unit processing time we give a constant competitive algorithm. We use this algorithm as a building block for the general case of variable job processing times and achieve competitive ratio
). We complement these algorithms with a lower bound of Ω(n) for unit-processing time jobs in the adversarial input model.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten