Sensitivity analysis of list scheduling heuristics

A.W.J. Kolen, A.H.G. Rinnooy Kan, C.P.M. Hoesel, van, A.P.M. Wagelmans

    Research output: Book/ReportReportAcademic

    39 Downloads (Pure)

    Abstract

    When jobs have to be processed on a set of identical parallel machines so as to minimize the makespan of the schedule, list scheduling rules form a popular class of heuristics. The order in which jobs appear on the list is assumed here to be determined by the relative size of their processing times; well known special cases are the LPT rule and the SPT rule, in which the jobs are ordered according to non-increasing and non-decreasing processing time respectively. When all processing times are exactly known, a given list scheduling rule will generate a unique assignment of jobs to machines. However, when there exists a priori uncertainty with respect to one of the processing times, then there will be, in general, several possibilities for the assignment that will be generated once that processing time is known. That number of possible assignments may be viewed as a measure of the sensitivity of the list scheduling rule that is applied. We derive bounds on the maximum number of possible assignments for several list scheduling heuristics, and we also study the makespan associated with these assignments. In this way we obtain analytical support for the intuitively plausible notion that the sensitivity of a list scheduling rule increases with the quality of the schedule produced. Key words: sensitivity analysis, list scheduling, heuristics, robustness, scheduling.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages21
    Publication statusPublished - 1993

    Publication series

    NameMemorandum COSOR
    Volume9310
    ISSN (Print)0926-4493

    Fingerprint Dive into the research topics of 'Sensitivity analysis of list scheduling heuristics'. Together they form a unique fingerprint.

    Cite this