Sensitivity Analysis of List Scheduling Heuristics
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;...
| Main Authors: | , , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5268 |
| _version_ | 1811086690323791872 |
|---|---|
| author | Kolen, A.W. J. Rinnooy Kan, A. H. G. Van Hoesel, C. P. M. Wagelmans, Albert |
| author_facet | Kolen, A.W. J. Rinnooy Kan, A. H. G. Van Hoesel, C. P. M. Wagelmans, Albert |
| author_sort | Kolen, A.W. J. |
| collection | MIT |
| description | 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 one of the job processing times is gradually increased, the schedule produced by a list scheduling rule will be affected in a manner reflecting its sensitivity to data perturbations. We analyze this phenomenon and obtain analytical support for the intuitively plausible notion that the sensitivity of a list scheduling rule increases with the quality of the schedule produced. |
| first_indexed | 2024-09-23T13:30:32Z |
| format | Working Paper |
| id | mit-1721.1/5268 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:30:32Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52682019-04-10T15:18:23Z Sensitivity Analysis of List Scheduling Heuristics Kolen, A.W. J. Rinnooy Kan, A. H. G. Van Hoesel, C. P. M. Wagelmans, Albert 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 one of the job processing times is gradually increased, the schedule produced by a list scheduling rule will be affected in a manner reflecting its sensitivity to data perturbations. We analyze this phenomenon and obtain analytical support for the intuitively plausible notion that the sensitivity of a list scheduling rule increases with the quality of the schedule produced. 2004-05-28T19:30:56Z 2004-05-28T19:30:56Z 1990-10 Working Paper http://hdl.handle.net/1721.1/5268 en_US Operations Research Center Working Paper;OR 229-90 1744 bytes 1241011 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Kolen, A.W. J. Rinnooy Kan, A. H. G. Van Hoesel, C. P. M. Wagelmans, Albert Sensitivity Analysis of List Scheduling Heuristics |
| title | Sensitivity Analysis of List Scheduling Heuristics |
| title_full | Sensitivity Analysis of List Scheduling Heuristics |
| title_fullStr | Sensitivity Analysis of List Scheduling Heuristics |
| title_full_unstemmed | Sensitivity Analysis of List Scheduling Heuristics |
| title_short | Sensitivity Analysis of List Scheduling Heuristics |
| title_sort | sensitivity analysis of list scheduling heuristics |
| url | http://hdl.handle.net/1721.1/5268 |
| work_keys_str_mv | AT kolenawj sensitivityanalysisoflistschedulingheuristics AT rinnooykanahg sensitivityanalysisoflistschedulingheuristics AT vanhoeselcpm sensitivityanalysisoflistschedulingheuristics AT wagelmansalbert sensitivityanalysisoflistschedulingheuristics |