PROBLEM 6.6

PLEASE DO IT STEP BY STEP.

IFORMATION THAT MAY BE USEFUL:

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.

dj Means: Due time (dj) The due date dj of job j represents the committed shipping or completion date (i.e., the date the job is promised to the customer). Completion of a job after its due date is allowed, but then a penalty is incurred. When a due date must be met it is referred to as a deadline and denoted by d .

6.6. Apply Algorithm 3.3.1 to find an optimal schedule for the proportionate flow shop F3] Pi,-P) 1 U, with the following jobs. jobs 1 2 3 4 5 6 p 5 3 44 9 3 d 17 19 21 22 24 24 FOR REFERENCE THIS IS ALGORITH 3.3.1 Algorithm 3.3.1 (Minimizing Number of Tardy Jobs) Step 1 Set J-0, Je,n), and Jd0 Set the counter k = 1. Step 2. Add job k to J Delete job k from J Go to Step 3 Step 3. JEJ go to Step 4. Otherwise, let E denote the job that satisfies p max (p) EJ Delete job &fromJ Add job & to Jd Step 4. Set Jk = J If k = n STOP otherunse set k = k 1 and go to Step 2. In words the algorithm can be described as follows. Jobs are added to the set of on-time jobs in increasing order of their due dates. If including job k to the set of scheduled jobs implies that job k would be completed late, then the scheduled job with the longest processing time, say job, is marked late and discarded. Since the algorithm basically orders the jobs according to their due dates, the worst case computation time is that of a simple sort, i.e., O(n log(n)) Note that the algorithnn creates in its last step n job sets J1,,Set Jk is a subset of jobs,... , k), consisting of those jobs that are candidates for meeting their due dates in the final optimal schedule. Set J consists of all jobs that meet their due dates in the optimal schedule generated. 6.6. Apply Algorithm 3.3.1 to find an optimal schedule for the proportionate flow shop F3] Pi,-P) 1 U, with the following jobs. jobs 1 2 3 4 5 6 p 5 3 44 9 3 d 17 19 21 22 24 24 FOR REFERENCE THIS IS ALGORITH 3.3.1 Algorithm 3.3.1 (Minimizing Number of Tardy Jobs) Step 1 Set J-0, Je,n), and Jd0 Set the counter k = 1. Step 2. Add job k to J Delete job k from J Go to Step 3 Step 3. JEJ go to Step 4. Otherwise, let E denote the job that satisfies p max (p) EJ Delete job &fromJ Add job & to Jd Step 4. Set Jk = J If k = n STOP otherunse set k = k 1 and go to Step 2. In words the algorithm can be described as follows. Jobs are added to the set of on-time jobs in increasing order of their due dates. If including job k to the set of scheduled jobs implies that job k would be completed late, then the scheduled job with the longest processing time, say job, is marked late and discarded. Since the algorithm basically orders the jobs according to their due dates, the worst case computation time is that of a simple sort, i.e., O(n log(n)) Note that the algorithnn creates in its last step n job sets J1,,Set Jk is a subset of jobs,... , k), consisting of those jobs that are candidates for meeting their due dates in the final optimal schedule. Set J consists of all jobs that meet their due dates in the optimal schedule generated