Lower bounds for Smith's rule in stochastic machine scheduling

Caroline Jagtenberg, Uwe Schwiegelshohn, Marc Jochen Uetz

Research output: Book/ReportReportProfessional

75 Downloads (Pure)

Abstract

We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan [5] showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of ${1\over 2}(1+\sqrt{2}) \approx 1.207$. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show,somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.229. This constitutes the first lower bound for WSEPT in this setting, and in particular, it shows that even with exponentially distributed processing times, stochastic scheduling has somewhat nastier worst-case examples than deterministic scheduling. In that respect, our analysis sheds new light on the fundamental differences between deterministic and stochastic scheduling.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages12
Publication statusPublished - Jul 2010

Publication series

NameCTIT Technical Report Series
PublisherUniversity of Twente, Centre for Telematics and Information Technology
No.TR-CTIT-10-30
ISSN (Print)1381-3625

Keywords

  • Exponential distribution
  • METIS-270930
  • EWI-18185
  • Stochastic Scheduling
  • IR-72807
  • WSEPT

Cite this

Jagtenberg, C., Schwiegelshohn, U., & Uetz, M. J. (2010). Lower bounds for Smith's rule in stochastic machine scheduling. (CTIT Technical Report Series; No. TR-CTIT-10-30). Enschede: Centre for Telematics and Information Technology (CTIT).
Jagtenberg, Caroline ; Schwiegelshohn, Uwe ; Uetz, Marc Jochen. / Lower bounds for Smith's rule in stochastic machine scheduling. Enschede : Centre for Telematics and Information Technology (CTIT), 2010. 12 p. (CTIT Technical Report Series; TR-CTIT-10-30).
@book{cc402d19a8b34468802de2f85803cb43,
title = "Lower bounds for Smith's rule in stochastic machine scheduling",
abstract = "We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan [5] showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of ${1\over 2}(1+\sqrt{2}) \approx 1.207$. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show,somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.229. This constitutes the first lower bound for WSEPT in this setting, and in particular, it shows that even with exponentially distributed processing times, stochastic scheduling has somewhat nastier worst-case examples than deterministic scheduling. In that respect, our analysis sheds new light on the fundamental differences between deterministic and stochastic scheduling.",
keywords = "Exponential distribution, METIS-270930, EWI-18185, Stochastic Scheduling, IR-72807, WSEPT",
author = "Caroline Jagtenberg and Uwe Schwiegelshohn and Uetz, {Marc Jochen}",
year = "2010",
month = "7",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "TR-CTIT-10-30",
address = "Netherlands",

}

Jagtenberg, C, Schwiegelshohn, U & Uetz, MJ 2010, Lower bounds for Smith's rule in stochastic machine scheduling. CTIT Technical Report Series, no. TR-CTIT-10-30, Centre for Telematics and Information Technology (CTIT), Enschede.

Lower bounds for Smith's rule in stochastic machine scheduling. / Jagtenberg, Caroline; Schwiegelshohn, Uwe; Uetz, Marc Jochen.

Enschede : Centre for Telematics and Information Technology (CTIT), 2010. 12 p. (CTIT Technical Report Series; No. TR-CTIT-10-30).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Lower bounds for Smith's rule in stochastic machine scheduling

AU - Jagtenberg, Caroline

AU - Schwiegelshohn, Uwe

AU - Uetz, Marc Jochen

PY - 2010/7

Y1 - 2010/7

N2 - We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan [5] showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of ${1\over 2}(1+\sqrt{2}) \approx 1.207$. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show,somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.229. This constitutes the first lower bound for WSEPT in this setting, and in particular, it shows that even with exponentially distributed processing times, stochastic scheduling has somewhat nastier worst-case examples than deterministic scheduling. In that respect, our analysis sheds new light on the fundamental differences between deterministic and stochastic scheduling.

AB - We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan [5] showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of ${1\over 2}(1+\sqrt{2}) \approx 1.207$. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show,somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.229. This constitutes the first lower bound for WSEPT in this setting, and in particular, it shows that even with exponentially distributed processing times, stochastic scheduling has somewhat nastier worst-case examples than deterministic scheduling. In that respect, our analysis sheds new light on the fundamental differences between deterministic and stochastic scheduling.

KW - Exponential distribution

KW - METIS-270930

KW - EWI-18185

KW - Stochastic Scheduling

KW - IR-72807

KW - WSEPT

M3 - Report

T3 - CTIT Technical Report Series

BT - Lower bounds for Smith's rule in stochastic machine scheduling

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

Jagtenberg C, Schwiegelshohn U, Uetz MJ. Lower bounds for Smith's rule in stochastic machine scheduling. Enschede: Centre for Telematics and Information Technology (CTIT), 2010. 12 p. (CTIT Technical Report Series; TR-CTIT-10-30).