PLEASE DO IT STEP BY STEP.

IFORMATION THAT MAY BE USEFUL:

Cmax MEANS: Makespan. The makespan, defined as max(C1, . . . , Cn), is equivalent to the completion time of the last job to leave the system. A minimum makespan usually implies a good utilization of the machine(s).

Pj MEANS: Processing time (pij): The pij represents the processing time of job j on machine i. The subscript i is omitted if the processing time of job j does not depend on the machine or if job j is only to be processed on one given machine.

Prec MEANS: "Precedence constraints" may appear in a single machine or in a parallel machine environment, requiring that one or more jobs may have to be completed before another job is allowed to start its processing. There are several special forms of precedence constraints: if each job has at most one predecessor and at most one successor, the constraints are referred to as chains. If each job has at most one successor, the constraints are referred to as an intree. If each job has at most one predecessor the constraints are referred to as an outtree. If no prec appears in the field, the jobs are not subject to precedence constraints.

CP rule Means: From this definition it follows that the CP rule is equivalent to the Highest Level first rule.

LNS rule MEANS: A priority rule often used when jobs are subject to arbitrary precedence constraints is indeed the so-called Largest Number of Successors first (LNS) rule. Under this rule the job with the largest total number of successors (not just the immediate successors) in the precedence constraints graph has the highest priority. Note that in the case of intrees the CP rule and the LNS rule are equivalent; the LNS rule therefore results in an optimal schedule in the case of intrees.

5.2. Consider P4 | prec Cmax with 12 jobs. jobs 1 2 3 45 6 7 8 9 10 11 12 P 10 10 10 12 11 10 12 12 10 10 10 10 The jobs are subject to the precedence constraints depicted in Figure 5.10. 10 5 12 Fig. 5.10 Precedence constraints graph (Exercise 5.2) Exercises 145 (a) Apply the generalized version of the CP rule: every time a machine is freed select the job at the head of the string with the largest total amount of processing (b) Apply the generalized version of the LNS rule: every time a machine is freed select the job that precedes the largest total amount of processing. (c) Is either one of these two schedules optimal? 5.2. Consider P4 | prec Cmax with 12 jobs. jobs 1 2 3 45 6 7 8 9 10 11 12 P 10 10 10 12 11 10 12 12 10 10 10 10 The jobs are subject to the precedence constraints depicted in Figure 5.10. 10 5 12 Fig. 5.10 Precedence constraints graph (Exercise 5.2) Exercises 145 (a) Apply the generalized version of the CP rule: every time a machine is freed select the job at the head of the string with the largest total amount of processing (b) Apply the generalized version of the LNS rule: every time a machine is freed select the job that precedes the largest total amount of processing. (c) Is either one of these two schedules optimal