Open AccessNote—A Note on Single Machine Sequencing with Random Processing Times
Author(s) -
Thom J. Hodgson
Publication year - 1977
Publication title -
management science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 4.954
H-Index - 255
eISSN - 1526-5501
pISSN - 0025-1909
DOI - 10.1287/mnsc.23.10.1144
Subject(s) - deferral , single machine scheduling , computer science , scheduling (production processes) , mathematical optimization , random variable , algorithm , mathematics , job shop scheduling , statistics , economics , finance , schedule , operating system
It is shown that Lawler's efficient (order n 2) algorithm for the n-job, one-machine scheduling problem (where the objective is to minimize the maximum deferral cost subject to arbitrary precedence relationships) also applies when the processing times are random variables and the objective is to minimize the maximum expected deferral cost. Several special cases are explored.