Phân Tích Độ Phức Tạp và Thuật Toán cho Lập Lịch Công Việc Độc Lập

Khám phá sự phức tạp và các thuật toán trong việc lập lịch đa tiêu chí cho công việc độc lập và công việc can thiệp trong sản xuất.

• Tác giả: Nguyen Huynh Tuong
• Người hướng dẫn: Soukhal Ameur, Maître De Conférences, Université François Rabelais De Tours
• Trường học: Université François-Rabelais de Tours
• Chuyên ngành: Informatique
• Đề tài: Complexité Et Algorithmes Pour L’ordonnancement Multicritere De Travaux Indépendants : Problèmes Juste-À-Temps Et Travaux Interférants
• Loại tài liệu: Thèse
• Năm xuất bản: 2009
• Địa điểm: Tours

Mục lục chi tiết

• Remerciements
• Résumé
• Abstract
• 1. Introduction générale
• 2. I: Ordonnancement juste-à-temps à date due commune
• 1.1. Introduction à l’ordonnancement juste-à-temps
• 1.1.1. Systèmes "Juste-à-temps"
• 1.1.2. Mesurer l’avance/retard d’un travail
• 1.1.3. Mesurer le coût total d’avances et retards des travaux
• 1.1.3.1. Fonction de coût linéaire continue
• 1.1.4. Dates de fin souhaitée
• 1.1.4.1. Date de fin commune donnée
• 1.1.4.2. Famille de dates de fin commune donnée
• 1.1.4.3. Dates de fin commune contrôlable
• 1.1.4.4. Dates de fin souhaitées généralisées
• 1.1.5. Complexité et approximation polynomiale
• 1.1.5.1. Approximation et garanties de performances
• 1.1.5.2. Schémas d’approximation polynomiaux
• 1.1.6. Problèmes d’ordonnancement Juste-à-temps abordés
• 2.1. Retard pondéré avec une date de fin donnée
• 2.1.1. État de l’art
• 2.1.1.1. Approximabilité du retard pondéré
• 2.1.1.2. Remarques sur programme dynamique de Lawler et Moore
• 2.1.2. Problème d’ordonnancement à une seule machine
• 2.1.2.1. Nouveau programme dynamique
• 2.1.3. Problème d’ordonnancement à machines identiques
• 2.1.3.1. Programme dynamique pour le cas de machines identiques
• 2.1.3.2. Extension au cas de machines uniformes
• 3.1. Avance et retard pondérés avec dates de fin données
• 3.1.1. Propriétés pour le cas d’une date de fin souhaitée commune
• 3.1.2. Durées opératoires identiques
• 3.1.2.1. Une seule machine avec une date de fin souhaitée commune
• 3.1.2.2. Une seule machine avec deux dates de fin souhaitées
• 3.1.2.3. Une seule machine avec famille de dates de fin souhaitées
• 3.1.2.4. Machines uniformes avec famille de dates de fin souhaitées
• 3.1.3. Durées opératoires quelconques
• 3.1.3.1. PTAS pour le cas d’une seule machine
• 3.1.3.2. PTAS pour le cas de m machines parallèles identiques
• 4.1. Avance et retard pondérés avec dates de fin contrôlables
• 4.1.1. Quelques notations spécifiques à ce chapitre
• 4.1.2. Durées opératoires identiques
• 4.1.2.1. Une seule machine avec une seule date de fin souhaitée
• 4.1.2.2. Machines identiques avec famille de dates de fin souhaitées
• 4.1.2.3. Machines uniformes avec une seule date de fin souhaitée
• 4.1.3. Durées opératoires quelconques
• 4.1.3.1. Une seule machine avec une seule date de fin souhaitée
• 4.1.3.2. Machines parallèles avec une seule date de fin souhaitée
• 5. Conclusion et perspectives de la première partie
• 3. II: Ordonnancement de travaux interférant indépendants
• 6. Introduction à l’ordonnancement des travaux interférants
• 6.1. Motivation et contexte de travail
• 6.2. Brève introduction de l’ordonnancement multi-critère
• 6.3. Classes de méthodes de résolution
• 6.4. Définition de l’ordonnancement avec des travaux interférants
• 6.5. État de l’art
• 6.6. Intérêt de l’étude
• 7. Problème d’ordonnancement à une seule machine
• 7.1. Problèmes résolus en temps polynomial
• 7.2. Problèmes NP-difficiles au sens ordinaire
• 7.3. Problèmes NP-difficiles au sens fort
• 8. Problème d’ordonnancement à machines parallèles
• 8.1. Résultats de complexité
• 8.2. Algorithme de programmation dynamique
• 8.2.1. Formulation générale de programmation dynamique
• 8.2.2. Une application de la formulation générale
• 8.2.3. Problèmes avec les fonction objectifs ∑ Cj (N1 ) et ∑ Cj (N )
• 8.2.4. Problèmes avec les fonction objectifs ∑ w j Cj (N1 ) and Cmax (N )
• 8.2.5. Problèmes avec les fonction objectifs ∑ w j Cj (N ) and Cmax (N1 )
• 8.2.6. Problèmes avec les fonction objectifs Cmax (N ) et Cmax (N1 )
• 9. Conclusion et perspectives de la seconde partie
• Conclusion générale et perspectives
• Liste des tableaux
• Table des figures

Tóm tắt

I. Tổng quan về Thuật Toán và Phân Tích Độ Phức Tạp trong Lập Lịch Công Việc Độc Lập

Thuật toán và phân tích độ phức tạp là hai khía cạnh quan trọng trong việc lập lịch công việc độc lập. Chúng giúp tối ưu hóa quy trình làm việc, giảm thiểu thời gian và chi phí. Việc áp dụng các thuật toán hiệu quả có thể cải thiện đáng kể hiệu suất của hệ thống. Nghiên cứu này sẽ đi sâu vào các phương pháp lập lịch, từ đó đưa ra các giải pháp tối ưu cho các vấn đề thực tiễn.

1.1. Khái niệm cơ bản về Thuật Toán Lập Lịch

Thuật toán lập lịch là quy trình xác định thứ tự thực hiện các công việc. Các thuật toán này có thể được phân loại thành nhiều loại khác nhau, tùy thuộc vào mục tiêu và yêu cầu cụ thể của từng bài toán.

1.2. Phân Tích Độ Phức Tạp trong Lập Lịch

Phân tích độ phức tạp giúp đánh giá hiệu suất của các thuật toán lập lịch. Điều này bao gồm việc xác định thời gian và không gian cần thiết để thực hiện thuật toán, từ đó đưa ra các lựa chọn tối ưu hơn.

II. Vấn đề và Thách thức trong Lập Lịch Công Việc Độc Lập

Lập lịch công việc độc lập đối mặt với nhiều thách thức, bao gồm sự cạnh tranh giữa các công việc và yêu cầu về thời gian. Các vấn đề như độ trễ, chi phí và tài nguyên hạn chế cần được xem xét kỹ lưỡng. Việc tìm ra giải pháp cho những thách thức này là rất quan trọng để tối ưu hóa quy trình làm việc.

2.1. Các Vấn Đề Thường Gặp trong Lập Lịch

Các vấn đề thường gặp bao gồm độ trễ trong việc hoàn thành công việc, sự xung đột giữa các công việc và yêu cầu về tài nguyên. Những vấn đề này có thể dẫn đến sự không hiệu quả trong quy trình làm việc.

2.2. Thách Thức trong Việc Tối Ưu Hóa Lịch Trình

Tối ưu hóa lịch trình đòi hỏi phải cân nhắc nhiều yếu tố như thời gian hoàn thành, chi phí và sự hài lòng của khách hàng. Việc tìm ra sự cân bằng giữa các yếu tố này là một thách thức lớn.

III. Phương Pháp Giải Quyết Vấn Đề Lập Lịch Công Việc Độc Lập

Có nhiều phương pháp để giải quyết vấn đề lập lịch công việc độc lập, bao gồm thuật toán tham lam, lập trình động và các phương pháp tối ưu hóa khác. Mỗi phương pháp có ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp là rất quan trọng.

3.1. Thuật Toán Tham Lam trong Lập Lịch

Thuật toán tham lam là một trong những phương pháp đơn giản và hiệu quả để lập lịch. Nó hoạt động bằng cách chọn lựa công việc tốt nhất tại mỗi bước, tuy nhiên, không phải lúc nào cũng đảm bảo kết quả tối ưu.

3.2. Lập Trình Động và Ứng Dụng của Nó

Lập trình động là một phương pháp mạnh mẽ cho các bài toán lập lịch phức tạp. Nó cho phép giải quyết các vấn đề bằng cách chia nhỏ chúng thành các bài toán con và giải quyết từng bài toán một cách hiệu quả.

IV. Ứng Dụng Thực Tiễn của Thuật Toán Lập Lịch

Các thuật toán lập lịch có nhiều ứng dụng trong thực tiễn, từ sản xuất đến quản lý dự án. Việc áp dụng các thuật toán này giúp tối ưu hóa quy trình làm việc và nâng cao hiệu suất. Nghiên cứu đã chỉ ra rằng việc sử dụng thuật toán lập lịch hiệu quả có thể giảm thiểu chi phí và thời gian.

4.1. Ứng Dụng trong Ngành Sản Xuất

Trong ngành sản xuất, lập lịch công việc độc lập giúp tối ưu hóa quy trình sản xuất, giảm thiểu thời gian chết và tăng cường hiệu suất làm việc.

4.2. Ứng Dụng trong Quản Lý Dự Án

Trong quản lý dự án, việc lập lịch công việc độc lập giúp đảm bảo rằng các nhiệm vụ được hoàn thành đúng hạn, từ đó nâng cao hiệu quả và sự hài lòng của khách hàng.

V. Kết Luận và Tương Lai của Lập Lịch Công Việc Độc Lập

Lập lịch công việc độc lập là một lĩnh vực nghiên cứu quan trọng với nhiều thách thức và cơ hội. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều tiến bộ với sự phát triển của công nghệ và các phương pháp mới. Việc tiếp tục nghiên cứu và phát triển các thuật toán lập lịch sẽ giúp cải thiện hiệu suất và giảm thiểu chi phí trong nhiều lĩnh vực.

5.1. Tóm Tắt Các Kết Quả Nghiên Cứu

Nghiên cứu đã chỉ ra rằng việc áp dụng các thuật toán lập lịch hiệu quả có thể cải thiện đáng kể hiệu suất làm việc và giảm thiểu chi phí.

5.2. Triển Vọng Tương Lai của Lập Lịch

Tương lai của lập lịch công việc độc lập sẽ được định hình bởi sự phát triển của công nghệ và các phương pháp tối ưu hóa mới, mở ra nhiều cơ hội cho nghiên cứu và ứng dụng.

Nội dung chính

Tổng quan luận án

Lý thuyết lập lịch (scheduling theory) là một lĩnh vực của tối ưu hóa tổ hợp, nằm ở giao điểm giữa toán học ứng dụng, khoa học máy tính và nghiên cứu vận hành. Xuất phát từ thực tiễn quản lý và điều hành sản xuất, các bài toán lập lịch hướng tới việc phân bổ tài nguyên cho các tác vụ và xác định thời điểm thực thi nhằm tối ưu hóa các mục tiêu định trước.

Trong các hệ thống sản xuất hiện đại, đặc biệt dưới triết lý sản xuất Tinh gọn (Lean Manufacturing) và Đúng hạn (Just-in-Time - JàT), sự chú trọng chuyển dịch từ sản xuất đẩy (push system) sang sản xuất kéo (pull system). Các tiêu chuẩn đánh giá truyền thống dựa trên các hàm mục tiêu chính quy (regular criteria) như thời gian hoàn thành cực đại ($C_{\max}$), tổng thời gian hoàn thành ($\sum C_i$), hay độ trễ cực đại ($L_{\max}$) không còn phản ánh đầy đủ yêu cầu thực tế. Việc hoàn thành công việc quá sớm làm phát sinh chi phí lưu kho, chi phí vốn và nguy cơ hư hỏng sản phẩm; ngược lại, hoàn thành trễ hạn dẫn tới phạt vi phạm hợp đồng và giảm mức độ hài lòng của khách hàng. Do đó, các tiêu chuẩn phi chính quy (non-regular criteria) kết hợp đồng thời độ sớm ($E_i$) và độ trễ ($T_i$) trở thành trọng tâm nghiên cứu.

Đồng thời, trong môi trường đa tác tử (multi-agent) hoặc chuỗi cung ứng dùng chung tài nguyên, các tập công việc khác nhau thường thuộc về các đối tượng thụ hưởng khác nhau với mục tiêu riêng biệt, dẫn đến sự cạnh tranh tài nguyên được gọi là lập lịch các công việc can thiệp (interfering jobs).

Luận án của nghiên cứu sinh Nguyen Huynh Tuong giải quyết hai nhóm bài toán cốt lõi:

1. Nhóm bài toán lập lịch đúng hạn với ngày hoàn thành mong muốn chung (Just-in-Time Scheduling with Common Due Date): Nghiên cứu các bài toán lập lịch công việc độc lập trên một máy và trên các máy song song, trong hai trường hợp ngày hoàn thành mong muốn chung được xác định trước (given due date) hoặc có thể kiểm soát/ấn định (controllable due date). Mục tiêu là xác định thứ tự thực hiện và thời điểm bắt đầu tối ưu, phân tích độ phức tạp thuật toán, xây dựng thuật toán chính xác (quy hoạch động, quy về bài toán gán) và các sơ đồ xấp xỉ đa thức (PTAS/FPTAS).
2. Nhóm bài toán lập lịch các công việc can thiệp (Scheduling with Interfering Jobs): Khảo sát bài toán đa mục tiêu trong đó một tiêu chuẩn được tối ưu hóa cho toàn bộ tập công việc ($N$), trong khi một tiêu chuẩn khác chỉ tối ưu hóa cho một tập con công việc ($N_1 \subset N$). Luận án xác định ranh giới độ phức tạp tính toán và đề xuất các thuật toán đa thức, giả đa thức dựa trên các phương pháp $\epsilon$-ràng buộc, kết hợp tuyến tính và quy hoạch mục tiêu (goal programming).

Đối tượng nghiên cứu của luận án là các công việc độc lập không cho phép ngắt quãng (non-preemptive independent jobs) được xử lý trên hệ thống máy đơn ($1$), hệ thống $m$ máy song song giống hệt ($P_m$) và hệ thống $m$ máy song song đồng nhất ($Q_m$). Phạm vi nghiên cứu tập trung vào phân tích độ phức tạp tính toán lý thuyết và thiết kế thuật toán trong tối ưu hóa tổ hợp.

Tổng quan tài liệu và vị trí của luận án

Về bài toán lập lịch Đúng hạn (JàT): Khái niệm JàT được phát triển từ triết lý quản trị Toyota do Taiichi Ohno khởi xướng nhằm loại bỏ lãng phí (Muda). Trong lý thuyết lập lịch, Kanet (1981) là một trong những tác giả đầu tiên đưa ra bài toán với ngày hoàn thành mong muốn chung $1|d_i=d|\sum (E_i + T_i)$ và chỉ ra cấu trúc nghiệm dạng chữ V (V-shape property). Các nghiên cứu tổng quan của Baker và Scudder (1990), Gordon et al. (2002), Lauff và Werner (2004), Sourd (2005) đã hệ thống hóa các dạng bài toán với ngày hoàn thành hạn chế (restrictive) và không hạn chế (unrestrictive).

Đối với hàm mục tiêu độ trễ có trọng số ($\sum w_i T_i$), Lawler và Moore (1969) đã công bố thuật toán quy hoạch động với độ phức tạp giả đa thức $O(n^2 d)$ cho bài toán một máy và cho rằng thuật toán có thể mở rộng trực tiếp sang trường hợp nhiều máy song song. Yuan (1992) chứng minh $1|d_i=d|\sum w_i T_i$ là NP-khó theo nghĩa thông thường, trong khi Lenstra, Rinnooy Kan và Brucker (1977) chứng minh $1|d_i|\sum w_i T_i$ là NP-khó theo nghĩa mạnh. Đối với bài toán xấp xỉ, Kovalyov và Werner (2002) chứng minh $P_m|d_i=d|\sum T_i$ không tồn tại thuật toán xấp xỉ đa thức trừ khi P = NP, nhưng đề xuất thuật toán thỏa mãn $(X^\sharp - X^) \le \epsilon(X^ + d)$. Kellerer và Strusevich (2006) thiết lập FPTAS với độ phức tạp $O(n^6 \log W / \epsilon^3)$ cho $1|d_i=d|\sum w_i T_i$.

Về bài toán công việc can thiệp (Interfering Jobs): Nghiên cứu kế thừa khung lý thuyết lập lịch đa mục tiêu của T'Kindt và Billaut (2006) và tiếp cận các bài toán lập lịch đa tác tử của Agnetis et al. (2004), Baker và Smith (2003), Yuan et al. (2005).

Khoảng trống học thuật mà luận án tập trung giải quyết:

• Làm rõ tính khả thi và khắc phục các hạn chế trong việc mở rộng quy hoạch động của Lawler và Moore cho bài toán cực tiểu hóa trễ có trọng số trên máy song song ($P_m, Q_m$).
• Giải quyết bài toán chi phí sớm - trễ kết hợp ($\sum (\alpha_i E_i + \beta_i T_i)$) trên máy đơn và máy song song khi thời gian xử lý bằng nhau hoặc bất kỳ, xây dựng các sơ đồ xấp xỉ đa thức (PTAS).
• Thiết lập bản đồ độ phức tạp tính toán và thuật toán giải chính xác cho bài toán công việc can thiệp trên máy đơn và máy song song dưới nhiều cấu hình tiêu chuẩn mục tiêu khác nhau.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án sử dụng ký hiệu chuẩn ba trường $\alpha|\beta|\gamma$ của Graham et al. để mô tả các bài toán lập lịch.

Các khái niệm và mô hình toán học

• Độ sớm ($E_i$) và Độ trễ ($T_i$): Cho công việc $J_i$ có thời gian hoàn thành $C_i$ và ngày hoàn thành mong muốn $d_i$: $$E_i = \max(0, d_i - C_i), \quad T_i = \max(0, C_i - d_i)$$
• Độ sẵn sàng (Promptitude): $E_i^r = \max(0, r_i - s_i)$ với $r_i$ là thời điểm đến, $s_i$ là thời điểm bắt đầu thực tế.
• Hàm chi phí tuyến tính liên tục: $$F_i(E_i, T_i) = \sum_{i=1}^n (\alpha_i E_i + \beta_i T_i)$$ Bao gồm 4 trường hợp: Đơn vị ($\alpha_i = \beta_i = w$), Đồng nhất ($\alpha_i = \alpha, \beta_i = \beta$), Đối xứng ($\alpha_i = \beta_i = w_i$), và Bất kỳ ($\alpha_i, \beta_i$ tùy ý).
• Mô hình xác định ngày hoàn thành kiểm soát được:
  • CON (Constant flow allowance): $d_i = d$
  • SLK (Slack): $d_i = r_i + p_i + q$
  • TWK (Total Work): $d_i = r_i + k \times p_i$
  • PPW (Processing Plus Wait): $d_i = r_i + k \times p_i + q$
  • NOP (Number of Operations): $d_i = r_i + k \times n_i$
  • RDM, JIQ, JIS: Ngày hoàn thành ngẫu nhiên hoặc dựa trên hàng đợi.

+-------------------------------------------------------------------------+
| Bảng: Phân loại các mô hình ấn định ngày hoàn thành (Gordon et al., 2002)|
+----------+----------------------------+---------------------------------+
| Mô hình  | Ý nghĩa                    | Công thức ngày hoàn thành ($d_i$)|
+----------+----------------------------+---------------------------------+
| CON      | Constant flow allowance    | $d_i = d$                       |
| SLK      | Slack                      | $d_i = p_i + q$                 |
| TWK      | Total work                 | $d_i = k \times p_i$            |
| PPW      | Processing plus wait       | $d_i = k \times p_i + q$        |
| NOP      | Number of operations       | $d_i = k \times n_i$            |
+----------+----------------------------+---------------------------------+

Phương pháp nghiên cứu

• Phân tích độ phức tạp tính toán: Chứng minh các bài toán thuộc lớp P, NP-khó theo nghĩa thông thường (NP-hard in the ordinary sense) hoặc NP-khó theo nghĩa mạnh (strongly NP-hard) thông qua các phép quy dẫn đa thức (polynomial reduction) từ các bài toán đã biết như Phân hoạch (Partition), 3-Phân hoạch (3-Partition), hay Tổng tập con (Subset Sum).
• Quy hoạch động (Dynamic Programming): Xây dựng các phương trình đệ quy trạng thái để tìm lời giải tối ưu toàn cục với độ phức tạp thời gian đa thức hoặc giả đa thức.
• Quy hoạch tuyến tính và Quy về bài toán gán (Assignment Problem): Đối với các bài toán có thời gian xử lý bằng nhau ($p_i = p$), cấu trúc ma trận chi phí được thiết lập để giải bằng thuật toán gán (Hungarian algorithm) trong thời gian đa thức $O(n^3)$.
• Thiết kế sơ đồ xấp xỉ: Xây dựng sơ đồ xấp xỉ thời gian đa thức (PTAS) và đa thức hoàn toàn (FPTAS) dựa trên kỹ thuật làm tròn dữ liệu đầu vào (rounding-the-input-data) và tỉa không gian trạng thái (trimming-the-state-space).

Nội dung chính theo từng chương

Chương 1: Giới thiệu về lập lịch đúng hạn (Introduction à l’ordonnancement juste-à-temps)

Chương 1 thiết lập khung lý thuyết tổng quan về sản xuất Đúng hạn (JàT), phân loại các tiêu chuẩn tối ưu phi chính quy, và làm rõ bài toán xác định thời điểm tối ưu (optimal timing problem) khi xuất hiện thời gian chết (idle time / temps mort) giữa các công việc. Chương này cũng phân loại các lớp xấp xỉ đa thức (APX, PTAS, FPTAS) dựa trên định nghĩa sai số tương đối $\epsilon$ và tỷ số hiệu năng $R(I, A)$.

+----------------------------------------------------------------------------------------------------+
| Bảng: Khung các bài toán lập lịch JàT được nghiên cứu trong Phần I (Bảng 1.2 trong luận án)        |
+----------+------------------------------+---------------------------+------------------------------+
| Chương   | Tiêu chuẩn mục tiêu          | $d_i = d$ (cho trước)     | $d_i \in D, |D|=k$ (cho trước)|
|          |                              | Không hạn chế / Hạn chế   | $k$ cố định                  |
+----------+------------------------------+---------------------------+------------------------------+
| Chương 2 | $\sum w_i T_i$               | $1; P_m; Q_m$             | $P_m; Q_m$                   |
| Chương 3 | $\sum (\alpha_i E_i + \beta_i T_i)$ | $1; P_m; Q_m$      | $P_m; Q_m$                   |
| Chương 4 | $\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$ | $1; P_m; Q_m$ | $1; P_m$              |
+----------+------------------------------+---------------------------+------------------------------+

Chương 2: Độ trễ có trọng số với ngày hoàn thành cho trước (Retard pondéré avec une date de fin donnée)

Chương 2 tập trung vào bài toán cực tiểu hóa tổng độ trễ có trọng số $\sum w_i T_i$ khi các công việc có chung ngày hoàn thành $d$.

+-----------------------------------------------------------------------------------------------------+
| Bảng: Tổng quan tài liệu về độ phức tạp của bài toán cực tiểu hóa độ trễ (Bảng 2.1 & 2.2 luận án)    |
+--------------------------------------------+-----------------------------------+--------------------+
| Bài toán                                   | Phương pháp & Độ phức tạp         | Nguồn trích dẫn    |
+--------------------------------------------+-----------------------------------+--------------------+
| $1|p_i = p|\sum w_i T_i$                   | Đa thức                           | [154]              |
| $P_m|p_i = p, r_i|\sum T_i$                | Đa thức                           | [21]               |
| $Q|p_i = p|\sum w_i T_i$                   | Đa thức - Bài toán gán $O(n^3)$   | [154]              |
| $1|w_i = k p_i|\sum w_i T_i$               | NP-khó thông thường; DP $O(n^2 P)$| [12]               |
| $1|d_i = d|\sum w_i T_i$                   | NP-khó thông thường; DP $O(n^2 d)$| [226], [150]       |
| $1|d_i = d|\sum w_i T_i$                   | FPTAS $O(n^6 / \epsilon^3)$       | [133]              |
| $P_m|d_i = d|\sum w_i T_i$                 | Thuộc $NP \setminus APX$          | [141]              |
| $1|d_i \in D, |D|=l|\sum w_i T_i$          | FPTAS                             | [135]              |
+--------------------------------------------+-----------------------------------+--------------------+

Chương này phân tích thuật toán quy hoạch động cổ điển của Lawler và Moore (1969) với hàm đệ quy $f(i, t)$ biểu diễn tổng chi phí trễ của $i$ công việc đầu tiên hoàn thành trước hoặc tại thời điểm $t$. Luận án chứng minh rằng việc mở rộng trực tiếp công thức đệ quy này sang bài toán nhiều máy song song không hiển nhiên do trạng thái phụ thuộc vào cấu hình vector thời gian hoàn thành trên từng máy. Từ đó, tác giả xây dựng thuật toán quy hoạch động mới giải quyết bài toán trên hệ thống $m$ máy song song giống hệt ($P_m$) và $m$ máy song song đồng nhất ($Q_m$), đồng thời mở rộng cho tập hữu hạn các ngày hoàn thành ($d_i \in D, |D|=l$).

Chương 3: Chi phí sớm và trễ có trọng số với các ngày hoàn thành cho trước (Avance et retard pondérés avec dates de fin données)

Chương 3 giải quyết bài toán cực tiểu hóa tổng chi phí sớm và trễ $\sum (\alpha_i E_i + \beta_i T_i)$ với ngày hoàn thành cho trước.

• Trường hợp thời gian xử lý bằng nhau ($p_i = p$):
  • Luận án chứng minh bài toán trên máy đơn với một ngày hoàn thành chung, hai ngày hoàn thành, hoặc một họ $k$ ngày hoàn thành ($d_i \in D, |D|=k$) đều có thể mô hình hóa chính xác dưới dạng bài toán gán (Assignment Problem) thông qua việc xác định ma trận chi phí vị trí và giải được trong thời gian đa thức $O(n^3)$.
  • Kết quả này được mở rộng thành công cho hệ thống máy song song đồng nhất ($Q_m$).
• Trường hợp thời gian xử lý bất kỳ ($p_i$ tùy ý):
  • Tác giả xây dựng Sơ đồ xấp xỉ thời gian đa thức (PTAS) cho bài toán trên máy đơn ($1|d_i=d|\sum (\alpha_i E_i + \beta_i T_i)$).
  • Mở rộng sơ đồ xấp xỉ cho hệ thống $m$ máy song song giống hệt ($P_m|d_i=d|\sum (\alpha_i E_i + \beta_i T_i)$) với $m$ cố định.

Chương 4: Chi phí sớm và trễ có trọng số với các ngày hoàn thành có thể kiểm soát (Avance et retard pondérés avec dates de fin contrôlables)

Chương 4 khảo sát bài toán khi ngày hoàn thành chung $d$ là một biến quyết định cần xác định đồng thời với thứ tự lập lịch, hàm mục tiêu bổ sung thêm chi phí ấn định ngày hoàn thành: $\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$.

• Trường hợp thời gian xử lý bằng nhau ($p_i = p$): Đề xuất các thuật toán đa thức tối ưu thông qua kỹ thuật gán vị trí và xác định vị trí tối ưu của ngày hoàn thành $d$ đối với máy đơn, máy song song giống hệt ($P_m$) và máy song song đồng nhất ($Q_m$).
• Trường hợp thời gian xử lý bất kỳ: Thiết lập các cấu trúc tính chất nghiệm tối ưu, phân tích chặn dưới (lower bound) và chặn trên (upper bound), đồng thời đề xuất thuật toán giải chính xác và thuật toán xấp xỉ trên máy đơn và máy song song.

Chương 5: Kết luận và triển vọng của phần thứ nhất (Conclusion et perspectives de la première partie)

Tổng kết toàn bộ các kết quả đạt được về độ phức tạp, thuật toán quy hoạch động, thuật toán gán đa thức và các sơ đồ xấp xỉ PTAS/FPTAS cho lớp bài toán lập lịch JàT có ngày hoàn thành chung cho trước và kiểm soát được.

Chương 6: Giới thiệu về lập lịch các công việc can thiệp (Introduction à l’ordonnancement des travaux interférants)

Chương 6 mở đầu phần II của luận án, trình bày bối cảnh mô hình hóa các công việc can thiệp độc lập. Khác với lập lịch đa mục tiêu truyền thống nơi tất cả công việc đều đóng góp như nhau vào mọi tiêu chuẩn, mô hình công việc can thiệp xem xét:

• Một tiêu chuẩn toàn cục được tính trên toàn bộ tập công việc $N$.
• Một hoặc nhiều tiêu chuẩn cục bộ chỉ áp dụng trên tập con công việc $N_1 \subset N$.

Chương này định nghĩa bài toán dưới ba hướng tiếp cận giải quyết đa mục tiêu: tiếp cận $\epsilon$-ràng buộc ($1|\epsilon|F_1(N)/F_2(N_1)$), kết hợp tuyến tính ($1||F_l(F_1(N), F_2(N_1))$) và quy hoạch mục tiêu (goal programming).

Chương 7: Bài toán lập lịch trên một máy đơn (Problème d’ordonnancement à une seule machine)

Chương 7 phân tích toàn diện ranh giới độ phức tạp tính toán cho bài toán công việc can thiệp trên một máy đơn ($1$).

• Nhận diện các lớp bài toán giải được trong thời gian đa thức (Polynomial time solvable).
• Chứng minh tính NP-khó theo nghĩa thông thường (NP-hard in the ordinary sense) cho các biến thể kết hợp giữa tổng thời gian hoàn thành có trọng số $\sum w_j C_j$ và độ trễ cực đại $L_{\max}$.
• Chứng minh tính NP-khó theo nghĩa mạnh (Strongly NP-hard) cho các kết hợp phức tạp giữa các tiêu chuẩn $\sum w_j C_j(N)$ và các ràng buộc cục bộ ngặt nghèo trên $N_1$.

Chương 8: Bài toán lập lịch trên các máy song song (Problème d’ordonnancement à machines parallèles)

Chương 8 mở rộng bài toán công việc can thiệp lên hệ thống máy song song ($P_m$).

• Thiết lập các kết quả độ phức tạp tính toán cho các cấu hình đa máy.
• Đề xuất khung thuật toán quy hoạch động tổng quát (general dynamic programming formulation) áp dụng cho các cặp hàm mục tiêu:
  1. $\sum C_j(N_1)$ và $\sum C_j(N)$
  2. $\sum w_j C_j(N_1)$ và $C_{\max}(N)$
  3. $\sum w_j C_j(N)$ và $C_{\max}(N_1)$
  4. $C_{\max}(N)$ và $C_{\max}(N_1)$

Chương 9: Kết luận và triển vọng của phần thứ hai (Conclusion et perspectives de la seconde partie)

Đánh giá tổng kết các đóng góp lý thuyết trong việc định hình mô hình công việc can thiệp, tính đầy đủ của bản đồ độ phức tạp và hiệu quả tính toán của các thuật toán quy hoạch động đã thiết kế.

Kết quả và những đóng góp mới

Luận án đạt được những kết quả cụ thể sau:

1. Về mặt lý thuyết độ phức tạp:

   • Hoàn thiện bảng phân loại độ phức tạp tính toán cho bài toán cực tiểu hóa trễ có trọng số $\sum w_i T_i$ và sớm - trễ kết hợp $\sum (\alpha_i E_i + \beta_i T_i)$ trên máy đơn và máy song song ($P_m, Q_m$).
   • Thiết lập bản đồ độ phức tạp chi tiết (đa thức, NP-khó thông thường, NP-khó mạnh) cho bài toán lập lịch công việc can thiệp trên máy đơn và hệ thống máy song song với các cặp tiêu chuẩn mục tiêu $\sum C_j$, $\sum w_j C_j$, $C_{\max}$, và $L_{\max}$.

2. Về mặt thiết kế thuật toán:

   • Xây dựng thuật toán quy hoạch động giải quyết bài toán $P_m|d_i=d|\sum w_i T_i$ và mở rộng cho trường hợp máy song song đồng nhất $Q_m$ cũng như tập các ngày hoàn thành $d_i \in D, |D|=k$, khắc phục khoảng trống từ công trình của Lawler và Moore (1969).
   • Đề xuất phương pháp chuyển đổi các bài toán JàT có thời gian xử lý bằng nhau ($p_i = p$) về dạng bài toán gán, giải quyết tối ưu trong thời gian đa thức $O(n^3)$ cho cả trường hợp một ngày hoàn thành, hai ngày hoàn thành, và họ ngày hoàn thành.
   • Thiết lập các sơ đồ xấp xỉ thời gian đa thức (PTAS) cho bài toán sớm - trễ kết hợp trên máy đơn và hệ thống $m$ máy song song giống hệt.
   • Xây dựng khung quy hoạch động tổng quát giải bài toán công việc can thiệp trên máy song song cho nhiều cấu hình mục tiêu khác nhau.

Hạn chế và hướng nghiên cứu tiếp

Dựa trên phạm vi và các nội dung được trình bày trong luận án, các hạn chế và hướng mở rộng nghiên cứu bao gồm:

• Thời điểm đến của công việc (Release dates): Phần lớn các mô hình trong luận án giả định tất cả công việc đều sẵn sàng tại thời điểm ban đầu ($r_i = 0$). Việc mở rộng bài toán sang trường hợp thời điểm đến tùy ý ($r_i \ge 0$) sẽ làm thay đổi cấu trúc không gian nghiệm và cần các kỹ thuật tối ưu mới.
• Thời gian chuyển đổi/cài đặt (Setup times): Luận án chưa xét tới thời gian cài đặt máy phụ thuộc hoặc không phụ thuộc vào thứ tự công việc giữa các lần chuyển đổi.
• Cấu hình nhà xưởng phức tạp: Nghiên cứu tập trung chủ yếu vào máy đơn và máy song song; việc phát triển các mô hình Đúng hạn và công việc can thiệp cho hệ thống chuyền sản xuất (Flow shop), xưởng mở (Open shop) hay xưởng công việc (Job shop) là hướng đi tiếp theo.
• Số lượng tập tác tử can thiệp: Mô hình công việc can thiệp trong luận án khảo sát chủ yếu trên hai tập ($N$ và $N_1$). Hướng mở rộng là xem xét $k$ tập công việc can thiệp ($N_1, N_2, \dots, N_k$) cạnh tranh đồng thời trên cùng tài nguyên.

Giá trị tham khảo

Luận án là tài liệu tham khảo cho:

• Nghiên cứu sinh và nhà nghiên cứu trong lĩnh vực Tối ưu hóa tổ hợp, Nghiên cứu vận hành và Khoa học máy tính lý thuyết: Tham khảo phương pháp chứng minh độ phức tạp tính toán, kỹ thuật quy đổi bài toán sang dạng bài toán gán, và phương pháp thiết kế sơ đồ xấp xỉ đa thức (PTAS/FPTAS).
• Giảng viên đại học: Sử dụng làm tài liệu giảng dạy chuyên đề cao học về Lý thuyết lập lịch, Quy hoạch động nâng cao và Lập lịch đa mục tiêu/đa tác tử.
• Kỹ sư tối ưu hóa và nhà phân tích chuỗi cung ứng: Tham khảo các mô hình toán học và nguyên lý cân bằng sớm - trễ trong việc ấn định ngày giao hàng (due date assignment) và lập lịch sàn sản xuất theo triết lý JàT.

Câu hỏi thường gặp

1. Tại sao hàm mục tiêu trong lập lịch Đúng hạn (JàT) lại được gọi là tiêu chuẩn phi chính quy (non-regular criterion)?
Một tiêu chuẩn được gọi là chính quy nếu giá trị hàm mục tiêu không tăng khi thời gian hoàn thành của các công việc giảm xuống. Trong bài toán JàT với chi phí sớm và trễ kết hợp ($\sum (\alpha_i E_i + \beta_i T_i)$), việc đẩy thời gian hoàn thành của một công việc về sớm hơn thời điểm $d_i$ sẽ làm tăng chi phí độ sớm ($E_i$). Do đó, tiêu chuẩn này là phi chính quy, và nghiệm tối ưu có thể yêu cầu chèn thêm thời gian chết (idle time) có chủ đích giữa các công việc liên tiếp.

2. Thuật toán quy hoạch động của Lawler và Moore (1969) gặp khó khăn gì khi mở rộng sang hệ thống máy song song?
Lawler và Moore đề xuất hàm đệ quy $f(i, t)$ tính toán trên một biến thời gian vô hướng $t$ đại diện cho thời điểm hoàn thành trên một máy duy nhất. Khi chuyển sang $m$ máy song song, trạng thái hoàn thành của hệ thống không còn là một giá trị vô hướng mà trở thành một vector $m$ chiều biểu thị thời điểm kết thúc trên từng máy $(t_1, t_2, \dots, t_m)$. Điều này làm tăng độ phức tạp không gian trạng thái và đòi hỏi cấu trúc đệ quy mới như luận án đã xây dựng.

3. Tại sao các bài toán JàT với thời gian xử lý bằng nhau ($p_i = p$) lại giải được bằng bài toán gán trong thời gian đa thức?
Khi tất cả công việc có thời gian thực thi như nhau, độ sớm $E_i$ và độ trễ $T_i$ của một công việc chỉ phụ thuộc vào vị trí xử lý cụ thể mà công việc đó được phân bổ trên trục thời gian so với ngày hoàn thành mong muốn $d$. Chi phí khi xếp công việc $J_i$ vào vị trí thứ $k$ là hoàn toàn xác định trước, cho phép chuyển bài toán về bài toán gán tuyến tính (linear assignment problem) và giải bằng thuật toán Hungary với độ phức tạp $O(n^3)$.

4. Khái niệm bài toán lập lịch công việc can thiệp (Interfering Jobs) khác biệt như thế nào so với lập lịch đa mục tiêu truyền thống?
Trong lập lịch đa mục tiêu truyền thống, tất cả công việc thuộc tập $N$ đều đóng góp vào việc tính toán tất cả các hàm mục tiêu (ví dụ cực tiểu hóa đồng thời $C_{\max}(N)$ và $\sum T_i(N)$). Trong bài toán công việc can thiệp, một hàm mục tiêu được đánh giá trên toàn bộ tập công việc $N$, nhưng các hàm mục tiêu hoặc ràng buộc khác chỉ áp dụng riêng cho một tập con công việc xác định ($N_1 \subset N$), phản ánh sự can thiệp và cạnh tranh tài nguyên giữa các nhóm công việc khác nhau.

Kết luận

Luận án tiến sĩ của Nguyen Huynh Tuong đã phân tích các bài toán lập lịch tổ hợp phi chính quy trong sản xuất Đúng hạn và môi trường công việc can thiệp. Tác giả đã giải quyết các bài toán trên cấu hình máy đơn, máy song song giống hệt và máy song song đồng nhất thông qua việc phân loại độ phức tạp, xây dựng thuật toán quy hoạch động chính xác, mô hình hóa bài toán gán đa thức và thiết lập các sơ đồ xấp xỉ PTAS. Các kết quả này đóng góp cơ sở lý thuyết và thuật toán cho lĩnh vực tối ưu hóa lập lịch đa mục tiêu và lập lịch sản xuất hiện đại.

Trích đoạn nội dung tài liệu

UNIVERSITÉ FRANÇOIS-RABELAIS DE TOURS ÉCOLE DOCTORALE : SANTÉ, SCIENCE, ET TECHNOLOGIES Laboratoire d’Informatique THÈSE présentée par : Nguyen HUYNH TUONG soutenue le : 17 juin 2009 pour obtenir le grade de : Docteur de l’Université François-Rabelais de Tours Discipline/Spécialité : INFORMATIQUE COMPLEXITÉ ET ALGORITHMES POUR L’ORDONNANCEMENT MULTICRITERE DE TRAVAUX INDÉPENDANTS : PROBLÈMES JUSTE-À-TEMPS ET TRAVAUX INTERFÉRANTS THÈSE dirigée par : SOUKHAL Ameur Maître de conférences, Université François Rabelais de Tours BILLAUT Jean-Charles Professeur, Université François Rabelais de Tours RAPPORTEURS : BAPTISTE Philippe Chargé de Recherche CNRS, HDR (Paris) CHRÉTIENNE Philippe Professeur, Université Pierre et Marie Curie (Paris VI) JURY : AGNETIS Alessandro Professeur, Université de Sienne, Italie BAPTISTE Philippe Chargé de Recherche CNRS, HDR (Paris) BILLAUT Jean-Charles Professeur, Université François Rabelais de Tours CARLIER Jacques Professeur, Université de Technologie de Compiègne CHRÉTIENNE Philippe Professeur, Université Pierre et Marie Curie (Paris VI) NERON Emmanuel Professeur, Université François Rabelais de Tours SOUKHAL Ameur Maître de conférences, Université François Rabelais de Tours À ma famille : mes parents, ma femme et ma fille Remerciements Les travaux réalisés au cours de cette thèse ont été effectués au sein du Laboratoire d’Informatique de l’Université de François Rabelais de Tours (EA 2101), dans l’équipe Ordonnancement et Conduite. Je souhaite tout en premier lieu remercier Ameur Soukhal, Maître de Conférences à l’Ecole Polytech’Tours, qui a encadré cette thèse. Pendant ces trois années, il a su orien- ter aux bons moments mes travaux de recherches en me faisant découvrir l’ordonnan- cement au travers de son regard novateur et critique. Ses conseils et ses commentaires précieux m’ont permis de surmonter les difficulté et de progresser.

Je tiens à exprimer mes remerciements à Jean-Charles Billaut, Professeur de l’Ecole Polytech’Tours et également mon directeur de thèse, pour ses encouragements, ses conseils et sa confiance. J’adresse tous mes sincères remerciements à Philippe Chrétienne, Professeur de l’Université Pierre et Marie Curie (Paris VI), et à Philippe Baptiste, Professeur de l’École Polytechnique (LIX), qui m’ont fait l’honneur d’accepter d’être rapporteurs de mes tra- vaux. Mes chaleureux remerciements s’adressent à Jacques Carlier, Professeur de l’Uni- versité de Technologie de Compiègne d’avoir accepté d’être examinateur et président du jury. Je remercie également les autres membres du jury qui ont accepté de juger ce travail : Alessandro Agnetis, Professeur de l’Université de Siena (Italy) et Emmanuel Néron, Professeur de l’Université François Rabelais de Tours.

Je remercie le Ministère de l’Éducation et la Recherche pour le financement qui m’a été accordé pour le bon déroulement de ma thèse. Plus largement, je voudrais remercier les différentes personnes du Laboratoire d’In- formatique et du Département Informatique de Polytech’Tours auprès desquelles je suis souvent venue chercher conseil et avec lesquelles j’ai partagé de très bons mo- ments, tant pour le travail que pour des instants de détente. Grâce à un partage et une bonne convivialité entre les membres de l’équipes, j’ai eu l’opportunité d’effectuer ma thèse dans d’excellente condition. Parmi ceux qui ont contribué à mon travail, je remer- cie tout spécialement Jean-Louis Bouquard et Vincent T’Kindt pour les conseils scienti- fiques et leur supports.

Dans ces remerciements je n’oublie jamais les autres membres de l’équipe qui ont fait de mon séjour, une période très agréable et enrichissante. Je pense en particulier à Christian Proust (Directeur de l’Ecole Polytech’Tours), Patrick Martineau, Christophe Lenté, Claudine Tacquard, Carl Esswein, Geoffey Vilcot, Cédric Pessan, Mathieu Pérotin, Cédric Mocquillon, Mathieu Rouleau, Yanick Kergosen, Gaël Sauvanet, et Rabah Belaid. Mes remerciements sont adressés également aux étudiants du cycle d’ingénieur qui sont intervenus dans mes projets de recherche : Brien Lit- i teaut, Paul Vignard, Corentin Del’homme, Dan Shao, Zangou Dao, Laurent Miscopein et Daudé Guillaume. Enfin, mes remerciements vont à ma femme My-Dung ainsi qu’à nôtre petite fille Gia-An, qui sont à mes côtés depuis le début et qui m’ont toujours écoutées et accom- pagnées dans cette aventure avec beaucoup de patience et surtout d’amour.

Résumé Nous abordons dans cette thèse des problèmes d’ordonnancement de travaux in- dépendants sur une machine ou sur des machines parallèles. Plus précisément, nous abordons deux catégories de problèmes : 1. les problèmes d’ordonnancement de type juste-à-temps : il s’agit de déterminer un ordonnancement de sorte que les travaux se terminent le plus près possible de leur date de fin souhaitée. On considère le cas où la date de fin souhaitée commune est connue et le cas où elle est à déterminer.

De nouveaux algorithmes exacts sont proposés - gloutons et programmes dynamiques -. Des schémas d’ap- proximation sont élaborés. les problèmes d’ordonnancements de travaux interférants : il s’agit de déterminer un ordonnancement qui permet d’optimiser un critère pour la globalité des tra- vaux à effectuer, sachant que la solution trouvée doit permettre également l’opti- misation d’un autre critère défini uniquement sur un sous-ensemble des travaux. Il s’agit ici d’un nouveau problème d’ordonnancement multicritère, différent de la notion classique, et qui se rapproche des problèmes de type "multi-agent schedu- ling" ou "interfering job sets".

Les approches considérées pour trouver une solution non dominée sont l’approche ε-contrainte, la combinaison linéaire de critères et le goal programming. De nouveaux résultats de complexité sont montrés et des al- gorithmes polynomiaux/pseudo-polynomiaux sont développés pour le calcul de cette solution non dominée. Mots-clés : ordonnancement, une machine, machines parallèles, juste-à-temps, tra- vaux interférants, complexité, programmation dynamique, schéma d’approximation iii Abstract In this thesis we consider scheduling problems of independent jobs on a single ma- chine or on parallel machines. More precisely, we tackle two kinds of problems : 1.

just-in-time scheduling problems : it aims to determine a schedule so that a job completes as close as possible to its due date. We consider the case where the common due date is known and the case where the common due date has to be fixed. New exact algorithms based on greedy algorithms and dynamic program- ming are proposed. Approximation schemes are given.

scheduling problems with interfering jobs : the aim is to determine a schedule that optimizes a criterion for the whole set of jobs and so that the solution optimizes another objective only for a subset of jobs. It is here a new multi-criteria schedu- ling problem, different from the classical notion, which is related to "multi-agent” or to "interfering job sets” scheduling problems. The approaches considered for finding a non-dominated solution are the ε-constraint approach, the linear com- bination of criteria and the goal programming approach. New complexity results are proposed and polynomial/pseudo-polynomial algorithms are developed for the calculation of the non-dominated solution.

Keywords : scheduling, single machine, parallel machines, just-in-time, interfering jobs, complexity, dynamic programming, approximation scheme v Table des matières Introduction générale 1 I Ordonnancement juste-à-temps à date due commune 5 1 Introduction à l’ordonnancement juste-à-temps 7 1.1 Systèmes "Juste-à-temps" .2 Mesurer l’avance/retard d’un travail .3 Mesurer le coût total d’avances et retards des travaux .1 Fonction de coût linéaire continue .4 Dates de fin souhaitée .1 Date de fin commune donnée .2 Famille de dates de fin commune donnée .3 Dates de fin commune contrôlable .4 Dates de fin souhaitées généralisées .5 Complexité et approximation polynomiale .1 Approximation et garanties de performances .2 Schémas d’approximation polynomiaux .6 Problèmes d’ordonnancement Juste-à-temps abordés. 24 2 Retard pondéré avec une date de fin donnée 25 2.2 État de l’art .1 Approximabilité du retard pondéré .2 Remarques sur programme dynamique de Lawler et Moore .3 Problème d’ordonnancement à une seule machine .1 Nouveau programme dynamique .4 Problème d’ordonnancement à machines identiques .1 Programme dynamique pour le cas de machines identiques .2 Extension au cas de machines uniformes. 46 3 Avance et retard pondérés avec dates de fin données 49 3.2 Propriétés pour le cas d’une date de fin souhaitée commune .3 Durées opératoires identiques .1 Une seule machine avec une date de fin souhaitée commune .2 Une seule machine avec deux dates de fin souhaitées .3 Une seule machine avec famille de dates de fin souhaitées .4 Machines uniformes avec famille de dates de fin souhaitées .4 Durées opératoires quelconques .1 PTAS pour le cas d’une seule machine .2 PTAS pour le cas de m machines parallèles identiques. 87 4 Avance et retard pondérés avec dates de fin contrôlables 91 4.1 Quelques notations spécifiques à ce chapitre .2 Durées opératoires identiques .1 Une seule machine avec une seule date de fin souhaitée .2 Machines identiques avec famille de dates de fin souhaitées .3 Machines uniformes avec une seule date de fin souhaitée .3 Durées opératoires quelconques .1 Une seule machine avec une seule date de fin souhaitée .2 Machines parallèles avec une seule date de fin souhaitée.

127 5 Conclusion et perspectives de la première partie 129 II Ordonnancement de travaux interférant indépendants 133 6 Introduction à l’ordonnancement des travaux interférants 135 6.1 Motivation et contexte de travail .2 Brève introduction de l’ordonnancement multi-critère .2 Classes de méthodes de résolution .3 Définition de l’ordonnancement avec des travaux interférants .4 État de l’art .5 Intérêt de l’étude. 146 7 Problème d’ordonnancement à une seule machine 149 7.2 Problèmes résolus en temps polynomial .3 Problèmes NP-difficiles au sens ordinaire .4 Problèmes NP-difficiles au sens fort. 169 8 Problème d’ordonnancement à machines parallèles 171 8.2 Résultats de complexité .4 Algorithme de programmation dynamique .1 Formulation générale de programmation dynamique .2 Une application de la formulation générale .3 Problèmes avec les fonction objectifs ∑ Cj (N1 ) et ∑ Cj (N ) .4 Problèmes avec les fonction objectifs ∑ w j Cj (N1 ) and Cmax (N ) .5 Problèmes avec les fonction objectifs ∑ w j Cj (N ) and Cmax (N1 ) .6 Problèmes avec les fonction objectifs Cmax (N ) et Cmax (N1 ). 180 9 Conclusion et perspectives de la seconde partie 181 Conclusion générale et perspectives 183 Liste des tableaux 1.1 Classification des problèmes d’ordonnancement à affecter date de fin [126] 18 1.2 Tableau de problèmes abordés .1 État de l’art sur la minimisation des retards .2 État de l’art sur la minimisation des retards .3 Durées opératoires, dates de fin souhaitées, et pénalités .1 État de l’art sur la minimisation des avances et des retards .2 Durées opératoires, dates de fin souhaitées, et pénalités d’avance/retard 59 3.3 Durées opératoires et les poids (pénalités d’avance et de retard) des travaux 73 4.1 Problèmes JàT avec affectation de la date de fin souhaitée .2 Performance de la borne inférieure par rapport à une borne supérieure .1 Bilan et perspectives .1 Résultats de complexité de l’ordonnancement multi-agent [121] .1 Ordonnancement avec travaux interférants sur une seule machine [118] 150 8.1 Ordonnancement avec travaux interférants sur machines parallèles.

172 xi Table des figures 1.1 Calcul de l’avance en fonction de date de fin souhaitée .2 Calcul de l’avance en fonction de la promptitude .3 Calcul de l’avance en fonction de date de début souhaitée .4 Calcul du retard .5 Fonction de coût d’avance/retard linéaire et continue .6 Juste-à-temps : critère non-régulièr .1 Cas d’une seule machine - position du nouveau travail en retard .2 Cas d’une seule machine - nouvelle fonction de récurrence .3 Cas d’une seule machine - travail Ji est en avance .4 Cas d’une seule machine - travail Ji est en retard .6 Fonction récurrente du cas de machines parallèles .7 Cas 1 - Ji est en avance sur M1 .8 Cas 2 - Ji est en retard sur M1 .9 Cas 3 - Ji est en avance sur M2 .10 Cas 4 - Ji est en retard sur M2 .11 Algorithme WTP2CDD .12 Algorithme WTQ2CDD .1 Positions des travaux sur une machine avec une date due donnée .2 Matrice des coûts d’affectation des travaux .3 Exemple avec 5 travaux .4 Matrice d’affectation avec 5 travaux .5 Matrice d’affectation avec 5 travaux et (δ1 , δ2 ) = (0, 3) .6 Solution optimale correspondant au Cas (a) .7 Matrice d’affectation avec 5 travaux et (δ1 , δ2 ) = (1, 2) .8 Solution optimale selon le cas (b) .9 Exemple avec temps morts dans [ D0 , D1 ] et ] D1 , D2 ] et après D2 .