SCHEDULING PARALLEL MACHINES ONLINE

The problem of scheduling jobs on parallel machines is studied when (1 ) the existence of a job is not known until its unknown release date a nd (2) the processing requirement of a job is not known until the job is processed to completion. Two general algorithmic techniques are dem onstrated for converting existing polynomial-time algorithms that requ ire complete knowledge about the input data into algorithms that need less advance knowledge. Information-theoretic lower bounds an the leng th of on-line schedules are proven for several basic parallel machine models, and almost all of our algorithms construct schedules with leng ths that either match or come within a constant factor of the lower bo und.