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

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 are shown to be optimal.

MoreLess

Year of publication:	2012
Authors:	Wu, Yong ; Ji, Min ; Yang, Qifan
Published in:	International Journal of Production Economics. - Elsevier, ISSN 0925-5273. - Vol. 135.2012, 1, p. 367-371
Publisher:	Elsevier
Subject:	Scheduling \| Semi-online \| Grade of service \| Two machines \| Competitive ratio

Online Resource

Check full text access |

More access options

Check Google Scholar

In libraries world-wide (WorldCat)

In German libraries (KVK)

subito order

I need help

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010597256