Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/8596
Title: Several semi-online scheduling problems on two identical machines with combined information
Authors: Cao, Q
Cheng, TCE 
Wan, G
Li, Y
Keywords: Buffer
Combined information
Identical machines
Scheduling
Semi-online
Issue Date: 2012
Source: Theoretical computer science, 2012, v. 457, p. 35-44 How to cite?
Journal: Theoretical Computer Science 
Abstract: In this paper we consider several semi-online scheduling problems on two identical machines with combined information. The objective of each problem is to minimize the makespan. The first problem is semi-online scheduling with known optimal solution value and maximum job size. We obtain a lower bound 65 and design an optimal algorithm with a competitive ratio 65. The second problem is semi-online scheduling with a buffer of size k, where k(k<1) is a finite positive integer, and known maximum job size. We obtain a lower bound 65 and design an algorithm with a competitive ratio 54. The third problem is semi-online scheduling with a buffer of size 1 and jobs arriving in decreasing order of their processing times. We obtain a lower bound 76, which matches an upper bound in the literature. The last problem is semi-online scheduling with a buffer of size 1 and all the job processing times being bounded in the interval [1,t](t<1). We obtain a lower bound maxmin43,t+26,min54,t+14,min76,t+23, where the lower bound 43 for t<6 matches an upper bound in the literature, and design an algorithm with a competitive ratio maxt+23,87 for 1≤t≤32, which is optimal for 107≤t≤32.
URI: http://hdl.handle.net/10397/8596
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2012.07.005
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

26
Last Week
3
Last month
Checked on May 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.