Approximation in stochastic scheduling: The power of LP-based priority policies

dc.contributor.authorMöhring, Rolf H.
dc.contributor.authorSchulz, Andreas S.
dc.contributor.authorUetz, Marc
dc.date.accessioned2021-12-17T10:11:48Z
dc.date.available2021-12-17T10:11:48Z
dc.date.issued1998
dc.description.abstractWe consider the problem to minimize the total weighted completion time of a set of jobs with individual release dates which have to be scheduled on identical parallel machines. Job processing times are not known in advance, they are realized on-line according to given probability distributions. The aim is to find a scheduling policy that minimizes the objective in expectation. Motivated by the success of LP-based approaches to deterministic scheduling, we present a polyhedral relaxation of the performance space of stochastic parallel machine scheduling. This relaxation extends earlier relaxations that have been used, among others, by Hall, Schulz, Shmoys, and Wein (1997) in the deterministic setting. We then derive constant performance guarantees for priority policies which are guided by optimum LP solutions, and thereby generalize previous results from deterministic scheduling. In the absence of release dates, the LP-based analysis also yields an additive performance guarantee for the WSEPT rule which implies both a worst-case performance ratio and a result on its asymptotic optimality, thus complementing previous work by Weiss (1990). The corresponding LP lower bound generalizes a previous lower bound from deterministic scheduling due to Eastman, Even, and Isaacs (1964), and exhibits a relation between parallel machine problems and corresponding problems with only one fast single machine. Finally, we show that all employed LPs can be solved in polynomial time by purely combinatorial algorithms.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15794
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14567
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherstochastic schedulingen
dc.subject.otherapproximationen
dc.subject.otherworst-case performanceen
dc.subject.otherpriority policyen
dc.subject.otherLP-relaxationen
dc.subject.otherWSEPT ruleen
dc.subject.otherasymptotic optimalityen
dc.titleApproximation in stochastic scheduling: The power of LP-based priority policiesen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1998, 595en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-595-1998.pdf
Size:
105.37 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-595-1998.ps.gz
Size:
80.63 KB
Format:
Unknown data format

Collections