Answer to Question #30045 in Quantitative Methods for LaurenC

Question

One machine can process at most one job at a time. The jobs
are of diferent durations, all in the range (0,1] (after suitable scaling). A job,
once started must be completed without interruption. All jobs are available
at time t = 0. The time (half-)line ft : t ¸ 0g is composed of intervals of
length 2: [0,2), [2,4), [4,6). We recall that [4,6), for example, is the set
ft : 4 · t < 6g. Each interval is divided into an active region when jobs may
be started and a passive region when jobs, already started may be completed
but no new jobs may be commenced. The active regions are: [0,1], [2,3], [4,5],
The passive regions are: (1,2), (3,4), (5,6). Thus, for example, if a job
of duration 0.6, say, starts at t = 2:7 and thus finishes at t = 3:3, the machine
must remain idle until time 4. That is, the next job can commence at t = 4
but not for any t such that 3:3 · t < 4.

Suppose that we are given the following eight jobs with durations
f0:45; 0:58; 0:8; 0:2; 0:15; 0:1; 0:5; 0:7g. Is it possible to complete these jobs us-
ing two intervals only?