IV. Sắp xếp thứ tự gia công 1. Sắp xếp thứ tự gia công trên một máy n công việc cần được tiến hành gia công trên một máy. Mỗi công việc có thời gian gia công và thời hạn hoàn thành quy định. Phải sắp xếp sao cho n công việc được làm nối tiếp nhau đạt được kết quả tối ưu. Nguyên tắc xếp công việc:  Đến trước làm trước (First Come First Served)  Theo thời hạn sớm nhất (Earliest Due Date): Công việc nào có thời hạn hoàn thành sớm nhất sẽ được chọn làm trước tiên.  Theo thời gian gia công ngắn nhất (Shortest Processing Time): Công việc có thời gian gia công ngắn nhất được làm trước.  Theo thời gian gia công dài nhất (Longest Processing Time): Công việc dài nhất được làm trước. Ví dụ: Có 5 công việc được gia công với thời gian và thời hạn cho trước. Công việc Thời gian gia công(ngày) Thời hạn hoàn thành Hãy xác định thứ tự các công việc được gia công theo các nguyên tắc trên. Đến trước làm trước Thứ tự gia công: A,B,C,D,E Công vệc A làm 6 ngày Công việc B chờ 6 ngày để công việc A hoàn thành và 2 ngày gia công kế tiếp, như vậy B hoàn thành sau 8 ngày. Chậm so với thời hạn 2 ngày. Công việc Thời gian gia công(ngày) Dòng thời gian Thời hạn hoàn thành Thời gian chậm trễ Thời gian hoàn thành trung bình = Tổng dòng thời gian/số công việc = 77/5 =15,4 ngày Số công việc trung bình nằm trong hệ thống: = Tổng dòng thời gian/ tổng thời gian gia công = 77/28 = 2,75 công việc Thời gian chậm trễ trung bình: = Tổng số ngày trễ hẹn/ số công việc = 11/5 = 2,2 ngày Theo thời hạn sớm nhất Công việc Thời gian gia công(ngày) Dòng thời gian Thời hạn hoàn thành Thời gian chậm trễ Thời gian hoàn thành trung bình = Tổng dòng thời gian/số công việc = 68/5 =13,6 ngày Số công việc trung bình nằm trong hệ thống: = Tổng dòng thời gian/ tổng thời gian gia công = 68/28 = 2,42 công việc Thời gian chậm trễ trung bình: = Tổng số ngày trễ hẹn/ số công việc = 6/5 = 1,2 ngày Theo thời gian gia công ngắn nhất Công việc Thời gian gia công(ngày) Dòng thời gian Thời hạn hoàn thành Thời gian h