Job Shop Scheduling Terminology 4.Tardiness and lateness Tardiness is the positive difference between the completion time and the due date of a job. Lateness refers to the difference between the job completion time and its due date and differs from tardiness in that lateness can be either positive or negative. If lateness is positive,it is tardiness;when it is negative,it is earliness Tardines Completion Due date S time of Job i of Job i of Job i Lateness>0--- Tardiness Completion Due date Lateness<0--- time of Job i of Job i Earliness When the completion of Job is earlier than due date,the tardiness is 0 ®上浒道大皇
Job Shop Scheduling Terminology 4. Tardiness and lateness • Tardiness is the positive difference between the completion time and the due date of a job. • Lateness refers to the difference between the job completion time and its due date and differs from tardiness in that lateness can be either positive or negative. • If lateness is positive, it is tardiness; when it is negative, it is earliness Due date of Job i Completion time of Job i Tardines s of Job i Due date of Job i Completion time of Job i When the completion of Job is earlier than due date, the tardiness is 0 Lateness>0--- Tardiness Lateness<0--- Earliness
Sequencing Rules FCFS (first come-first served) Jobs are processed in the sequence in which they entered the shop; The simplest and nature way of sequencing as in queuing of a bank SPT(shortest processing time) Jobs are sequenced in increasing order of their processing time; The job with shortest processing time is first,the one with the next shortest processing time is second,and so on; EDD (earliest due date) Jobs are sequenced in increasing order of their due dates; The job with earliest due date is first,the one with the next earliest due date is second,and so on; 圈上浒充通大漫
Sequencing Rules • FCFS (first come-first served) • Jobs are processed in the sequence in which they entered the shop; • The simplest and nature way of sequencing as in queuing of a bank • SPT (shortest processing time) • Jobs are sequenced in increasing order of their processing time; • The job with shortest processing time is first, the one with the next shortest processing time is second, and so on; • EDD (earliest due date) • Jobs are sequenced in increasing order of their due dates; • The job with earliest due date is first, the one with the next earliest due date is second, and so on;
Sequencing rules CR (Critical ratio) Critical ratio is the remaining time until due date divided by processing time; Scheduling the job with the smallest CR next; Current Remaining time of Job i Due date of Job time i Processing time of Job i CR,-Remaining time of Job i/Processing time of Job i =(Due date of Job i-current time)/Processing time of Job i CR provides the balance between SPT and EDD,such that the task with shorter remaining time and longer processing time takes higher priority; CR will become smaller as the current time approaches due date,and more priority will given to one with longer processing time; For a job,if the numerator of its CR is negative the job has been already later),it is naturally scheduled next; If more than one jobs are later,higher priority is given to one that has shorter processing time(SPT). 圆上泽充通大漫
Sequencing Rules • CR (Critical ratio) Critical ratio is the remaining time until due date divided by processing time; Scheduling the job with the smallest CR next; Processing time of Job i Due date of Job i Current time Remaining time of Job i CRi=Remaining time of Job i/Processing time of Job i =(Due date of Job i-current time)/Processing time of Job i CR provides the balance between SPT and EDD, such that the task with shorter remaining time and longer processing time takes higher priority; CR will become smaller as the current time approaches due date, and more priority will given to one with longer processing time; For a job, if the numerator of its CR is negative ( the job has been already later), it is naturally scheduled next; If more than one jobs are later, higher priority is given to one that has shorter processing time (SPT)
Sequencing Rules Example 5.1 A machine center in a job shop for a local fabrication company has five unprocessed jobs remaining at a particular point in time.The jobs are labeled 1,2,3,4,and 5 in the order that they entered the shop.The respective processing times and due dates are given in the table below. Sequence the 5 jobs by above 4 rules and compare results based on mean flow time,average tardiness,and number of tardy jobs Job number Processing Time Due Date 1 11 61 2 29 45 3 31 31 4 1 33 5 2 32 圈上泽充鱼大崇
Sequencing Rules Example 5.1 A machine center in a job shop for a local fabrication company has five unprocessed jobs remaining at a particular point in time. The jobs are labeled 1, 2, 3, 4, and 5 in the order that they entered the shop. The respective processing times and due dates are given in the table below. Sequence the 5 jobs by above 4 rules and compare results based on mean flow time, average tardiness, and number of tardy jobs Job number Processing Time Due Date 1 2 3 4 5 11 29 31 1 2 61 45 31 33 32
Mean Flow time=268/5=53.6 Sequencing Rules-]Average tardiness=121/5-24.2 No.of tardy jobs=3. Job number Processing Time Due Date t 2 29 4行 3 3 3+ 4 33 2 Job Completion Time Due Date Tardiness 1 11 61 0 2 40 45 0 3 71 31 40 4 72 33 39 5 74 32 42 Totals 268 121
Sequencing Rules——FCFS Job number Processing Time Due Date 1 2 3 4 5 11 29 31 1 2 61 45 31 33 32 Job Completion Time Due Date Tardiness 1 11 61 0 2 40 45 0 3 71 31 40 4 72 33 39 5 74 32 42 Totals 268 121 Mean Flow time=268/5=53.6 Average tardiness=121/5=24.2 No. of tardy jobs=3