Question 3.79

49. A photocopy shop must schedule independent batches of documents to be copied. The times for the different sets of documents are (in minutes) 12, 23, 32, 13, 24, 45, 23, 23, 14, 21, 34, 53, 18, 63, 47, 25, 74, 23, 43, 43, 16, 16, 76.

  1. Construct a schedule using the list-processing algorithm on three machines.
  2. Construct a schedule using the list-processing algorithm on four machines.
  3. Repeat parts (a) and (b), but use the decreasing-time-list algorithm.
  4. Suppose union regulations require that an 8-minute rest period be allowed for any photocopy task over 45 minutes. Use the decreasing-time-list algorithm, with the preceding times modified to take into account the union requirement, to schedule the tasks on three human-operated machines.

49.

(a) Processor 1: 12, 13, 45, 34, 63, 43, 16, idle 226 to 298; Processor 2: 23, 24, 23, 53, 25, 74, 76; Processor 3: 32, 23, 14, 21, 18, 47, 23, 43, 16, idle 237 to 298

(b) Processor 1: 12, 24, 14, 34, 25, 23, 16, 16, 76; Processor 2: 23, 23, 21, 63, 43, idle 173 to 240; Processor 3: 32, 23, 53, 74, idle 182 to 240; Processor 4: 13, 45, 18, 47, 43, idle 166 to 240

(c) Three machines: Processor 1: 76, 45, 43, 24, 23, 18, 16, 13; Processor 2: 74, 47, 34, 32, 23, 21, 14, 12, idle 257 to 258; Processor 3: 63, 53, 43, 25, 23, 23, 16, idle 246 to 248 Four machines: Processor 1: 76, 43, 24, 23, 16, idle 182 to 194; Processor 2: 74, 43, 25, 23, 16, 13; Processor 3: 63, 45, 32, 23, 18, 12, idle 193 to 194; Processor 4: 53, 47, 34, 23, 21, 14, idle 192 to 194

(d) Processor 1: 84, 45, 43, 25, 23, 23, 16, 12; Processor 2: 82, 55, 34, 32, 23, 18, 14, 13; Processor 3: 71, 61, 43, 24, 23, 21, 16, idle 259 to 271