Optimal semi‐online scheduling algorithms on two parallel identical machines under a grade of service provision

Optimal semi‐online scheduling algorithms on two parallel identical machines under a grade of service provision

0.00 Avg rating0 Votes
Article ID: iaor201110603
Volume: 135
Issue: 1
Start Page Number: 367
End Page Number: 371
Publication Date: Jan 2012
Journal: International Journal of Production Economics
Authors: , ,
Keywords: combinatorial optimization
Abstract:

This paper investigates semi‐online scheduling problems on two parallel identical machines under a grade of service (GoS) provision. We consider two different semi‐online versions where the optimal offline value of the instance is known in advance or the largest processing time of all jobs is known in advance. Respectively for the two semi‐online models, two algorithms with competitive ratios of 3/2 and ( 5 + 1 ) / 2 equ1 are shown to be optimal.

Reviews

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