Online Preemptive Hierarchical Scheduling on Two Uniform Machines with Rejection

Xiao Min (), Jing Liu (), Yanxia Dong () and Ming Jiang ()
Additional contact information
Xiao Min: College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing 314001, P. R. China
Jing Liu: College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing 314001, P. R. China
Yanxia Dong: College of Mathematics, Shanghai University, Shanghai 200444, P. R. China
Ming Jiang: College of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 04, 1-15

Abstract: This paper studies the online hierarchical scheduling problem on two uniform machines with rejection. Two uniform machines M1, M2 run at the speeds of s ∈ (0, +∞), 1 separately; and they are provided with different capabilities. Each machine has a certain GOS level 1 or 2 and every job is also associated with a hierarchy 1 or 2. The job can only be assigned to the machine whose GOS level does not exceed the job's hierarchy. Preemption is permitted but idle is not introduced. Jobs come one by one over list. When a job arrives, it can be accepted and scheduled on some machine or rejected by paying its penalty. The objective is to minimize the sum of makespan yielded by accepted jobs and total penalties of all rejected jobs. For this problem, we propose a family of several online algorithms according to the range of s and the related lower bound is also obtained. These algorithms achieve optimal competitive ratio when s ∈ (0, 1) ∪ [1.618, +∞), but have a small gap between upper bound and lower bound in interval [1, 1.618).

Keywords: Scheduling; uniform machines; preemption; hierarchy; rejection (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021759591550027X
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:32:y:2015:i:04:n:s021759591550027x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021759591550027X

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().