CHƯƠNG 15: LỊCH TRÌNH CỦA MỘT PHÂN XƯỞNG

Chia sẻ: Hoang Trong Tuan | Ngày: | Loại File: DOC | Số trang:23

Thêm vào BST

Báo xấu

313
lượt xem 157
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chúng ta nhớ rằng muc dich cua xí nghiệp là sản xuất. Sự ap dụng các kỹ thuật như quản trị tồn kho, bao tri, quản trị các nguồn nhân lực …co mục tiêu hàng đầu la bảo đảm viec sản xuất có thể được tien hanh trong những điều kiện chấp nhận được. Nếu tòan bộ hệ thống vận hành gan nhu bình thường, thi khi phat lenh san xuat, các trung tâm sản xuất phải có: Danh sách các cong viec phải thực hiện trong một thời gian định trước; Đủ trang thiết bị và nhân công để đảm bảo cho các cong viec...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CHƯƠNG 15: LỊCH TRÌNH CỦA MỘT PHÂN XƯỞNG

Chương 15 LICH TRINH CỦA MỘT PHAN XƯỞNG 15.1 Giới thiệu Chúng ta nhớ rằng muc dich cua xí nghiệp là sản xuất. Sự ap dụng các kỹ thuật như quản trị tồn kho, bao tri, quản trị các nguồn nhân lực …co mục tiêu hàng đầu la bảo đảm viec sản xuất có thể được tien hanh trong những điều kiện chấp nhận được. Nếu tòan bộ hệ thống vận hành gan nhu bình thường, thi khi phat lenh san xuat, các trung tâm sản xuất phải có: - Danh sách các cong viec phải thực hiện trong một thời gian định trước - Đủ trang thiết bị và nhân công để đảm bảo cho các cong viec nay - Nguyên liệu và sản phẩm đòi hỏi. Cho đến giai đọan này, các quyết định phần lớn dựa trên hệ thống thông tin của xí nghiệp. Giờ chi còn phải đảm bảo su điều đan trong ngắn hạn bằng cách quản lí các vấn đề trước mắt: hỏng máy , những bien cố, tình trạng khẩn cấp phút cuối và những vấn đề khác. Vấn đề được đặt ra dĩ nhiên tùy thuộc vào lọai hình sản xuất : ví dụ trong trường hợp một dây chuyền lắp ráp xe hơi , vấn đề chủ yếu là đồng bộ hóa các dòng linh kien để cho ở đầu ra của dây chuyền, mỗi chiếc xe phải có được bộ phận của nó. Trong phần này, chúng ta quan tâm đến cac xuong sản xuất hoac lap rap lam việc voi quy mo nhỏ. Vấn đề chủ yếu ở đây là liên kết được các thao tác để hòan thành mục tiêu sản xuất nói cách khác là xác định lịch trình sản xuất. 15.1.1 Định nghĩa Trước khi tiếp tục , đầu tiên ta sẽ xác định các thuật ngữ được sử dụng về sau. 1. Công việc: Phân xưởng phải đảm bảo một danh sách các công việc. công việc có thể la gia cong một bộ phận duy nhất, sản xuất một lô 100 mẫu XY hoặc cắt một cuon thành 10 cuon nho co chieu dài 100m rộng 20 cm. 2. Thao tác: một công việc được thực hiện bởi một chuỗi các thao tác cơ bản kết hợp lại theo một thứ tự logic mà ta gọi là chuỗi công việc ( ta xác định chuỗi của qui trình chế tạo hoặc chuỗi của quá trình gia công tùy thuộc vào lọai công việc duoc đề cập ). Công việc “ cắt thanh 10 cuon nho “ có thể diễn ra những thao tác sau : - Xuất phát từ cuon mẹ dài 2 m - Đặt cuon mẹ trước thợ đánh ống chỉ - Điều chỉnh dao cắt - Thực hiện việc cắt
- quan lai thành những cuon 3. Nguồn lực : để thực hiện một thao tác đòi hỏi những thiết bị ( máy móc , dụng cụ ) và người điều khiển. Ta gọi nguồn lực là tất cả các phương tiện kỹ thuật và con người cần thiết cho một thao tác. Khi nguồn lực có sẵn bị hạn chế có thể tạo nên những xung đột nhỏ giữa các thao tác. Do đó phải tiến hành phân sử để quyết định những thao tác nào chia nhau nguồn lực có sẵn vào lúc này và những thao tác nào phải chờ đợi. 4. chuỗi thao tác: la chuỗi logic các thao tác, không xác định nguồn lực và máy móc cần thiết để thực hiện. Chuỗi thao tác cũng định rõ những nguồn lực duoc cung cap cho thao tác ( đặc biệc , khi nhiều máy có khả năng thực hiện một thao tác). 5. Lịch tiến độ : tiến độ của tòan bộ công việc bao gồm việc lên chương trình tại thời điểm nào thì thao tác nào phải được thực hiện, nếu cần nên xác định rõ thực hiện trên máy nào với nguồn lực nào, và luon tôn trọng mục tiêu đã xác định. 6. Chuỗi tuần tự : sắp đặt tuần tự tòan bộ công việc, nghĩa là xác định thứ tự chung đi qua các máy. Chuỗi thứ tự thực hiện không chứa đựng thông tin rõ ràng về ngày bắt đầu và kết thúc cac thao tác. Đối với một chuỗi nào đó, có thể tốn tại nhiều lịch tiến độ. 15.1.2 Sự đa dạng của vấn đề Vấn đề lịch tiến độ rat khác nhau tu phan xuong nay sang phan xuong khac và không tồn tại một phương pháp chung cho phép giải quyết một cách có hiệu quả cho tất cả các trường hợp. Sự đa dạng này do giả thuyết và những du lieu khác nhau. 1. Các công việc Một công việc có thể bắt đầu bất cứ khi nào hoặc tồn tại một ngày( hoặc giờ ) tối thiểu trước do ta khong thể khởi động ( ngày co cac tai nguyen ri). Cũng co thể tồn tại một ngày kết thúc kế họach như mong muốn (ngày hòan thành di ) nếu vượt quá ngày này ta phải chịu các hình phạt. 2. Các thao tác Thời lượng pi của một thao tác đã được xác đinh trước ( 20 phút) , ước tính ( khỏang từ 15 đến 20 phút ), hoặc hòan tòan không xác định ( khi sữa chữa một bộ phận nào đó ). Chúng ta có thể ngung 1 thao tác trong khi đang thực hiện ( ưu tiên ) hoặc không . Khi thao tác đã bị ngung, công việc có thể tiếp tục ( quyền ưu tiên voi bo nhớ ) hoặc thao tác phải tro lại luc dau (quyền ưu tiên không được ghi nhớ ). 3. Các chuỗi
- Các thao tác phải độc lập với nhau - Các thao tác của một công việc nào đó phải được lien kết một cách duy nhất theo một trật tự ( chuỗi tuyến tính ). - Chuỗi tạo nên các mối quan hệ định trước ( trật tự bộ phận ) giữa các thao tác. 4. Máy móc - Không có thời gian chuẩn bị và điều chỉnh khi ta thay đổi thao tác. - Chỉ tồn tại thời gian chuẩn bị chi le thuoc các thao tác sắp bắt đầu. - Thời gian chuẩn bị phụ thuộc vào thao tác vừa mới kết thúc và thao tác bắt đầu. 5. Sự noi tiep giữa các thao tác liền nhau của cùng một công việc Trong một vài ngành công nghiệp , các thao tác liền nhau của cùng một công việc phải được thực hịên không có sự chờ đợi hoặc trong một khỏang thời gian định trước. Đặc biệt điều này thể hiện rõ trong đúc điện, khi 1 chi tiet vua ra khoi bon chua acide, chi vai phut sau no phai duoc dua vao bon tiep sau de trung hoa acide. 6. Các mối quan hệ thao tác / máy móc ( nguồn lực ) Một thao tác cần một máy xác định, hoặc nhiều máy ( giống nhau hoặc khác nhau ) có khả năng thực hiện thao tác. Do đó bài tóan lịch tiến độ cong them vao bài tóan sử dụng các máy nào cho thao tác. 7. Diện tích tồn kho Diện tích tồn kho giua cac máy móc có giới hạn hay không. 15.1.3 Ky hieu Chúng ta sử dụng cách ky hieu của Anh , được dùng trong phần lớn các tạp chí và sách. Lưu ý rằng tùy trường hợp ta cần cân nhắc giữa các công việc và các thao tác. m số lượng máy n số lượng công việc i chỉ số công việc hoặc thao tác tùy theo ngữ cảnh ti ngày bắt đầu thực hiện i Ci ngày kết thúc thực hiện i pi thời gian thực hiện i di ngày hòan thành mong muốn hoặc hạn cuối ri ngày tối thiểu bắt đầu công việc thứ i
Li sự chênh lệch so với ngày cuối cùng mong muốn hay trễ dai số: Li = Ci - di Ti trễ thực của i : Ti = Max ( 0 , Ci - di ) Ei hòan thành sớm i : Ei = Max( 0 , di - Ci ) Ui chỉ bao trễ Ui = 1 nếu Ti > 0 ; Ui = 0 nếu không Fi thời gian hiện dien trong xưởng : Fi = Ci - ri Wi khối lượng thao tác i 15.1.4 Các tiêu chuan Để so sánh hai lịch tiến độ, nên định nghĩa các chỉ bao su hoan thien và tiêu chuan đo lường. Ba mục tiêu chính mà ta tìm cách đạt tới liên quan đến thời gian của lam viec, thời gian xuất hiện , sự trễ. 1. Thời gian của tòan bộ công việc Giam tổng thời gian yêu cầu để thực hiện đồng lọat các thao tác la giam Ci lớn nhất. Ta lưu ý rằng CMax = Min( Max Ci ) 2. Thời gian hiện dien (encours) Thời gian hiện dien la thời gian công việc hiện dien trong phan xuong, nghia la lien quan voi Fi = Ci – ri . Tiêu chuan đầu tiên là giảm thiểu tổng các thời gian ∑Fi nay hoặc theo cách tương đương, là giảm thiểu thời gian 1 hiện dien trung bình trong xưởng F = ∑ . Khi co giá trị cua phan n Fi xuong tham gia, ta phải gắn khối lượng Wi với thời gian hiện dien và tiêu chuẩn trở thành ∑WiFi . Lưu ý rằng ∑WiFi = ∑Wi( Ci – ri) = ∑WiCi – hang so. Trong thực tế, tiêu chuẩn được qui ước là C = 1 / n∑ C i và ∑WiCi . Khi ta ước tính phạt một công việc kéo dài co thoi gian cho doi quá lâu , ta sử dụng FMax = Min( Max Fi ) . Tiêu chuẩn này thể hiện lợi ích chỉ khi tồn tại ngày co the su dung duoc. Trong trường hợp ngược lại , CMax và FMax là như nhau. 3. Sự trễ Khi ngày hoàn thành da duoc định truoc, ta tìm các bien phap de những ngày này được ton trọng. Những tiêu chuan là trễ thực ( TMax , T ) hoặc trễ đại số nếu ta đánh giá rằng sớm và trễ deu khong tot. Thỉnh thoảng , những hình phạt do sự trễ không phụ thuộc vào thời lượng trễ ( nếu bộ phận thay thế phải gửi qua đường máy bay, máy bay đến trễ 2 giờ hoặc 20 phút thì sự trễ là như nhau ). Trong trường hợp này chúng ta ghi nhận số lượng công việc bị trễ ∑U i Trong trường hợp một qui trình sản xuất dung luc kịp thời, chúng ta ton trọng 1 cach tot da những ngày xuất hàng đã định trước. Những tiêu chuan se là ∑(αiEi +βiTi). Chi phi của sự sớm αi bao gồm chi phi dự trữ, bảo hiem hoặc do hư hại của sản phẩm. Chi phicủa sự trễ αi bao gồm chi phi do việc không thỏa mãn khách hàng, những chi phi do bi phạt .. Thay cho những chỉ bao ở trên , ta cũng có thể xem xét những chỉ bao đã hiệu chỉnh : nếu ta phải trả tiền bồi thường αi khi thao tac bị trễ , ta sẽ xét
đến ∑αiUi . Nếu ta xem xét tất cả các du lieu và các chỉ bao, ta nhận thấy rằng thuật ngữ “ lịch tiến độ của phân xưởng “ thuc ra bao gom nhieu van de khác nhau. Ngòai ra, dieu quan trong co tinh quyet dinh thứ hai của lịch tiến độ là bối cảnh của sản xuất . Trong trường hợp đơn giản nhất , ta đả biết trước danh sách công việc phải thực hiện và các đặc tinh của nó. Ta nói đây là bối cảnh tĩnh. Khi co nhung công việc có thể đến vào lúc bất kì, và được thêm vào cac công việc dang duoc thuc hien trong lịch tiến độ, ta gọi đó là bối cảnh động. Cuối cùng ta nói bối cảnh reactif khi sự hỏng máy và những điều bất ngờ khác bỗng xảy den. Trong hai trường hợp cuối cùng này, nên phan ung để thich ung va làm cho lịch tiến độ phù hợp với những yêu cầu mới. Các bối cảnh trong công nghiệp rất thường ở dạng động và phan ung lai. Trong khi bài tóan cơ bản vẫn là bài tóan tĩnh. 15.2 Dac tinh tong quat Một lịch tiến độ được xác định hòan tòan bởi tập hợp các ngày kết thúc thực hiện của mỗi thao tác Ci ( hoặc bởi tập hợp các ngày bắt đầu ti ) 15.2.1 Lịch tiến độ chu dong Ví dụ : xem xét một phân xưởng có 3 máy và 3 bộ phận phải được gia công trên 3 máy đó.Các bộ phận phải làn lượt qua 3 máy theo các chuoi thao tác khác nhau được cho dưới đây ( phân xưởng theo mô hình Job shop ) bộ phận máy thời máy thời máy thời lượng lượng lượng 1 2 2 3 3 1 3 2 2 4 1 3 3 6 3 1 3 2 2 3 2 Giả sử rằng các bộ phận phải được thực hiện theo thứ tự bộ phận 1, bộ phận 2 , bộ phận 3 lần lượt trên moi máy. Sơ đồ Gantt sau đây đưa ra một lịch tiến độ có thể ( ta ky hieu 1.2 nghia la thao tác thứ 2 khi gia công bộ phân thứ 1 ) M1 1,3 2,2 3,1 M2 1,1 2,1 3,2 M3 1,2 2,3 3,3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Ta nhan xet rằng có thể thực hiện việc dịch về bên trái các thao tác (2,1) , (3,1) và (3,2) mà không cần đặt lại thứ tự thực hiện các bộ phận. Điều này dẫn đến sơ đồ thứ hai M1 1,3 2,2 3,1 M2 1,1 2,1 3,2 M3 1,2 2,3 3,3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Một lịch tiến độ như thế này mà trong đó tất cả các công việc đều được giu co dinh bên trái được gọi là bán linh họat. Một cách tổng quát hơn, chúng ta nói rằng một lịch tiến độ là bán linh họat nếu không thể khởi động trước một thao tác mà không thay đổi thứ tự thực hiện trên các máy hoặc doi cho một công việc khác hoặc vi phạm một ràng buột kỹ thuật. Nếu thứ tự thực hiện là không bắt buộc, ta có thể doi ve phia trái các thao tác tương ứng với bộ phận 3 , điều này dẫn đến giản đồ thứ ba M1 3,1 1,3 2,2 M2 1,1 2,1 3,2 M3 1,2 3,3 2,3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Một lịch tiến độ như vậy được gọi là linh họat. Một cách tổng quát, ta nói rằng một lịch tiến độ là linh họat nếu không thể khởi động trước một thao tác mà không lam doi cho một thao tác khác hoặc vi phạm một ràng buột kỹ thuật. 15.2.2 Điều độ Một tiêu chuan được gọi là điều độ khi giá trị của nó giảm dần nếu và chỉ nếu ít nhất một trong các Ci giảm dần ( nhung cai khac có giá trị cố định ). Phần lớn các chỉ bao đưa ra những tiêu chuan điều độ ( C , CMax, F , FMax, L , LMax, T ,TMax) . Những ngọai lệ chủ yếu là: 1. những chỉ bao gắn với viec som cua nhung thao tac 2. Những chỉ bao nhằm vào viec noi lai cac tai trong của cong viec.
Dac tinh : người ta chỉ ra rằng để giảm 1 tiêu chuan điều độ, cần thiết xem xét chỉ các lịch tiến độ linh họat (actif). Lấy lại ví dụ trên .Nếu tiêu chuan là giảm tổng thời gian ( CMax), lịch tiến độ thứ 3 là linh hoat va la tốt nhất ( với thời gian tổng cộng là 17 ). Nhưng ngược lại nếu bộ phận 1 phải được giao trong 11 , 2 giao trong 18 và 3 giao trong 19 và tiêu chuan lại là giảm thiểu tổng số thời gian lam sớm hon, lịch tiến độ này trở nên xấu nhất với giá trị là 13. Lịch tiến độ 1 lại trở nên tốt nhất đối với tiêu chí này với giá trị bằng 4. 15.2.3 Lịch tiến độ không có sự chậm trễ Trong một vài trường hợp, các thao tác của cùng một công việc nối tiếp nhau mà không có sự chờ đợi. Trường hợp này tồn tại khi không thể có sự dự trữ giữa các máy hoặc vì những ràng buột kỹ thuật ( chẳng hạn sự lien tiep giữa các bể ngam khi xử lí bề mặt các bộ phận kim lọai ). Do đó ta nói lịch tiến độ không có sự chậm trễ. Giản đồ sau biểu diễn một lịch tiến độ như trên. M1 1,3 2,2 3,1 M2 1,1 2,1 3,2 M3 1,2 2,3 3,3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 15.2.4 Quan hệ trao đổi của các thao tác Xét bài tóan tổng quát sau. Cho một tập hợp n thao tác và một hàm f có giá trị thực, được gán cho một giá trị f(π) tại mỗi hóan vị của π thao tác.Ta muon tìm một hóan vị π* sao cho : f(π*) = min f(π) Nếu chúng ta không biết cấu trúc của hàm f , chỉ còn một cách là ước lượng f(π) đối với mỗi một hóan vị trong n! hóan vị có thể. Bây giời giả sử rằng tồn tại một mối quan hệ tam thoi va hòan tòan R ( có nghĩa là thứ tự gan nhu tòan phần ) trên các thao tác với tính chất là với 2 thao tác b ,c và tất cả các hóan vi có dạng α.b.c.δ , ta có : bRc => f(α.b.c.δ) ≤ f(α.c.b.δ ) Do đó ta có thể thiết lập nên định lí sau đây: neu tồn tại một quan hệ R như trên, thi một giao hóan tối ưu nhất π* co the co duoc bằng cách phân lớp các thao tác theo quan hệ R, với O(nlogn) lần so sánh.
Mối quan hệ này thỉnh thỏang được gọi “ tính chất trao đổi của các cặp kề nhau “ hoặc “ quan hệ trao đổi của các thao tác “ trong các bài tóan của phân xưởng. Nó có nghĩa là khi b và c xuất hiện như những thao tác kề nhau với c trước b, có thể có lợi khi đổi chỗ chúng cho nhau. Phần lớn các qui tắc cổ điển mà chúng ta thấy về sau ( EDD , SPT , Johnson) đều dùng quan hệ này. 15.3 Vấn đề trên một máy Trong phần này chúng ta sẽ thu hẹp vấn đề đến mức đơn giản nhất : chúng ta chỉ có duy nhất một máy trong phân xưởng và các công việc được thu giảm chỉ còn một thao tác duy nhất trên máy này. Lợi ích của vấn đề này là nó cho phép định nghĩa và hợp thức hóa các nguyên tắc uu tien giua cac thao tac mà ta sẽ sử dụng để giải quyết các bài tóan phức tạp hơn. Ban đầu chúng ta sẽ xem xét lai vai vấn đề mà ta da biet giải quyet theo cách tối ưu nhất. Phần lớn các bài tóan lịch tiến độ phân xưởng trên một máy là NP- complets. Chúng ta đưa ra một mô hình được lập trình tuyến tính { 0, 1} 15.3.1 Tối thiểu thời lượng tổng cộng Chúng ta sẽ bắt đầu với tiêu chuan nay la tiêu chuan đơn giản nhất khi xem xét. Nhớ rằng đối với tiêu chuan này các lịch tiến độ chủ động là trội hơn. Nói cách khác, các thao tác san sang sẽ được sắp lịch sao cho các công việc này theo sau các công việc khác mà không để thời gian chết: 1. Khi không có lien he truoc do giữa các thao tác ( các thao tác độc lập), n! lịch tiến độ có thể đều có thời lượng tổng cộng bằng ∑ pi . 2. Khi có lien he truoc do giữa các thao tác, sơ đồ co được bằng cách đặt mội thao tác o 1 dinh , và một cung (A,B) giữa thao tác A và thao tác B, nếu thao tác A phải hòan thành trước khi thao tác B bắt đầu , thì sơ đồ không có đường vòng. Các lịch tiến độ có thể được đưa ra bằng cách lựa chọn các đồ hình của sơ đồ này và chúng đều có thời lượng tổng cộng bằng ∑ pi . 3. Voi ngày hòan thành ri , một giải pháp tối ưu đạt được bằng cách đặt các thao tác theo ri tăng dần. Có thể làm rõ các lời giải tối ưu này. Xét một lịch tiến độ bất kì và ky hieu [i] là công việc thứ i. Với t[i] là ngày bắt đầu chạy máy của công việc thứ i và C[i] là ngày kết thúc của công việc đó. Một lịch tiến độ là tối ưu nếu và chỉ nếu tồn tại ít nhất một công việc[k] sao cho : t[k] = r[k] t[i] = C[i-1] với i = k+1 , .. , n r[k] ≤ r[i] với i = k+1 , .. , n
4. Khi một thao tác mới yêu cầu một thời gian si để thay đổi dụng cụ và những điều chỉnh riêng , chỉ cần xem thời gian thưc hiện thao tác như là tổng thời gian thực hiện pi và thời gian điều chỉnh si . 5. Trong một vài trường hợp, thời gian chuẩn bị và thời gian khởi động máy để thực hiện thao tác thứ k phụ thuộc vào công việc i được thực hiện trước đó trên máy. Goi sik la thời gian này. Việc này thường xảy ra (thi du trong các lò khi mà nhiệt độ khác nhau tùy vào bộ phận được nung , hoặc trong nghành dệt khi chúng ta phải làm lại sợi ngang hoặc trong các công việc sơn). Thời gian cọ rửa các dụng cụ chuyển từ đen sang trắng lớn hơn rất nhiều so với chuyển từ trắng sang đen. Tối thiểu thời luợng tổng cộng được rút lại thành bài tóan của người chào hàng bang cach cho: Thành phố 0 = bắt đầu/ kết thúc của lịch tiến độ Thànhphố i = thao tác i Đi qua thành phố i cần một thời gian pi ( với p0 = 0 ) và di chuyển từ thành phố k đến thành phố i cần một thời gian là sik . 15.3.2 Tối thiểu thời gian hiện dien Nhan xet ban đầu : đối với vấn đề trên môt máy , các tiêu chuan C , J ( số lượng trung bình các thao tác có mặt trong xưởng trong tòan bộ thời gian thực hiện các công việc) và L là tương đương. 1. Công việc độc lập. Để tối thiểu C , lịch tiến độ tối ưu đạt được bằng cách sắp xếp các thao tác theo thời lượng tăng dần : p1 ≤ p2 ...≤ pn ( nguyên tắc được gọi là SPT shortest processing time ). Điều này được chứng tỏ bởi sự chuyển đổi giữa các thao tác. Với [j] là công việc thứ j . Ta có: C[1] = p[1] C[2] = p[1] + p[2] ….. C[n-1] = p[1] + p[2] + p[3] + … + p[n - 1] C[n] = p[1] + p[2] + p[3] + … + p[n-1] + p[n] ___________________________________________ ∑ C[i] = n.p[1] + (n-1).p[2] + …+ 2.p[ n-1] + p[n] sẽ là tối thiểu khi p[1] ≤ p[2] ≤ [3] ≤ … ≤ p[n-1] ≤ p[n] 2. Thời gian hòan thành. Khi tồn các thời gian hòan thành ri và không thể cắt một thao tác ( không ưu tiên ) thì việc tối thiểu C trở thành bài tóan NP- complet. Nếu sự ưu tiên là có thể , lịch tiến độ tối ưu đạt được khi thực hiện, o bat cu thoi diem nao, các thao tác có thời gian lam viec nhỏ nhất còn lại. Nguyên tắc này được gọi là SRPT ( Shortest Remaining Processsing Time ) đây là một sự cải tiến của quy tắc SPT. Trong thực tế chỉ có hai lọai sự kiện được xem xét:
1. Máy móc đang ranh rỗi : Ta sử dụng chúng để thực hiện các thao tác có cong viec còn lại nhỏ nhất trong số các công việc dang san sang. 2. Một thao tác mới xụất hiện trong phân xưởng ( thời gian hien tai là ri ). Với k là thao tác đang được thực hiện. Nếu thời gian lam viec còn lại của k lớn hơn pl , ta dừng thực hiện công việc dang thuc hien tren k và bắt đầu thực hiện công việc cua l. Nếu không tiếp tục thực hiện k và l phải chờ đợi. Để thực hiện một cách hiệu quả thuật tóan này , chúng ta bắt đầu bằng cách lựa chọn các thao tác theo ri tăng dần. Xét một ví dụ có 5 thao tác sau đây. Công việc 1 2 3 4 5 ri 0 1 2 4 9 pi 5 3 1 2 1 Các tính tóan được tóm tắt trong bảng 15.1 với * chỉ thao tác không dang san sang. Thời gian Công việc còn lại Chọn lựa 0 (5****) 1 1 (43***) 2 2 (421**) 3 3 (420**) 2 4 (4102*) 2 5 (4002*) 4 7 (4000*) 1 9 (20001) 5 10 (20000) 1 12 (00000) Bảng 15.1 – Cmax với sự ưu tiên 3. Tối thiểu ∑W i C i . Khi các thao tác là độc lập, một lịch tiến độ tối ưu đạt được khi sắp xếp các thao tác theo pi/ wi tăng dần ( nguyên tắc WSPT : weighted shortest processing time ). Khi có các ngày ri , bài tóan là NP- complet , ke ca khi quyền ưu tiên là được phép. 15.3.3 Tối thiểu thời gian trễ Trong tòan bộ phần này , các thao tác có ngày kết thúc chậm nhất là di 1. Các thao tác độc lập. Khi các thao tác là độc lập , lịch tiến độ nhận được bằng cách xắp xếp các thao tác theo ngày hòan thành tăng dần( d1 ≤ d2 ≤ d3 ≤ .. ≤ dn ) ( nguyên tắc EDD : early due date ou règle de Jackson – 1955 ) • Tối thiểu lượng trễ đại số lớn nhất Lmax (trễ đại số: co the som/ trễ hon).
• Tối thiểu thời gian trễ thực lớn nhất. Lưu ý rằng quy tắc EDD là tối ưu đối với trường hợp đặc biệt này, mot cach kha tong quat, nó cho một lời giải tốt khi ta giải quyết các tiêu chuan như là trễ đại số và trễ thực. 2. Sự mở rộng : Bài tóan này cho phép 2 mở rộng • Xét một hàm đơn điệu không giảm dần fi đối với mỗi thao tác i và tối thiểu fmax = max[ fi( Ci )] • Định rõ các ràng buột ban đầu dưới dạng một thứ tự định trước R : nếu iRj , thì thao tác i phải kết thúc trước khi thao tác j có thể bắt đầu ( trong bài tóan gốc , các thao tác là độc lập , có nghĩa là quan hệ R được xem như là rỗng ) Bài tóan này được giải quyết bởi nguyên tắc đơn giản sau: trong số các thao tác được sắp cuối cùng , có nghĩa là các thao tác không được thừa kế , để xuống cuối cùng thao tác được coi là có chi phi nhỏ nhất trong vị trí này. Rút thao tác ra. Sau đó lặp lại trên tập n-1 thao tác còn lại ( để Lmax , nguyên tắc này sẽ là “ để xuống cuối cùng thao tác có ngày kết thúc lớn nhất “ ). 3. Sap dat theo di-pi : lịch tiến độ đạt được bằng cách xắp xếp các thao tác theo di – pi tăng dần ( ngày bắt đầu tiến hành của các công việc chậm nhất ) xem ra cih loi. Thực vậy , no tối đa thoi gian trễ thực nhỏ nhất (!) là : max( min Ti ) 4.Các công việc trễ hạn . Tối thiểu số lượng công việc trễ đạt được theo cách đa thức. Ta có thể chứng minh rằng chuỗi tối ưu có cấu trúc sau : A : Tập hợp các công việc sớm hạn , sắp xếp theo thứ tự EDD B : Tập hợp các công việc trễ hạn , theo một thứ tự nào đó Thuật tóan được mô tả bởi thủ tục sau : 1. Ban đầu , sắp xếp các công việc theo nguyên tắc EDD A= { tập hợp các công việc } và R = Ф Tính tóan lịch tiến độ tương ứng 2. Nếu tồn tại các công việc trễ hạn trong A, thực hịen như sau : với k công việc trễ hạn ban đầu với l là công việc dài nhất trong số k công việc ban đầu đặt A =A – {l} và R = R + {l} Tính tóan lịch tiến độ Ket thuc 5.Ví dụ Thao tac 1 2 3 4 5 pi 1 5 3 9 7 di 2 7 8 10 11
Ban đầu A = { 1,2,3,4,5 } và R = Ф Vòng lặp 1 Thao tac 1 2 3 4 5 pi 1 5 3 9 7 Ci 1 6 9 18 25 di 2 7 8 10 11 Thao tác trễ hạn đầu tiên là k = 3 Thời lượng lớn nhất của thao tác là l =2 A = { 1 ,3 ,4,5} và R = {2} Vòng lặp thứ 2 Thao tac 1 3 4 5 2 pi 1 3 9 7 5 Ci 1 4 13 20 25 di 2 8 10 11 7 Thao tác trễ hạn đầu tiên là k = 4 Thời lượng lớn nhất của thao tác là l =4 A = { 1,3,5} và R = {2,4} Vòng lặp thứ 3 Thao tac 1 3 5 2 4 pi 1 3 7 5 9 Ci 1 4 11 di 2 8 11 Không còn sự trễ ở các thao tác trong A . Thuật tóan kết thúc và có hai lời giải tối ưu : {1,3,5,4,2} và {1,3,5,2,4} 6.Ngày lam việc ri và ngày hòan thành di. Nếu không có quyền ưu tiên xảy ra tất cả các bài tóan trong lớp này đều là NP-complet. Khi quyền ưu tiên là được phép , có thể tính thời lượng trễ lớn nhất Lịch tiến độ tối thiểu thời lượng trễ lớn nhất ( Tmax) đạt được khi áp dụng nguyên tắc EDD với một vài sự thay đổi sau : luôn dành máy cho các thao tác san sang (và chưa hòan thành ) có di nhỏ nhất
Trong thực tế chỉ có hai lọai sự kiện sau được xem xét • Máy móc duoc rãnh rỗi : Ta dùng chúng cho thao tác có di nhỏ nhất trong số các thao tác san sang. • Một thao tác mới l xuất hiên trong xưởng ( ngày hien tai rl ) . Với k là thao tác đang được thực hiện : Nếu dk ≥ dl ta ngừng thực hiện k và bắt đầu thực hiện l Nếu dk ≤ dl việc thực hiện k vẫn tiếp tục và l đặt ở tình trạng chờ đợi. 15.3.4 Mô hình hóa thành một chương trình tuyến tính Lịch tiến độ trên một máy có thể được mô hình hóa dưới dạng chương trình tuyến tính với các biến { 0,1 } Các biến quyết định Ci ngày hòan thành của thao tác thứ i xij biến hai giá trị xác định thứ tự thực hiện của các thao tác i và j xij = 1 nếu i trước j xij = 0 nếu không Có n biến Ci và toi da n2 biến xij . Trường hợp các thao tác khong lien he voi nhau bởi các quan hệ xác định trước đó thi hai so nay bang nhau. Các ràng buột 1. Nhóm các ràng buột đầu tiên diễn tả rằng khi thao tác a ở trước thao tác b thì Cb≥Ca + pb Nên giai thich các điều kiện nhu sau : Nếu i trước j ( xij = 1 ) thì Cj ≥ Ci + pj. Nếu j trước i ( xij = 0 ) thì Ci ≥ Cj + pi. Điều này được hiện thưc bởi hai phương trình tuyến tính sau với M là một hang số rất lớn Cj – Ci + M.( 1 – xij ) ≥ pj Ci – Cj + M.xij ≥ pi 2. Sự tồn tại của ngày đến ri được đưa ra bởi Ci ≥ ri + pi 3. Sự tồn tại của ngày hòan thành di có thể đưa den: Các biến trễ Ti với các ràng buột Ti ≥ Ci – di Các biến sớm Ei với các ràng buột Ei ≥ di – Ci Hai ràng buột này có thể được gộp lại dưới dạng phương trình : Ti – Ei =Ci– di 4.Các tiêu chuan khác Dòng thời gian Fi thêm vào các ràng buột Fi = Ci – ri
Các biên Li không duoc danh dấu được thay thế bởi Ti – Ei = Ci – di Chỉ thị trễ của thao tác i Ui∈ { 0, 1 } thêm vào M.Ui ≥ Ci – di Ví dụ 1 : sự tối thiểu thời gian làm việc, với ngày đến Min CMax thỏa mãn : CMax ≤ Ci ; ∀ i Ci ≥ ri + pi ; ∀ i Cj – Ci + M.( 1 – xij ) ≥ pj Ci – Cj + M.xij ≥ pi Ví dụ 2 : Sự tối thiểu của viec không được coi trọng ngày di , với các chi phi ai và bi tỷ lệ với sự sớm và sự trễ hạn Min ∑ (a E + b T ) i i i i i thỏa mãn : Ci ≥ ri + pi Cj – Ci + M.( 1 – xij ) ≥ pj Ci – Cj + M.xij ≥ pi Ti – Ei = Ci – di 15.3.5 Giải quyết theo nguyên tắc SEP Các vấn đề trên một máy thích hợp với các cách giải quyết theo cac phương pháp tách và định giá trị từng bước ( SEP hoặc Branch and Bound ). Minh họa nguyên tac của phương pháp SEP dựa trên bài tóan về sự trễ can bang sau. Chúng ta thực hiện 5 thao tác với thời gian thực hiện pi và ngày hòan thành di đã biết trước . Hình phạt Wi trên một đơn vị trễ và ta tìm lịch tiến độ tối thiểu giá trị tổng cộng ∑W i T i Thao tac pi di Wi 1 4 8 2 2 5 9 1 3 3 11 4 4 6 18 2 5 8 20 3 Đối với các bài tóan có sự trễ hạn kéo dài , ta thấy rằng nguyên tắc EDD dựa trên cách sắp xếp các thao tác theo di tăng dần cho một kết quả tốt. Do đó chúng ta sẽ sử dụng phát hiện EDD để xác định lời giải ban đầu thích hợp. pi Ci di Ti Wi WiTi 4 4 8 0 2 0 5 9 9 0 1 0 3 12 11 1 4 4 6 18 18 0 2 0
8 26 20 6 3 18 22 Với sự phát hiện này , chúng ta tìm thấy một lời giải có giá trị 22 Trong các bài tóan với dấu hiệu của sự trễ , sẽ có lợi khi ta chọn thao tác cuối cùng để sắp lịch tiến độ, sau đó kế cuối , và tăng lên cho đến thao tác đầu tiên. Minh họa điều này : thời gian cho tòan bộ 5 thao tác là 26. Do đó chúng ta chắc chắn rằng thao tác thực hiện cuối cùng sẽ vừa xong là vào ngày 26. Do đó chúng ta có thể tính thời lượng trễ và giá trị C5(p) tương ứng với mỗi Thao tac. Thao tác p di Ti = 26 – di Wi C5(p) 1 8 18 2 36 2 9 17 1 17 3 11 15 4 60 4 18 8 2 16 5 20 6 3 18 Trong lúc này chúng ta không biết làm thế nào để sắp lịch tiến độ cho bốn thao tác đầu tiên. Trong trường hợp tốt nhat, không một thao tác nào bị trễ. Do đó giá trị C5(p) sẽ nho so voi tổng giá trị chờ đợi. Với phát hiện EDD , chúng ta có một lời giải với giá trị 22. Khi đặt thao tác 1 ở vị trí cuối cùng trong trường hợp tốt nhất sẽ cho một lời giải với giá trị 36. Vô ích khi theo đuổi ý tưởng trên. Điều này cũng xảy ra tương tự cho thao tác 3 với lời giải có giá trị 60. Do đó chỉ còn 3 lựa chọn có thể : 2, 4 và 5 với các giá trị 17,16 và 18 . Vì chúng ta tìm kiếm một sự tối thiểu , nên ta sẽ bắt đầu bằng cách đặt thao tác 4 ở vị trí thứ 5. Chúng ta lặp lại quá trình trên và chú ý đến thao tác nao sẽ được đặt vào vị trí số 4 biết rằng thao tác thứ 4 vừa xong vào ngày 20. Dần dần chúng ta nhận được một nhánh ban đầu va hai lịch tiến độ có giá trị 19 ( Hình 15.1 )
Bây giờ nên bắt đầu từ cây , bỏ qua những nút có giá trị lớn hơn 19 ( ví dụ : thao tác 3 tại vị trí số 3 ) , và tiếp tục khảo sát trên những nút khác để chọn ra nút có giá trị nhỏ nhất ( ví dụ : Chúng ta bắt đầu khảo sát thao tác 2 trên nút 1 tiếp theo là thao tác 5 trên nút 1 ). Cây tổng thể được cho ra sau đây. (hinh 15.2)
15.4 Vấn đề trên nhiều máy Trong lọai bài tóan này , phân xưởng có m máy và n thao tác phải được thực hiện trên đó. Chuỗi thao tác đã được biết trước và quyền ưu tiên là không được phép. Một thao tác tương ứng với sự đi qua của thao tác trên một máy. Để thuận tiện , ta kí hiệu thao tác Pi-Mj tương ứng với thao tác thứ i ( i =1..n) được thực hiện trên máy j( j = 1.. m ) và ta kí hiệu pij là thời lượng của thao tác này. Trong văn chương , ta phân biệt nhiều trương hợp tùy theo chuỗi thao tac. 1.Flow-shop : các máy được sắp từ 1 đến m và các thao tác đi qua lần lược trên tất cả các máy từ 1 đến m ( dòng sản xuất ). Không có sự hạn chế về thời gian giữa các máy ( diện tích dự trữ đầy đủ ). Xét một máy bất kì. Ta đặt Oj là thứ tự mà các thao tác đi qua máy j . Khi các hàng chờ được quản lí theo FIFO ( vào trước ra trước ) , các thao tác đi qua theo cùng một thứ tự trên tất cả các máy và O1 = O2 = .. = Om .Dó la sự hóan vị của Flow-shop. 2. Job-shop : các chuỗi sẽ khác nhau tùy thuộc vào các thao tác. Trong mô hình cơ bản , các thao tác đi qua mỗi máy chỉ một lần duy nhất , điều này không còn dung nữa trong các mô hình tổng quát. 3. Open-shop : thứ tự đi qua của các thao tác trên các máy không quan trọng. 4.Bài tóan không ưu tiên với sự linh họat về thứ tự thực hiện các thao tác : chuỗi họat động của một thao tác có thứ tự định trước. 5. Bài tóan tổng quát : các nguồn lực khác máy móc có thể tác động ( các dung cu đặc biệt , phương tiện chuyên chở , người vận hành chuyên môn hóa ), lam tang các ràng buột mới, thậm chí lũy tích. Bài tóan có khuynh hướng tiến gần đến lọai bài tóan Pert với các nguồn lực. 15.4.1 Flow-shop trên 2 máy Bài tóan này được giải quyết theo thuật tóan đa thức của Jonhson( 1955 ). Ta đặt ai và bi là thời gian đi qua trên máy 1 và 2 của thao tác i .Một sự ứng dụng của thuật tóan này là : Với U = { i sao cho ai < bi } và V = { i sao cho ai ≥ bi } Lịch tiến độ tối ưu đạt được khi lấy U được sap theo thứ tự tăng dần của ai V được sap theo thứ tự giam dần của bi Ví dụ Thao tac 1 2 3 4 5 6 7 8 ai 5 6 8 2 7 3 4 2 bi 8 4 6 7 2 3 8 4
U = ( 1,4,7,8 ) và sau khi sap hang ta thu được thứ tự 4,8,7,1 V = ( 2,3,5,6 ) và sau khi sap hang ta thu được thứ tự 3,2,6,5 Thứ tự tối ưu là : 4,8,7,1,3,2,5,6 Một mở rộng của thuật tóan này được đưa ra bởi Mitten( 1950 ), người đã đưa vào sự lệch pha giữa các thao tác. Ta đặt li là thời gian nhỏ nhất tu luc bắt đầu của công việc trên máy 1 den luc bắt đầu công việc trên máy 2 ( start-lag ) • li > ai : tồn tại một thời gian kiểm tra , vận chuyển , … giữa hai thao tac. • li = ai : tro ve bài tóan Johnson • li < ai : công việc la sản xuất theo từng lô , và ta có thể bắt đầu gia công lô này trên máy 2 mà không cần chờ đợi đầy lô. Tương tự , Mitten đưa vào thời gian nhỏ nhất si tách giữa sự kết thúc của công việc trên máy 1 và sự kết thúc của công việc trên máy 2 ( stop-lag ). Do đó một lịch tiến độ hóan vị tối ưu được xác định bởi : với U = { i sao cho ai < bi } và V = { i sao cho ai ≥ bi } đặt yi = max ( li – ai , si – bi ) lịch tiến độ tối ưu đạt được khi lấy U được chọn theo thứ tự tăng dần của ai + yi V được chọn theo thứ tự giam dần của bi + yi 15.4.2 Job-shop trên 2 máy Bài tóan này được giải theo cách đa thức theo phương pháp sau : - Với A là tập hợp các thao tác sử dụng máy 1 rồi đến máy 2, sắp theo phương pháp Jonhson. - Với B là tập hợp các thao tác sử dụng máy 2 rồi đến máy 1, sắp theo phương pháp Jonhson. - Với C là tập hợp các thao tác chỉ sử dụng duy nhất máy 1, theo bất cứ một thứ tự nào. - Với D là tập hợp các thao tác chỉ sử dụng duy nhất máy 2, sắp theo bất cứ một thứ tự nào. Thứ tự tối ưu đạt được khi thực hiện: máy 1 theo thứ tự : A đến C rồi đến B máy 2 theo thứ tự : B đến D rồi đến A 15.4.3 Flow-shop trên m máy Kết quả tổng quát :
Định lí 1 : nếu tiêu chuan là điều độ , trong số các lịch tiến độ tối ưu , tồn tại một lịch tiến độ sao cho : O1 = O2 Định lí 2: đối với tiêu chuan Cmax , trong số các lịch tiến độ tối ưu , tồn tại một lịch tiến độ sao cho Om-1 = Om Do đó, de tối thiểu tiêu chuan Cmax cho các bài tóan trên 3 máy , ta chỉ cần xen xét các lịch tiến độ hóan vị. Định lí 3: ( Mac Mahon 1917 ) : lịch tiến độ hóan vị tối ưu cũng là lịch tiến độ tối ưu nếu và chỉ nếu với tất cả các cặp thao tác ( h,i) với h trước i : hoặc là min( phj , pik ) ≤ min( phk , pij ) với 1 ≤ j ≤ k ≤ m hoặc là bất đẳng thức ngược lại luôn xác định Phương pháp phát hiện Tồn tại nhiều phương pháp phát hiện khác nhau.Ở đây chúng ta chỉ giới thiệu hai phương pháp : phương pháp phát hiện CDS là phương pháp tham khảo, và phương pháp phát hiện NEH cho kết quả, theo các kiểm tra, tốt hơn, tuy nhiên phải trả giá khá đắt cho thời gian tính tóan. Lưu ý rằng cả hai phương pháp đều được dùng để xây dựng các lịch tiến độ hóan vị. 1. Phương pháp phát hiện CDS ( Campbell , Dudek và Smith 1970 ) Phương pháp này dựa trên nguyên tắc của Jonhson, là tạo ra m-1 bài tóan trên hai máy ảo. Máy ảo đầu tiên gồm k máy đầu tiên , máy ảo thứ hai gồm k máy cuối cùng với k thay đổi từ 1 đến m-1 . Xét ví dụ sau : có 6 thao tác và 4 máy . Thời gian họat động như sau : Thao tac 1 2 3 4 5 6 M1 6 8 2 2 3 4 M2 4 4 6 6 7 8 M3 3 8 7 2 3 7 M4 8 2 5 8 7 4 Phương pháp xây dựng 3 bài tóan trên 2 máy Bài toán 1 Thao tac 1 2 3 4 5 6 M1 6 8 2 2 3 4 M4 8 2 5 8 7 4 Một thứ tự tối ưu cho bài toán trên 2 máy ảo đạt được theo thuật tóan của Jonhson là (3,4,5,1,6,2). Khi thực hiện 6 thao tác qua 4 máy theo thứ tự như trên , ta nhận được lời giải với giá trị là 50 .