A note on on-line scheduling with partial information

✍ Scribed by Guochuan Zhang; Deshi Ye

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 411 KB
• Volume: 44
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(02)00168-2

✦ Synopsis

we consider a variant of on-line scheduling, where partial information on future jobs is known beforehand. Assume that the last job will be the longest (with the longest execution time). We provide the beat possible on-line algorithms with competitive ratios /z and 3/2, respectively, for m = 2 and 3, where m is the number of machines.