We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Scheduling Jobs Online on Linear Hierarchical Parallel Machines.
- Authors
Xiao XIN; Min MOU; Guohua MU
- Abstract
A parallel machine scheduling problem is considered in the presence of machine eligibility restrictions. The machines run at the same constant speed but they form a linear hierarchy of capability, i.e., leftward machines are more capable than rightward ones. Jobs arrive online over time at their release times. The processing time of a job will be known immediately upon its arrival. Each job specifies the least capable machine that can process it, and this job can be assigned to any of the machines to the left of this machine (including this machine itself). The jobs must be processed non-preemptively. The objective is to minimize the maximum flow time, where the flow time of a job is defined to be the difference between its release time and completion time. A constant competitive ratio algorithm for the problem is presented. Previously, no such result was known even in the offline setting.
- Subjects
SCHEDULING; LINEAR machines (Electric machines); COMBINATORIAL optimization
- Publication
International Journal of Simulation -- Systems, Science & Technology, 2016, Vol 17, Issue 47, p40.1
- ISSN
1473-8031
- Publication type
Article
- DOI
10.5013/IJSSST.a.17.47.40