Sensitivity analysis of list scheduling heuristics

DOI10.1016/0166-218X(94)90005-1MaRDI QIDQ1339396zbMATH OpenOpenAlexFDO

Authors Antoon W. J. Kolen, Stan Van Hoesel, Albert P. M. Wagelmans, Alexander H. G. Rinnooy Kan

Publication date 10 October 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(94)90005-1

zbMATH Keywords

heuristicsidentical parallel machineslist scheduling rulesmakespansensitivity analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Review text

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 the processing time is known. This 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 plausible notion that the sensitivity of a list scheduling rule increases with the quality of the schedule produced.

Recommendations

• Probabilistic Bounds on the Performance of List Scheduling
• Sensitivity bounds for machine scheduling with uncertain communication delays
• Sensitivity analysis for scheduling problems
• Sensitivity analysis for scheduling problems
• Sensitivity Analysis for Stochastic Scheduling Problems

Cites work

• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• The Asymptotic Optimality of the LPT Rule

Cited in

(12)

• Stability of a schedule minimizing mean flow time
• A list-scheduling heuristic for the short-term planning of assessment centers
• Sensitivity analysis of a greedy heuristic for knapsack problems
• Constructing the minimization diagram of a two-parameter problem
• Parametric methods in integer linear programming
• Sensitivity analysis of a fuzzy multiobjective scheduling problem
• Sensitivity analysis for some scheduling problems
• Parallel Machine Scheduling with Uncertain Communication Delays
• On robust online scheduling algorithms
• Sensitivity analysis of the unrelated parallel machine scheduling problem with rework processes and machine eligibility restrictions
• Heuristic stability: a permutation disarray measure
• Stability analysis in discrete optimization involving generalized addition operations

This page was built for publication: Sensitivity analysis of list scheduling heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1339396)