Details

Autor(en) / Beteiligte

• Cui, Qianna
• Pan, Haiwei

Titel

Online and Semi-Online Vector Scheduling on A Single Machine with Rejection

Ist Teil von

• 2018 IEEE International Conference on Data Mining Workshops (ICDMW), 2018, p.980-985

Ort / Verlag

IEEE

Erscheinungsjahr

2018

Quelle

IEEE Electronic Library Online

Beschreibungen/Notizen

• In this paper, we design an online algorithm for vector scheduling on a single machine with rejection and its competitive ratio is d, where d is the dimensions of vector. In addition, we consider two versions of semi-online vector scheduling on a single machine with rejection. In the first version, semi-online with rearrangement allows at most one job to be reassigned after scheduling all jobs, then we show a semi-online algorithm with competitive ratio 1/2 d+2 for d > 3. The second version is semi-online with rejection buffer whose length= 1, which can hold one job. When d > 3, we also give an algorithm with competitive ratio 1/2 d + 2.