# Réduction polynomiale pour l'ordonnancement Juste-à-Temps avec une date de fin souhaitée non-restrictive ou contrôlable

Ameur Soukhal, Nguyen Huynh Tuong

► To cite this version:

Ameur Soukhal, Nguyen Huynh Tuong. Réduction polynomiale pour l'ordonnancement Juste-à-Temps avec une date de fin souhaitée non-restrictive ou contrôlable. Congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Université de Picardie Jules Verne Pôle Universitaire Cathédrale Amiens, France, Mar 2024, Amiens, France. hal-04827560

HAL Id: hal-04827560

https://hal.science/hal-04827560v1

Submitted on 9 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Réduction polynomiale pour l'ordonnancement Juste-à-Temps avec une date de fin souhaitée non-restrictive ou contrôlable

Ameur SOUKHAL¹, Nguyen HUYNH TUONG²

¹ Université de Tours, Laboratoire d'Informatique Fondamentale et Appliquée de Tours LIFAT
ROOT, France(2)

ameur.soukhal@univ-tours.fr

² Industrial university of Ho Chi Minh city, Vietnam

htnguyen@iuh.edu.vn

**Mots-clés** : Ordonnancement JàT, Réduction, algorithmes polynomiaux, FPTAS, PTAS.

## 1 Introduction

Un des problèmes de juste-à-temps (JàT) classiques est le modèle pour lequel tous les travaux ont une date de fin souhaitée commune $d_i = d$, introduit par Kanet en 1981. Un tel modèle correspond par exemple à un système d'assemblage où les composants d'un produit devraient être prêts en même temps, ou bien lorsqu'il s'agit d'une commande d'un client qui doit être livrée à une date prévue à l'avance.

L'avance d'un travail $J_i$ est mesurée par $E_i = \max(0, d - C_i)$ ou son retard est donné par $T_i = \max(0, C_i - d)$ avec $C_i$ sa date d'achèvement.

Principalement deux problèmes d'ordonnancement sur une seule machine sont étudiés :

- Problèmes d'ordonnancement JàT avec date de fin souhaitée non-restrictive : lorsque les travaux peuvent être débutés avant la date zéro ou lorsque nous avons $d = \sum_{i=1}^n p_i$, avec $p_i$ la durée opératoire du travail $J_i$. Le problème est noté $1|d_i = d, \text{unres}| \sum (\alpha_i E_i + \beta_i T_i)$ où unres indique que $d$ est non restrictive.

- Problème d'ordonnancement avec dates de fin souhaitées contrôlables, noté CON, où $d$ est une variable de décision. Le problème est ainsi noté $1|CON, d_i = d| \sum (\alpha_i E_i + \beta_i T_i + \gamma d)$ où contrairement au cas précédent, $d$ est une variable de décision pour laquelle un coût $\gamma$ est associé.

Nous examinons aussi le cas symétrique lorsque : $\alpha_i = \beta_i = w_i, \forall i = 1, \dots, n$.

## 2 CON vs UNRES : cas symétrique

Pour le cas symétrique avec une seule date de fin souhaitée commune non-restrictive, le problème d'ordonnancement $1|d_i = d, \text{unres}| \sum (w_i E_i + w_i T_i)$ est montré polynomial [3] si la valeur maximale des pénalités est bornée par une fonction en $n$. Dans le cas général, $1|d_i = d, \text{unres}| \sum (w_i E_i + w_i T_i)$ accepte un FPTAS [4].

Par une réduction polynomial, nous avons montré que le problème $1|CON, d_i = d| \sum (w_i E_i + w_i T_i + \gamma d)$ présente les mêmes propriétés, à savoir si $w_i$ est bornée par une fonction en $n$ le problème est polynomial, sinon il accepte un FPTAS.

## 3 Due date commune non restrictive

Considérons le problème d'ordonnancement $1|d_i = d, \text{unres}| \sum (\alpha_i E_i + \beta_i T_i)$ connu NP-difficile. Dans cette communication, nous avons montré que ce problème accepte un schéma d'approximation polynomial PTAS. L'idée globale de notre démarche est basée sur le fait
qu'une solution optimale a une structure 'V-shape' [2]. Ainsi, il suffit de déterminer l'ensemble des travaux en avance pour avoir une solution. Pour cela, deux étapes principales sont nécessaires. La première a pour objectif de simplifier la taille des entrées en utilisant la technique dite "rounding technic" [1]. Elle consiste à transformer les pénalités d'avance/retard et les durées opératoires des travaux en des puissances entières de $(1 + \varepsilon)$. L'objectif est de réduire la taille de l'instance en prenant une décision pour certains travaux à exécuter en avance et ceux à exécuter en retard. Nous qualifions ces travaux par des travaux "décidables" moyennant un coût supplémentaire engendré par de telles décisions. Nous montrons que ce coût est borné par $(1 + O(\varepsilon))$.

La deuxième étape consiste à chercher la meilleure affectation des travaux de l'ensemble que nous qualifions "non-décidables". Sous l'hypothèse $\alpha_{min} \le \alpha_i \le \alpha_{max}, \forall i = 1...n$ et $\alpha_{max}/\alpha_{min} \le 2$, nous montrons qu'une énumération totale des sous-ensembles de travaux en avance a une complexité bornée par $2^{O(\log_2(1/\varepsilon)/\varepsilon^4)}$. Un programme dynamique pour le PTAS est proposé.

# 4 Date de fin commune contrôlable : CON

Le schéma de réduction polynomial que nous présenterons et avoir développé nous a permis de généraliser ce résultat au cas de date de fin souhaitée contrôlable et d'en déduire la proposition suivante.

**Proposition 1** *Le problème d'ordonnancement $1|CON, d_i = d|\sum(\alpha_i E_i + \beta_i T_i + \gamma d)$ accepte un PTAS en $O_\varepsilon(n^2)$ sous l'hypothèse $\alpha_{min} \le \alpha_i \le \alpha_{max}, \forall i = 1...n$ et $\alpha_{max}/\alpha_{min} \le 2$.*

# 5 Synthèse des résultats

Nous présenterons une synthèse de résultats obtenus sur l'étude des problèmes d'ordonnancement JàT avec date de fin souhaitée commune non-restrictive ou contrôlable. Ces résultats sont de deux natures :

- Solutions optimales : nous avons généralisé les résultats connus dans la littérature pour un problème à l'autre, c'est le cas du problème JàT symétrique tel exposé précédemment. Nous avons également étudié un autre cas où les durées opératoires sont identiques, $1|p_i = p, d_i = d, unres|\sum(\alpha_i E_i + \beta_i T_i)$. Nous montrons que ce dernier est polynomial. En s'appuyant sur le schéma de réduction que nous avons proposé, nous déduisons ainsi que le $1|CON, p_i = p, d_i = d|\sum(\alpha_i E_i + \beta_i T_i + \gamma d)$ est polynomial.

- Schémas d'approximation : nous déduisons le FPTAS pour le problème CON symétrique lorsque les pénalités sont quelconques. Pour le problème $1|CON, d_i = d, unres|\sum(\alpha_i E_i + \beta_i T_i)$ nous avons montré sous certaines hypothèses que ce problème accepte un PTAS et donc ce résultat est aussi valide pour la version date de fin souhaitée contrôlable.

Notre étude a montré l'existence d'un lien fort entre ces deux classes de problèmes d'ordonnancement J-à-T : CON et UNRES même si de nature les deux problèmes ne sont pas équivalents.

# Références

[1] F. Afrati, A. Bampis, C. Kenyon and I. Milis, *A PTAS for the average weighted completion time problem on unrelated machines*. Journal of Scheduling, vol. 3, pp. 323–332, (2000).

[2] K.R. Baker and G.D. Scudder, *Sequencing with earliness and tardiness penalties : a review*, Operations Research (1990) 38, pages. 22–36.

[3] B. Jurisch, W. Kubiak and J. Jozéfowska, *Algorithms for minclique scheduling problems*, Discrete Applied Mathematics, vol. 72, pp. 115–139, (1997).

[4] M.Y. Kovalyov and W. Kubiak, *A fully polynomial approximation scheme for the weighted earlinesstardiness problem*, Operations Research, vol. 47, pp. 757-761, (1999).