NDLI: Online scheduling with a buffer on related machines

Content Provider	Springer Nature Link
Author	Dósa, György Epstein, Leah
Copyright Year	2008
Abstract	Online scheduling with a buffer is a semi-online problem which is strongly related to the basic online scheduling problem. Jobs arrive one by one and are to be assigned to parallel machines. A buffer of a fixed capacity K is available for storing at most K input jobs. An arriving job must be either assigned to a machine immediately upon arrival, or it can be stored in the buffer for unlimited time. A stored job which is removed from the buffer (possibly, in order to allocate a space in the buffer for a new job) must be assigned immediately as well. We study the case of two uniformly related machines of speed ratio s≥1, with the goal of makespan minimization.Two natural questions can be asked. The first question is whether this model is different from standard online scheduling, that is, is any size of buffer K>0 already helpful to the algorithm, compared to the case K=0. The second question is whether there exists a constant K, so that a larger buffer is no longer beneficial to an algorithm, that is, increasing the size of the buffer above this threshold would not change the best competitive ratio further. Previous work (Kellerer et al., Oper. Res. Lett. 21, 235–242, 1997; Zhang, Inf. Process. Lett. 61, 145–148, 1997; Englert et al., Proc. 48th Symp. Foundations of Computer Science (FOCS), 2008) shows that in the case s=1, already K=1 allows to design a $\frac{4}{3}$ -competitive algorithm, which is best possible for any K≥1, whereas the best possible ratio for K=0 is $\frac{3}{2}$ . Similar results have been show for multiple identical machines (Englert et al., Proc. 48th Symp. Foundations of Computer Science (FOCS), 2008).We answer both questions affirmatively, and show that a buffer of size K=2 is sufficient to achieve the a competitive ratio which matches the lower bound for K→∞ for any s>1. In fact, we show that a buffer of size K=1 can evidently be exploited by the algorithm for any s>1, but for a range of values of s, it is still weaker than a buffer of size 2. On the other hand, in the case s≥2, a buffer of size K=1 already allows to achieve optimal bounds.
Starting Page	161
Ending Page	179
Page Count	19
File Format	PDF
ISSN	13826905
Journal	Journal of Combinatorial Optimization
Volume Number	20
Issue Number	2
e-ISSN	15732886
Language	English
Publisher	Springer US
Publisher Date	2008-12-10
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Semi-online algorithms Scheduling Uniformly related machines Operations Research/Decision Theory Optimization Theory of Computation Mathematical Modeling and Industrial Mathematics Convex and Discrete Geometry Combinatorics
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization Discrete Mathematics and Combinatorics Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Semi-online scheduling with “end of sequence” information

Semi-online scheduling on two identical machines with rejection

Semi-online scheduling with known maximum job size on two uniform machines

Semi-online scheduling on two uniform machines with the known largest size

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

Semi-online scheduling with combined information on two identical machines in parallel

The hierarchical model for load balancing on two machines

Optimal online algorithms on two hierarchical machines with tightly-grouped processing times

Online LPT algorithms for parallel machines scheduling with a single server

Online scheduling with a buffer on related machines

Similar Documents

Semi-online scheduling with “end of sequence” information

Semi-online scheduling on two identical machines with rejection

Semi-online scheduling with known maximum job size on two uniform machines

Semi-online scheduling on two uniform machines with the known largest size

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

Semi-online scheduling with combined information on two identical machines in parallel

The hierarchical model for load balancing on two machines

Optimal online algorithms on two hierarchical machines with tightly-grouped processing times

Online LPT algorithms for parallel machines scheduling with a single server

Online scheduling with a buffer on related machines