NDLI: Minimizing average completion time in the presence of release dates

Content Provider	Springer Nature Link
Author	Phillips, Cynthia Stein, Clifford Wein, Joel
Copyright Year	1998
Abstract	A natural and basic problem in scheduling theory is to provide good average quality of service to a stream of jobs that arrive over time. In this paper we consider the problem of schedulingn jobs that are released over time in order to minimize the average completion time of the set of jobs. In contrast to the problem of minimizing average completion time when all jobs are available at time 0, all the problems that we consider are NP-hard, and essentially nothing was known about constructing good approximations in polynomial time. We give the first constant-factor approximation algorithms for several variants of the single and parallel machine models. Many of the algorithms are based on interesting algorithmic and structural relationships between preemptive and nonpreemptive schedules and linear programming relaxations of both. Many of the algorithms generalize to the minimization of averageweighted completion time as well. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Starting Page	199
Ending Page	223
Page Count	25
File Format	PDF
ISSN	00255610
Journal	Mathematical Programming
Volume Number	82
Issue Number	1-2
e-ISSN	14364646
Language	English
Publisher	Springer-Verlag
Publisher Date	1998-01-01
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Scheduling Preemptive scheduling Average weighted completion time Approximation algorithms Relaxations Linear programming Mathematics of Computing Numerical Analysis Combinatorics Calculus of Variations and Optimal Control Optimization Mathematical and Computational Physics Mathematical Methods in Physics Numerical and Computational Methods Operation Research/Decision Theory
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

Minimizing Average Completion Time in the Presence of Release Dates (1995)

Approximability of average completion time scheduling on unrelated machines

The constrained minimum weighted sum of job completion times problem

Approximability of flow shop scheduling

Preemptive and non-preemptive generalized min sum set cover

Scheduling uniform machines on-line requires nondecreasing speed ratios

Minimizing Average Completion Time in the Presence of Release Dates (1996)

Scheduling by positional completion times: Analysis of a two-stage flow shop problem with a batching machine

On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates (0)

Minimizing average completion time in the presence of release dates

Similar Documents

Minimizing Average Completion Time in the Presence of Release Dates (1995)

Approximability of average completion time scheduling on unrelated machines

The constrained minimum weighted sum of job completion times problem

Approximability of flow shop scheduling

Preemptive and non-preemptive generalized min sum set cover

Scheduling uniform machines on-line requires nondecreasing speed ratios

Minimizing Average Completion Time in the Presence of Release Dates (1996)

Scheduling by positional completion times: Analysis of a two-stage flow shop problem with a batching machine

On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates (0)

Minimizing average completion time in the presence of release dates