Single machine semi-online scheduling for smart manufacturing

Nous étudions la valeur de l’information dans des problèmes d’ordonnancement semi-online sur machine unitaire. Nous proposons ainsi des algorithmes semi-online pour résoudre ces problèmes et nous évaluons leurs performances. Contrairement aux problèmes d’ordonnancement classiques offline où le décideur connaît toutes les caractéristiques de l’instance à ordonnancer, dans les problèmes d’ordonnancement online ou semi-online la prise de décision est effectuée sans aucune information ou uniquement avec des informations partielles sur l’instance. Notre travail consiste à distinguer les informations qui peuvent améliorer la prise de décision dans un contexte d’ordonnancement semi-online des informations qui, même disponibles, n’apportent aucune amélioration. Nous traitons principalement les problèmes semi-online dont la fonction objective est la minimisation de la somme des dates de fin des tâches sur machine unitaire. Nous commençons par étudier plusieurs modèles semi-online avec des informations partielles sur les temps de traitement des tâches. Ensuite, nous considérons le problème avec une information sur les dates d’arrivée et finalement la combinaison de l’information sur les temps de traitements et les dates d’arrivée des tâches. Pour chaque problème étudié où l’information partielle est identifiée comme utile, nous proposons un algorithme semi-online intégrant l’information dans la prise de décision. Ensuite, nous évaluons sa performance à l’aide d’une analyse de compétitivité ou par étude expérimentale comparative.We study the value of information in semi-online single machine scheduling problems. We propose semi-online algorithms to solve these problems and evaluate their performances. Unlike the classical offline scheduling problems where the decision maker knows all characteristics of the instance to be scheduled, in online scheduling problems the decision-making is performed without previous information or only with partial information about the instance. Our work consists in distinguishing information that can improve the decision-making in a semi-online scheduling context from information that, even if available, does not bring any improvement. We mainly deal with semi-online problems for minimising the total completion time on a single machine. We start by studying several semi-online models with partial information on processing times of jobs. Then, we consider the problem with information on jobs release dates and finally the combination of information on processing times and jobs release dates. For each studied problem where partial information is identified as useful, we propose a semi-online algorithm integrating the information into the decision-making. We then evaluate its performance using a competitive analysis or a comparative experimental study