Ví dụ về thuật toán Johnson

Thuật toán JOHNSON

1. Chia các chi tiết thành 2 nhóm:

+ Nhóm 1: gồm các chi tiết có thời gian gia công chi tiết trên máy A bé hơn trên máy B.

+ Nhóm 2: gồm các chi tiết có thời gian gia công chi tiết trên máy A lớn hơn trên máy B.

Nếu hai thời gian trên bằng nhau thì vào nhóm nào cũng được.

2. Sắp xếp:

+ Sắp xếp nhóm 1 theo chiều tăng dần của thời gian gia công chi tiết trên máy A

+ Sắp xếp nhóm 2 theo chiều giảm dần của thời gian gia công chi tiết trên máy B

3. Nối nhóm 2 sau nhóm 1. Dãy thu được là lịch tối ưu.

Có 5 công việc được thực hiện trên hai máy. Công việc nào cũng phải làm trên máy 1 trước rồi mới chuyển sang máy 2. Thời gian thực hiện từng công việc được cho như sau:

	A	B	C	D	E
Thời gian thực hiện trên M1	5	3	8	10	7
Thời gian thực hiện trên M2	2	6	4	7	12

Theo thuật toán Johnson 2 máy ta có trật tự các công việc như sau:

                                    B     -   E     -      D      -      C     -      A

Sử dụng sơ đồ Gantt, ta có trật tự các công việc và thời gian tiêu hao tương

ứng như sau:

Theo kết quả trên sơ đồ ta thấy dòng thời gian ngắn nhất để hoàn thành cả 5 công việc trên 2 máy theo thuật toán Johnson là 35 đơn vị thời gian. Với máy 1 cho dù là trật tự bố trí nào thời gian cũng là như nhau và trong ví dụ trên là 33, vấn đề là ở máy 2. Trong trường hợp này khi kết thúc công việc B dòng thời gian là  9, trong khi đó công việc E vẫn đang còn được thực hiện ở máy 1. Dòng thời gian kết thúc của E là 10. Do đó máy 2 sẽ phải chờ máy 1 thì mới có công việc E để gia công trên máy 2.

Thuật toán Johnson dựa vào nguyên tắc ưu tiên cho công việc có thời gian gia công ngắn nhất(STP). Tuy nhiên cũng cần lưu ý rằng đây là bài toán 2 máy do đó không phải lúc nào cũng đưa ra kết quả tối ưu hay nói cách khác phương án có thời gian ngắn nhất trong số các phương án không phải là phương án duy nhất.