Đến nội dung

Hình ảnh

Bài toán sắp xếp

- - - - - scheduling theory

  • Please log in to reply
Chủ đề này có 4 trả lời

#1
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

BÀI TOÁN SẮP XẾP

 

 

 

Richard Walter Conway, William L. Maxwell, et Louis W. Miller.
Theory of Scheduling. Dover, 2003.

 

 

Chúng ta gặp những bài toán sắp xếp cực kỳ thường xuyên. Chúng xuất hiện mỗi khi chúng ta phải quyết định thực hiện các công việc theo thứ tự nào. Mỗi bài toán có thể liên quan tới một thứ khác nhau, ví dụ: lô hàng ở một nhà máy sản xuất, máy bay chờ đợi lệnh hạ cánh, khách khứa ngồi trước cửa kính ở quầy tiếp khách trong ngân hàng, chương trình để chạy trong máy tính, hay đơn giản là công việc dọn nhà chiều thứ bảy. Luận điểm của chúng tôi đó là, bất kể tính chất của một công việc cụ thể cần xác định thứ tự thực hiện, thì luôn luôn tồn tại sự tương đồng căn bản với bài toán sắp xếp.

 

Bài toán sắp xếp rõ ràng sẽ được giải quyết, bởi vì hầu hết các công việc đều được thực hiện: máy bay hạ cánh, khách ngân hàng nhận/chuyển tiền, và chúng ta làm xong ít nhất vài việc nhà chiều thứ bảy. Tuy nhiên, đa số các bài toán này được giải theo cách ngẫu nhiên hoặc theo lề thói. Chúng ta còn không nhận ra cả sự tồn tại của bài toán đó, chứ đừng nói đến lời giải. Đôi khi, sự sắp xếp được quyết định hoàn toàn bừa bãi; nhiều lúc công việc được thực hiện theo thứ tự chúng xuất hiện. Khao khát công bằng cố hữu đã nâng cao giá trị của giải pháp "tới trước làm trước" (first-come, first-served) trong các bài toán sắp xếp tới một mức độ vô cùng bất xứng với hiệu năng vốn có của nó. Giải pháp ấy có thể thích hợp với những ông chủ bán vé xem phim, song không hẳn sẽ áp dụng tốt với các lô hàng bất động trên sàn nhà máy.

 

Phát biểu vấn đề và lời giải một cách chuẩn tắc cho một bài toán sắp xếp có lẽ là chuyện hiếm. Nếu có thì đại để sẽ như sau:

  • $\alpha$ là chuỗi hành động thực hiện $A$ trước rồi $B$.
  • $\beta$ là chuỗi hành động thực hiện $B$ trước rồi $A$.
  • Vì $\alpha$ được ưa thích hơn $\beta$ nên ta chọn "làm $A$ rồi $B$".

Dĩ nhiên chúng ta sẽ không biện luận rằng phân tích chuẩn tắc trên là thích đáng cho toàn thể bài toán sắp xếp trong đời sống thường nhật, tuy nhiên, đối với những vấn đề trong hoạt động công nghiệp, vận tải, cơ quan chính phủ cũng như tổ chức thì kết quả sắp xếp không phải là chuyện nhỏ nhặt, và chúng ta nên bỏ công sức để suy ngẫm một cách bài bản. Ấy thế các vấn đề đó lại bị giải quyết quá thường xuyên bằng thói quen chứ không phải giải thuật. Điều phối viên máy móc trong công xưởng, dầu là người quyết định những lô hàng nào trong dãy hàng chờ sẽ được làm, lại hay dùng các tiêu chí không liên quan mấy tới mục đích của công ty. Chương trình trên máy tính sẽ chạy theo thứ tự gửi tới CPU, một quy trình công bằng không thể cãi, nhưng ai cũng sẽ thấy rằng làm như vậy còn lâu mới đạt được tới tối ưu. Các chương sách tiếp theo sẽ chứng minh bằng lập luận đại số, ví dụ bằng số cụ thể và thử nghiệm trên máy tính, để cho chúng ta thấy có sự khác biệt đáng kể giữa các thứ tự sắp xếp khác nhau. Ít nhất thì trong một số bài toán thực tế, những khác biệt này ắt hẳn sẽ tạo ra sai khác phí tổn hoặc giá trị thành phẩm đủ lớn để chúng ta cân nhắc. Vấn đề ở đây không phải là quyết định xem có nên giải quyết một bài toán sắp xếp cụ thể nào đó, nên chọn thứ tự nào. Vấn đề là chúng ta sẽ xác định xem quyết định được đưa ra bằng phương pháp nào, bởi ai, và cho tiêu chí gì.

 

 

Vấn đề sắp xếp có lẽ không thiết yếu bằng các quyết định xem tác vụ nào kế tiếp, hoặc tác vụ đó được thực hiện ra sao khi việc tới. Tuy nhiên, nếu lựa chọn thứ tự hợp lý có thể cải thiện kết quả phần nào, thì chúng ta không nên bỏ qua cơ hội như thế. Dẫn chứng trong những chương kế tiếp sẽ chỉ ra rằng nếu áp dụng một cách phân loại, dù là đơn giản nhất, vào hệ thống đa nhiệm, thì chúng ta vẫn sẽ luôn tìm ra những khác biệt thú vị chỉ có thể xuất hiện do thay đổi thứ tự tác vụ. Trong nhiều trường hợp, nhiều giải thuật mặc dù hữu dụng và thực tiễn ngang nhau, lại có những đặc tính hiệu năng khác nhau đáng kể.

 

 

(Còn nữa)


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

1. Những Câu Hỏi Về Sắp Xếp "Thuần Túy"
Khi nghiên cứu về sắp xếp trong ứng dụng thực tế, chúng ta sẽ gặp một khó khăn, đó là những câu hỏi này thường không được xét tách bạch: chúng tác động và xen lẫn với các quyết định thuộc phương diện khác.  Nhiều khi thứ tự thực hiện sẽ ảnh hưởng đến sự lựa chọn tác vụ nào để làm, ảnh hưởng đến tính chất của tác vụ, hoặc ảnh hưởng đến cả phương thức thi hành. Chẳng hạn, một tác vụ sản xuất ban đầu cần làm 100 đơn vị của sản phẩm nào đó. Quyết định trì hoãn đơn hàng này một tháng thay vì bắt đầu làm ngay hôm nay, sẽ có thể có một trong các tác động sau:

  1. Đơn hàng bị hủy bỏ hoàn toàn.
  2. Một đơn hàng phụ kèm được thêm vào để số đơn vị cần sản xuất trở thành $150$.
  3. Xuất hiện thay đổi kỹ thuật trong thiết kế.
  4. Một loại nguyên liệu thô có sẵn hiện tại nhưng sau một tháng thì hết hàng và cần phải thay thế.
  5. Một cỗ máy trọng yếu còn hoạt động hiện tại nhưng sau một tháng thì hư hỏng cần phải sửa chữa, khiến chúng ta phải tìm công cụ thay thế.
  6. Một cỗ máy mới, hoặc công cụ mới, dù hiện tại đang trên đường giao hàng, nhưng tháng tới thì đã tới và nâng cao hiệu suất làm việc.
  7. Công nhân đã làm nhiều công việc tương tự trong suốt tháng qua và đã cải thiện tay nghề.

Nếu bất kỳ thay đổi nào bên trên có thể xảy ra với xác suất đáng kể, thì câu hỏi sắp xếp sẽ trở nên gắn kết mật thiết với quyết định cần làm cái gì và cần làm thế nào. Đối với những trường hợp này, quyết định sắp xếp nhất định sẽ cần có sự xét đoán từ phía kỹ thuật hoặc quản lý. Đáng tiếc là các bài toán như thế lại đặc thù với bối cảnh riêng, do đó chúng ta không thể rút ra được kinh nghiệm tổng quát nào nếu không đặt mình vào hoàn cảnh đã cho.

Giải pháp là chúng ta chỉ cần trích xuất một bài toán không phụ thuộc vào các yếu tố trên để xem xét vấn đề sắp xếp thuần túy. Bài toán như vậy sẽ phi thực tế bởi nó không biểu diễn chính xác tình huống ngoài đời nào, song trên phương diện tổng quát thì lại có nhiều lợi ích, vì nó xấp xỉ được nhiều tình thế. Mặc dù kết quả thu được từ công trình nghiên cứu mô hình lý tưởng trừu tượng này sẽ không cho ta lời giải của bất kỳ bài toán sắp xếp thực tiễn nào, thông tin mà chúng cung cấp lại nên được đặt ra song song với quyết định và dữ liệu về các khía cạnh khác của một vấn đề trong đời thực. Người cầm trịch nên biết hệ quả của một thứ tự sắp xếp khác nếu những thay đổi liệt kê bên trên không xảy ra. Hiểu biết này có lẽ sẽ không là nhân tố chính để quyết định, nhưng ít nhất cũng nên được cân nhắc.

Chúng ta sẽ xem xét một bài toán mà mọi quyết định liên quan tới cần làm cái gìthế nào đã được đưa ra từ trước. Vì những lựa chọn này hoàn toàn không bị ảnh hưởng bởi thứ tự tiến hành, chúng ta sẽ sử dụng các giả định sau xuyên suốt tác phẩm này:

  1. Những công việc cần thực hiện (một công việc là một chuỗi hoạt động định sẵn) đều được xác định hoàn chỉnh; nghĩa là cả đặc tính và tầm quan trọng của công việc đã được quyết định bằng cơ chế nào đó không thuộc phạm trù của cuốn sách này. Dĩ nhiên, chúng ta thường gặp trường hợp quá trình sắp xếp không biết toàn bộ các công việc tương lai, mà chỉ biết lần lượt theo thời gian. Trường hợp này vẫn được chấp nhận trong giả định của chúng ta.
    Chúng ta mở rộng giả định hơn nữa: mọi công việc trong danh sách đều phải thực thi, vì bài toán sắp xếp thuần túy không liên quan tới việc lựa chọn chỉ làm một phần của danh sách cho thỏa mãn yêu cầu nào đó. Ví dụ trong sản xuất, chúng ta không cần suy xét công việc nào sẽ mang lại nhiều lợi nhuận nhất. Chúng ta giả sử rằng các lựa chọn và quyết định như thế đã có từ trước và mỗi công việc là một cam kết chắn chắc sẽ hoàn thành.
  2. Tài nguyên hoặc cơ sở vật chất cần có để thực hiện các công việc trên đều được xác định hoàn chỉnh. Chẳng hạn, bài toán có thể nói rằng một tổ đội $8$ người có thể vận hành $10$ cỗ máy đủ kiểu loại, và thời gian làm việc có thể lên tới $44$ tiếng mỗi tuần. Có thể kết quả của bài toán sắp xếp dựa trên cơ sở hiện tại sẽ khuyến nghị gia tăng năng suất công xưởng bằng cách thêm thiết bị hoặc tăng giờ làm, tuy nhiên vấn đề đấy nằm ngoài khuôn khổ bài toán sắp xếp thuần túy.
  3. Ta đã biết trước thứ tự các hoạt động trong mỗi công việc, bao gồm mọi ràng buộc về thứ tự thực hiện. Ta cũng biết tất cả các phương thức để thực thi những hoạt động này, và công xưởng phải có cơ sở vật chất để hoàn tất mỗi hoạt động.

Hầu hết công trình nghiên cứu trong bài toán sắp xếp đều làm việc với job-shop scheduling và sử dụng các thuật ngữ trong sản xuất: công việc (job), máy (machine), công đoạn (operation), quy trình (routing), và thời gian thực hiện (processing-time). Thực ra, các nghiên cứu đều dựa trên mô hình sắp xếp thuần túy lý tưởng của một nhà máy sản xuất như trên, và kết quả của chúng cũng có thể áp dụng cho những bài toán bên vận tải, truyền thông, dịch vụ, etc. Tuy vậy, cũng có thể nói rằng các kết quả đó không cái nào áp dụng được, vì mô hình lý tưởng này không biểu diễn chính xác một job-shop thực tế nào cả. Nếu tác phẩm này gần gũi với ngành công nghiệp hơn các ngành khác, ấy là bởi kiến thức nền tảng của chúng tôi trong ngành đó đã hướng chúng tôi chọn lựa các giả thiết để nghiên cứu, chứ không phải vì chúng tôi đã chọn tiếp tục sử dụng từ vựng của ngành công nghiệp.

Trước đây chúng tôi có xem xét đến việc phân biệt rạch ròi giữa sắp xếp (sequence) và lập kế hoạch (schedule): sequence liên quan đến thứ tự công đoạn trên một máy, schedule là đồng thời đồng bộ cho nhiều máy. Nhưng chúng tôi thấy rằng phân biệt vậy không làm sáng tỏ được điều gì hơn, nên hai từ này coi như là đồng nghĩa trong những chương kế tiếp.

Trong phần sau, chúng ta sẽ định nghĩa chi tiết các giả định của mô hình lý tưởng nền tảng cho toàn bộ cuốn sách này.

 

(Còn nữa)


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#3
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

2. Quy Trình Job-Shop
Đơn vị căn bản trong quy tình job-shop (xưởng gia công) là operation (tác vụ). Ta có thể hình dung một tác vụ tương tự một công đoạn cơ bản cần phải thực hiện, nhưng trong lý thuyết lập lịch (theory of scheduling) thì chúng ta không cần phải định nghĩa cụ thể một tác vụ. Lý thuyết quan tâm tới những gì có thể mà tác vụ đó có thể làm, chứ không phải bản chất của tác vụ. Ba đặc tính thiết yếu của mỗi tác vụ (các đặc tính khác sẽ được miêu tả trong chương 2) phải được nêu ra trong một bài toán cụ thể:

(1) Một ký hiệu liên kết tác vụ với một job (công việc).
(2) Một ký hiệu liên kết tác vụ với một machine (máy).
(3) Một số thực biểu diễn processing-time (thời gian xử lý) của tác vụ.

Dựa vào ký hiệu nhận diện (1), tập hợp tất cả tác vụ có thể phân hoạch thành các tập con rời nhau và bao trọn (ND: "Phân hoạch" một tập hợp là chia tập hợp đó thành các tập con đôi một không giao nhau (tính "rời nhau") và hợp tất cả các tập con là tập ban đầu (tính "bao trọn")
); các tập con này được gọi là job (công việc). Tương tự, ký hiệu (2) cũng sẽ phân hoạch tập hợp các tác vụ thành các tập con, mỗi tập con sẽ được liên kết với một machine (máy).

Ngoài ra, với mỗi công việc, chúng ta có thể xác định một thứ tự bán phần trên các tác vụ cấu thành công việc (hãy xem như là các yêu cầu kỹ thuật buộc chúng ta phải thực hiện tác vụ theo thứ tự cho trước). Thứ tự bán phần giữa các tác vụ này được ký hiệu bằng một quan hệ nhị nguyên (ND: "Quan hệ nhị nguyên" là quan hệ đặt ra giữa hai phần tử) mà chúng ta gọi là xếp trước. Nếu $ x $ và $ y $ là 2 tác vụ của cùng một công việc, và nếu vì lý do nào đó $ x $ phải tiến hành trước $y $ thì ta nói $ x $ xếp trước $ y $, và ký hiệu là:
\[    x \succ y \]

 

Đồng thời, nếu $ x \succ y $, ta cũng có thể viết là $ y \prec x $ và nói rằng tác vụ $ y $ theo sau tác vụ $ x $. Quan hệ xếp trước này có tính bắc cầu:
\[    x \succ y \text{ và } y \succ z \text{ thì } x \succ z \]

Một trường hợp đặc biệt trong quan hệ thứ tự này là khi không có tác vụ nào khác chen giữa. Ta nói tác vụ $ x $ xếp ngay trước tác vụ $ y $ (hoặc tác vụ $ y $ theo ngay sau $ x $) và viết là:
\[    x \succ \succ y \text{ hoặc } y \prec \prec x \]
nếu $ x \succ y $ và không tồn tại tác vụ $ z $ nào để $ x \succ z \succ y $.

Thông thường, để cho tiện lợi, ta biểu diễn các quan hệ này trên một đồ thị trật tự đi trước (precedence graph) như sau:

Đỉnh của đồ thị sẽ biểu diễn các tác vụ, các cạnh có hướng (mũi tên) biểu diễn quan hệ "xếp ngay trước". Ta nói tồn tại một quan hệ xếp trước giữa hai đỉnh nếu có một đường đi có hướng giữa hai đỉnh đó.

Trong quy trình này, dễ thấy một cỗ máy là một thiết bị hoặc cơ sở có khả năng thực hiện bất cứ điều gì cần thiết để hoàn tất một tác vụ, nhưng nói một cách trừu tượng, thì một cỗ máy chỉ là một trục thời gian với những khoảng thời gian mở cố định. Một xưởng job-shop là một tập các cỗ máy gắn với một tập các tác vụ; một quy trình job-shop bao gồm các cỗ máy, công việc (tác vụ), và một mệnh đề quy định tác vụ nào sẽ chạy trong khoảng thời gian nào trên cỗ máy nào thích hợp.

Lập lịch (schedule) cho một quy trình job-shop tức là gán cho mỗi tác vụ một cỗ máy cụ thể và một vị trí xác định trên trục thời gian của máy đó. Với mỗi tác vụ, việc này tương đương với tìm một hoặc nhiều khoảng $(b_1, c_1), (b_2, c_2), \ldots$ sao cho:
(1) $(c_1 - b_1) + (c_2 - b_2) + \ldots$ lớn hơn hoặc bằng thời gian xử lý tác vụ.
(1) $b_{1x}$, giá trị $b_1$ gán cho tác vụ $x$, không nhỏ hơn $b_{1y}$ với mọi tác vụ $y$ thuộc cùng công việc với $x$ và $y \succ x$.
(1) Từng khoảng $(b_i, c_i)$ nằm hoàn toàn trong những khoảng thời gian mà cỗ máy tương ứng cho phép thực hiện.

Nếu nhìn khác đi, lập lịch có thể coi là việc xây dựng thứ tự các tác vụ gán với từng cỗ máy, phần nào giống với loại trật tự áp đặt lên các tác vụ của mỗi công việc.

Có rất nhiều quy tắc khác nhau được đưa ra để giới hạn sự sắp đặt và gán ghép này. Hầu hết mọi lý thuyết phát triển tới nay đều liên quan tới một quy tắc nghiêm ngặt nào đó; các quy tắc này đều nhằm mục đích là định rõ một quy trình job-shop đơn giản. Ta có thể đưa thêm vài giới hạn vào định nghĩa tập hợp công việc và cỗ máy, cũng như cách thức xây dựng lịch trình. Những giới hạn này là:
(1) Mỗi cỗ máy luôn luôn sẵn sàng thực hiện tác vụ, không tồn tại sự chia cắt trục thời gian thành từng ca hay ngày, và không quan tâm đến sự gián đoạn tạm thời vì hỏng hóc hay bảo dưỡng.
    Mỗi cỗ máy chỉ đơn giản là một khoảng thời gian $(0, T)$ với $T$ là một số lớn tùy ý.
(2) Mỗi công việc là một chuỗi tác vụ được sắp xếp nghiêm ngặt, không hề có sự phân chia hay tụ hợp tác vụ.
    Với mỗi tác vụ $x$, chỉ có tối đa một tác vụ $y$ sao cho $y \succ \succ x$ và tối đa một tác vụ $z$ sao cho $x \succ \succ z$.
(3) Mỗi tác vụ chỉ có thể thực hiện bởi một cỗ máy trong xưởng.
(4) Mỗi loại cỗ máy trong xưởng chỉ có duy nhất một cái.
    Mỗi cỗ máy có một số định danh độc nhất để với mỗi tác vụ trong cùng công việc, tác vụ ấy sẽ gán với một cỗ máy duy nhất trong xưởng.
(5) Không chia cắt: một khi tác vụ đã bắt đầu trên một máy thì nó phải hoàn thành trước khi cỗ máy đó thực hiện một tác vụ khác.
    Mỗi tác vụ chỉ được phép gán với một khoảng $(b,c)$, và $c-b$ bằng với thời gian xử lý tác vụ.
(6) Các tác vụ liên tiếp của một công việc không được có thời gian xử lý chồng lấp nhau. Tại từng thời điểm, mỗi công việc chỉ được có nhiều nhất một tác vụ đang xử lý.
    $b_x$, giá trị $b$ gán cho tác vụ $x$, không được nhỏ hơn $c_y$, với mọi tác vụ $y$ cùng công việc mà $y \succ x$.
(7) Tại từng thời điểm, mỗi máy chỉ xử lý nhiều nhất một tác vụ.
    Xét khoảng $(b_x, c_x)$ gán tác vụ $x$ vào một máy. Với mọi khoảng gán $(b_y, c_y)$ khác trên cùng máy đó, thì $b_x \ge c_y$ hoặc $c_x \le b_y$.

Những giới hạn này chủ yếu là để đơn giản hóa cấu trúc, song đồng thời, chúng cũng làm tăng tính tổng quát của mô hình. Đa phần các ứng dụng khác nhau dựa trên mô hình này đều cần phải nới lỏng một hoặc vài giới hạn trên, vì mô hình đấy không hoàn toàn thực tiễn cho mọi ứng dụng. Tuy nhiên, có vẻ quy trình job-shop đơn giản trên lại là cốt lõi của nhiều ứng dụng, và nghiên cứu nó mang lại những kiến thức hữu ích cho nhiều lãnh vực khác nhau. Dù sao đi nữa, đây cũng là mô hình được sử dụng nhiều nhất trong nghiên cứu từ trước đến nay, trong khi những quy trình job-shop phức tạp kiểu khác chỉ có một số ít công trình tản mác.

Ta nên chú ý một giới hạn cực kỳ quan trọng rằng quy trình job-shop sơ giản chỉ dùng một tài nguyên. Ta giả sử rằng mỗi tác vụ chỉ yêu cầu một cỗ máy để thực hiện. Tuy nhiên, ta cũng có thể giả định rằng công đoạn xử lý cần phải có đồng thời máy, thợcông cụ. Khi ấy, ta cần phải miêu tả thêm trong từng tác vụ loại thợ và công cụ nào cần có; và gán tác vụ vào trục thời gian phải chờ đến khi máy, thợ và công cụ thích hợp đồng thời sẵn sàng.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#4
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

3. Phân Loại Bài Toán Lập Lịch

Một bài toán lập lịch (sắp xếp) được miêu tả bằng bốn thông tin:

  1. Công việc và tác vụ cần thực hiện.
  2. Số lượng và số loại máy cấu thành công xưởng.
  3. Quy tắc sắp đặt công việc.
  4. Tiêu chuẩn đánh giá lịch trình.

Tiểu mục trước đã xác định các thuộc tính của tác vụ và trật tự bán phần của tác vụ trong công việc của mọi bàn toán lập lịch. Mỗi bài toán sẽ khác nhau về số lượng công việc cần làm, thứ tự nhập xưởng của công việc, và thứ tự góp mặt của các cỗ máy khác nhau khi xử lý tác vụ của từng việc. Cách nhập xưởng của công việc sẽ phân biệt bài toán tĩnh động. Bài toán tĩnh, công việc xuất hiện cùng lúc và công xưởng đang rỗi rãi, sẵn sàng khởi động. Do không công việc mới nào đến thêm, ta chỉ cần chú ý vào nhóm công việc hoàn toàn xác định và hiện hữu này. Đối với bài toán động, công xưởng trở thành một quy trình liên tục. Công việc sẽ đến từng đợt, có khi chỉ có thể biết áng chừng trên con số thống kê, và sự nhập xưởng sẽ kéo dài đến tương lai vô tận. Vì vậy, chúng ta phải có những phương pháp khác biệt hoàn toàn để phân tích câu hỏi sắp xếp của hai bài toán này. Chúng tôi phân chia cuốn sách này dựa trên sự phân biệt giữa bài toán tĩnh và động: bài toán tĩnh sẽ được nghiên cứu từ chương 3 đến 7, còn bài toán động là chương 8 đến 11.

Thứ tự xuất hiện của cỗ máy lúc xử lý tác vụ của từng việc sẽ phân định công xưởng là \emph{flow-shop} hay không. Flow-shop là khi mọi công việc nói chung đi từ máy này qua máy khác theo cùng một đường. Trên phương diện mô hình hóa, định nghĩa này hàm ý rằng có thể đánh số các máy sao cho số định danh của máy dành cho tác vụ $y$ sẽ lớn hơn số định danh của máy cho tác vụ $x$ của công việc, nếu $x$ xếp trước $y$.

Ở đối cực, ta có job-shop ngẫu nhiên: không có mô-típ chung cho quy trình thực hiện tác vụ trên các máy. Mỗi máy đều có cùng xác suất được sử dụng cho từng tác vụ của từng công việc. Hiển nhiên, mỗi thái cực này đều hiếm có trên thực tế, hầu hết công xưởng ngoài đời sẽ nằm đâu giữa hai giới hạn này, tuy nhiên hầu như mọi nghiên cứu trong lập lịch đều sử dụng một trong hai thái cực trên.

Các quy tắc lập lịch đã được trình bày gần hết qua các giả định của một quy trình job-shop đơn giản. Trừ khi nêu ra cụ thể, còn lại chúng ta ngầm sử dụng những ràng buộc trong phần 2.

Ta sẽ dùng một ký hiệu gồm 4 thông số, $A / B / C / D$ để đánh dấu bài toán lập lịch.

  • $A$ miêu tả sự nhập xưởng. Đối với bài toán động, $A$ sẽ chỉ ra xác suất phân bố của thời gian nhập xưởng. Với bài toán tĩnh, $A$ sẽ là số lượng công việc. Nếu không nói gì thêm thì các công việc này coi như là đến cùng lúc. Khi viết thông số đầu tiên là $n$, ta coi đó là số lượng công việc - túy ý nhưng hữu hạn - của một bài toán tĩnh.
  • $B$ miêu tả số lượng máy trong xưởng. Thông số thứ hai, ký hiệu bằng $m$, đại diện cho số lượng máy bất kỳ.
  • $C$ miêu tả quá trình thao tác trong xưởng. Các ký hiệu chính bao gồm $F$ cho flow-shop, $R$ cho job-shop ngẫu nhiên, và $G$ cho tổng quát (quá trình bất kỳ). Nếu xưởng chỉ có một máy và không có quá trình thao tác thì thông số thứ 3 sẽ bị lược bỏ.
  • $D$ miêu tả tiêu chuẩn đánh giá lịch trình. Các ký hiệu cho thông số thứ tư này sẽ được trình bày trong Chương 2.

Để ví dụ, bài toán Johnson (Phần 5-2) được ký hiệu là $n / 2 / F / F_{\max}$: chuỗi công việc với số lượng tùy ý, flow-shop hai máy và mục tiêu là tối thiểu hóa flow-time (hay còn gọi là thời gian nằm trong xưởng) lớn nhất.

Bài toán job-shop tổng quát - vẫn chưa có lời giải đến nay - được ký hiệu là $n / m / G / F_{\max}$: lập lịch cho $n$ công việc trong một công xưởng bất kỳ với $m$ máy sao cho công việc cuối cùng được hoàn thành sớm nhất có thể.


  • hxthanh và DOTOANNANG thích
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#5
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Trên đây là chương 1 của cuốn "Theory of Scheduling" của tác giả Conway (2003). Mặc dù tác giả đã giới thiệu bộ ký hiệu sử dụng để định danh bài toán, trong quá trình nghiên cứu của bản thân, mình thấy ký hiệu này không được sử dụng rộng rãi. Do đó mình dịch thêm từ nguồn Wikipedia về ký hiệu Graham (Graham notation). Theo mình, đây là bộ ký hiệu phổ biến hơn và cụ thể hơn.
https://en.wikipedia..._job_scheduling
 
Ký hiệu Graham
Đối với các bài toán lập lịch tối ưu, Ronal Graham và một số nhà nghiên cứu khác đã đề xuất ký hiệu $\alpha | \beta | \gamma$ để dán nhãn các bài toán. Mỗi thông số có thể bao gồm một chuỗi các từ ngăn cách bằng dấu phẩy. Dưới đây là định nghĩa của mỗi thông số, kèm theo một số giá trị thông dụng:

  • $\alpha$ biểu thị môi trường máy móc (machine environment):
    • $1$ (Single-machine): một máy duy nhất.
    • $P$ (Identical-machines / Parallel machines): nhiều máy song song và giống nhau. Công việc $j$ sẽ yêu cầu thời gian xử lý $p_j$ giống nhau trên mọi máy.
    • $Q$ (Uniform-machines): nhiều máy song song và có tốc độ khác nhau. Công việc $j$ sẽ mất $p_j / s_i$ thời gian trên máy $i$.
    • $R$ (Unrelated-machines): nhiều máy song song và khác nhau. Công việc $j$ sẽ mất thời gian $p_{ij}$ trên máy $i$.
    • $O$ (Open-shop): mỗi công việc $j$ sẽ có $m$ tác vụ $O_{ij}$. Tác vụ có thể thực hiện theo bất kỳ thứ tự nào. Tác vụ $O_{ij}$ sẽ mất $p_{ij}$ thời gian trên máy $i$.
    • $F$ (Flow-shop): mỗi công việc $j$ sẽ có $m$ tác vụ $O_{ij}$ cần thực hiện theo đúng thứ tự này. $O_{ij}$ sẽ mất $p_{ij}$ trên máy $i$.
    • $J$ (Job-shop): mỗi công việc $j$ bao gồm $n_j$ tác vụ $O_{kj} (k=1,\ldots,n_j)$ cần thực hiện theo đúng thứ tự. Tác vụ $O_{kj}$ cần $p_{kj}$ thời gian trên một máy $\mu_{kj}$ chuyên dụng và hai tác vụ $k, k'$ của cùng công việc $j$ sẽ cần hai máy $\mu_{kj}, \mu_{k'j}$ khác nhau $(k \ne k' \Rightarrow \mu_{kj}\ne \mu_{k'j})$.
    Mỗi ký hiệu chữ có thể đi kèm với một số để biểu thị số lượng máy là cố định. Ví dụ $P2$ là hai máy song song. $Pm$ là $m$ máy song song với $m$ là một hằng số. Trái lại, $P$ cho ta biết có $m$ máy song song nhưng $m$ không cố định ($m$ là một phần của dữ liệu đầu vào).
  • $\beta$ mô tả đặc tính công việc và các ràng buộc, ví dụ thời gian xử lý, nhập xưởng, giới hạn, tái khởi động, quan hệ trước sau, v.v.
    • $p_i = p$ hoặc $p_{ij} = p$: thời gian xử lý giống nhau cho mọi công việc.
    • $p_i = 1$ hoặc $p_{ij} = 1$: thời gian xử lý là 1 đơn vị thời gian đối với mọi công việc. Công việc dạng này được gọi là unit job (công việc đơn vị).
    • $r_j$: mỗi công việc có thời gian đến (release time). Ta không thể lập lịch cho việc $j$ sớm hơn mốc này.
    • $online-r_j$: bài toán online. Thông tin công việc chỉ xuất hiện khi công việc đến. Trường hợp này, chúng ta hay đo competitive ratio của thuật toán.
    • $d_j$: mỗi công việc có hạn chót (due date, deadline). Công việc phải thực hiện xong trước hoặc đúng hạn, nếu không sẽ có hình phạt (penalty).
    • $ptmn$ hoặc $prmp$ (preemption): công việc có thể dừng và sau đó tiếp tục trên cùng máy hoặc máy khác.
    • $split$: công việc có thể chia đều (split) và thực hiện cùng lúc trên nhiều máy.
    • $prec$ (precedence): một số công việc cần phải được thực hiện trước khi làm công việc khác.
    • $l_{ij}$ (time-lag): sau khi xong công việc $i$, ta phải chờ một khoảng $l_{ij}$ trước khi làm việc $j$.
    • $s_{j}$ (setup): công việc $j$ cần có một khoảng thời gian chuẩn bị $s_j$ trước khi bắt đầu thực hiện.
    • $M_j$ (eligible): công việc $j$ chỉ được phép thực hiện trên những máy được nếu trong tập hợp $M_j$.
    Thời gian xử lý công việc thường được hiểu ngầm là số tự nhiên, tuy nhiên không phải khi nào cũng vậy.
  • $\gamma$ là hàm mục tiêu (objective function): thông thường, mục tiêu là tối thiểu hóa một đại lượng nào đó. Đại lượng này có thể là một giá trị cực đại, cực tiểu, tổng hoặc tổng có hệ số (công việc $j$ sẽ có hệ số $w_j$).
    • $-$: không có hàm mục tiêu. Bài toán chỉ yêu cầu tìm một lịch trình khả thi (feasible) thỏa mãn mọi ràng buộc.
    • $C_j$ (completion time): thời gian hoàn thành của công việc $j$.
    • $C_{\max}$ (maximal completion time, makespan): thời gian hoàn thành toàn bộ công việc. $C_{\max} = \max\limits_{j} C_j$.
    • $F_j$ (flow time): thời gian tồn đọng, bằng khoảng cách giữa lúc nhập xưởng đến lúc hoàn thành. $F_j=C_j - r_j$.
    • $L_j$ (lateness): thời gian trễ. $L_j=C_j - d_j$.
    • $T_j$ (tardiness): thời gian trễ nếu có. $T_j = \max \{ 0; C_j - d_j \}$.
    • $E_j$ (earliness): thời gian trước hạn. $E_j = \max \{ 0; d_j - C_j \}$.

  • hxthanh và DOTOANNANG thích
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: scheduling theory

0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh