search engine gogoog needs to do a serious amount of computation every time it recompiles its index. the company has a single large supercomputer, together with an unlimited supply of high-end pcs. the overall computation is broken into n distinct jobs, labeled j1, j2, . . . , jn, which can be performed completely independently of one another. each job consists of two stages: first it needs to be preprocessed on the supercomputer, and then it needs to be finished on one of the pcs. job ji needs pi seconds of time on the supercomputer, followed by fi seconds of time on a pc. since there are at least n pcs available on the premises, the finishing of the jobs can be performed fully in parallel. however, the supercomputer can only work on a single job at a time, so the system managers need to work out an order in which to feed the jobs to the supercomputer. as soon as the first job in order is done on the supercomputer, it can be handed off to a pc for finishing; at that point in time a second job can be fed to the supercomputer.