NDLI: The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates

Content Provider	Springer Nature Link
Author	Chou, Mabel C. Queyranne, Maurice Simchi Levi, David
Copyright Year	2005
Abstract	Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. According to WSPR, whenever a machine completes a job, the next job assigned to it is the one with the least ratio of processing requirement to weight among all jobs available for processing at this point in time. We analyze the performance of this heuristic and prove that its asymptotic competitive ratio is one for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation of the problem.
Starting Page	137
Ending Page	157
Page Count	21
File Format	PDF
ISSN	00255610
Journal	Mathematical Programming
Volume Number	106
Issue Number	1
e-ISSN	14364646
Language	English
Publisher	Springer-Verlag
Publisher Date	2005-06-07
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Scheduling Asymptotic Performance Ratio On-line algorithms Analysis of Heuristics Mathematics of Computing Numerical Analysis Combinatorics Calculus of Variations and Optimal Control Optimization Mathematical and Computational Physics Mathematical Methods in Physics
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

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

Scheduling uniform machines on-line requires nondecreasing speed ratios

LP-based online scheduling: from single to parallel machines

Machine scheduling with resource dependent processing times

Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

Minimizing average completion time in the presence of release dates

Coordinate descent algorithms

Approximation algorithms for two-machine flow shop scheduling with batch setup times

Algorithms for railway crew management

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates

Similar Documents

Scheduling uniform machines on-line requires nondecreasing speed ratios

LP-based online scheduling: from single to parallel machines

Machine scheduling with resource dependent processing times

Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

Minimizing average completion time in the presence of release dates

Coordinate descent algorithms

Approximation algorithms for two-machine flow shop scheduling with batch setup times

Algorithms for railway crew management

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates