Faculté des sciences et techniques de l'ingénieur STI, Section de microtechnique, Institut de microtechnique IMT (Laboratoire de production microtechnique 1 LPM1)

Dynamic scheduling for production systems operating in a random environment

Dusonchet, Fabrice ; Hongler, Max-Olivier (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2003 ; no 2825.

Ajouter à la liste personnelle
    Summary
    Due to the steady tendency to propose highly customized products and to respond to volatile (i.e random) demands, Flexible Manufacturing Systems (FMS) are now present in most shopfloors. In this thesis, flexibility in a FMS is understood as the ability of a single production cell to deliver several different types of items, say N. The production capacity is usually limited in the sense that only one or K < N type(s) of items can be simultaneously produced. Each type of item faces a specific market demand which often shows random fluctuations. To insure a high reactivity when facing such random demands, efficient production rules for the FMS are mandatory. These rules include in particular two generic entities, namely: Finished Goods Inventories. The fluctuations of i) the production flows, (due to failure-prone machines) and ii) the demand flows, can be partly absorbed by the presence of Finished Good Inventories (FIG). Such storage zones incur costs especially when serving highly customized demands. Clearly, the balance between the advantage of high reactivity on the one hand and storage costs on the other introduces complex optimization issues. The optimal solution will generally include hybrid production rules, i.e. certain types of products optimally require FIG (we call this strategy make-to-stock production), while other types require no FIG (we call this strategy make-to-order production). Dynamic Scheduling rules. The intrinsic presence of fluctuations implies that simple deterministic scheduling rules (as for example deterministic polling rules which produce each type j of items periodically during a fixed period of time Tj) may lead to a very poor performance. Clearly, an optimal production schedule will be based on both past experience and observation of the present state of the system (i.e the populations of the FIG and the instantaneous rates of the demand and production flows). Hence, any optimal scheduling rule will necessarily present a time adaptive character (i.e. real time scheduling rules). In spite of a growing usage of FMS in industry, the general problem of determining the optimal dynamic scheduling of flexible manufacturing systems remains, in its full generality, an open issue of operations research. In order to give some answers to the question of optimal scheduling, the present thesis will discuss two mathematical models known as "Multi-Armed Bandit Problem" (MABP) and "Restless Bandit Problem" (RBP) in terms of which the FMS can be modeled. Let us briefly recall the salient features of the Bandit formalization. In its basic version, the MABP considers a series of N stochastic processes (also called projects) evolving in parallel. At each time t, a decision maker (DM) can engage at most one project (this feature reflects the limited resource property). The engaged project generates an instantaneous cost while the disengaged projects incur no cost and remain fixed ("frozen" dynamic rule of the disengaged projects). The optimal scheduling problem in the MABP consists in choosing at each time t which project to engage in order to minimize the global cost over a given time horizon. An exact solution of the basic MABP has been given in 1974 by Gittins. The solution is based on the construction of a set of N priority indices (the so-called Gittins indices) which assign to each project an "urgency function" in terms of which the optimal dynamic scheduling reads: "At each instant, engage the item exhibiting the smallest priority index value". To use the MABP formalization in the production engineering context, the basic hypothesis of the "frozen" dynamics needs to be loosened. It is indeed mandatory to allow for the following features: Disengaged projects evolve in time and do incur costs. This generalization is necessary to reflect the fact that demands for items not currently produced continue to accrue and their FGI obviously also incurs costs. The assumptions in a) lead us to study the so-called "Restless Bandit problems" for which the optimal scheduling rule is yet unknown. As it has been noted in the (scarce) literature available, a naive generalization of the priority indices will definitely not yield the optimal rule. However, close to optimal solutions can still be expressed in terms of suitably generalized priority indices. The use of such indices has the determining advantage of leading to very simple --though sub-optimal-- scheduling policies. This is indeed an essential feature of the production applications we have in mind. Hence, the construction of simple solvable models of optimal scheduling rules, will help to develop the perception needed to construct reliable heuristics applicable to the general problems. Accordingly, the general approach adopted in the present thesis is: Construct explicitly solvable classes of Bandit problems (Classical and Restless). Develop a heuristic to approach the problem of FMS and tests its validity on the basis of simulation studies. Moreover, as flexibility in a FMS generally generate setup penalties (such as the need for additional workforce incurring additional costs or cleaning operations imposing switching time delay) we will further: Construct an explicitly solvable class of MABP with setup penalties. Develop a heuristic to approach the general problem of MABP with setup costs and test its validity on the basis of the simple models introduced in iii). Our original contributions are: Explicit computation of the Gittins index for MABP (without switching penalties). We were able to compute explicitly the form of the Gittins indices when the evolution is given by a piecewise deterministic process which is intrinsically non-Markovian. This is among the few classes of non-Markovian examples in the literature for which the Gittins indices can be computed explicitly (M.-O. Hongler and F. Dusonchet, "Optimal stopping and Gittins indices for piecewise deterministic evolution process", Discrete Events Systems (2001) (11), 235--248). Explicit treatment of the Restless Multi-Armed Bandit process. We studied several underlying random dynamics relevant for the production engineering context, (e.g. diffusion processes as well as birth and death processes). We obtained explicit generalized priority indices and the resulting dynamic scheduling was compared with exact results derived numerically by A. Ha, (Oper. Res. 45, 1994, 42-53). Finally, using the RBP, we propose a sub-optimal heuristic solving the multi-items make-to-stock production problem (F. Dusonchet and M.-O. Hongler, "Continuous Time Restless Bandit and Dynamic Scheduling for Make-to-Stock Production", accepted for publication by IEEE Trans. on Robo. and Auto., (2003)). Construction of a sub-optimal heuristic for the MABP with setup penalties. Adding setup penalties to optimal control problems singularly increases the complexity of the solution. Therefore, very few results presently exist and the optimal decision problem with setups remains mostly unexplored. Our effort concentrates on the MABP with setup penalties and significant progress has been made by constructing a new class of MABP with setups for which the optimal policy can be explicitly constructed by recursion. Using this optimal derivation, we then propose a heuristic, approaching the optimal policy for general MABP with switching penalties (F. Dusonchet and M.-O. Hongler, "Optimal Policy for Deteriorating Two-Armed Bandit Problems with Switching Costs", accepted by Automatica, (2003)).
    Résumé
    La tendance croissante de fabriquer des produits de plus en plus proches du désir de tout un chacun, amène les entreprises d'aujourd'hui à s'équiper de chaînes de production flexible (CPF). La flexibilité dans une CPF représente la possibilité qu'a une unique machine de fabriquer différents produits finis, disons N. De plus, cette machine ne peut généralement fabriquer que M < N produits simultanément (nous dirons qu'elle a une "capacité limitée"). Chaque sorte de produit fini répond à une demande spécifique qui possède généralement des fluctuations aléatoires autour d'une valeur moyenne. La présence de ces fluctuations ne permet pas de connaître précisément les demandes futures et impose donc une grande réactivité de l'entreprise afin d'assurer la satisfaction de sa clientèle. En effet, chaque client est une entité égoïste qui a des désirs qu'elle veut, en principe, réaliser sans attendre. Pour faire face à cette difficulté, deux solutions se présentent : La construction de stocks de couverture : La fluctuation i) du flux de production (due aux enrayages des machines) et ii) du flux de la demande peut être partiellement absorbée par la construction de stocks de produits finis. Notons que de telles zones de stockage impliquent des coûts non-négligeables surtout en présence d'une demande ayant des désirs très personnalisés. Clairement, le conflit existant entre la volonté de répondre au plus vite à une demande spécifique et celle de minimiser les coûts de production rend l'optimisation du problème compliquée. Généralement, une solution optimale sera un compromis entre ces deux volontés qui se traduira par la construction de stocks de couverture pour certains produits (production sur stock) et non pour d'autres (production à la demande). L'utilisation d'ordonnancement dynamique de production : La présence intrinsèque de fluctuations à l'intérieur d'une chaîne de production implique que des politiques simples d'ordonnancement (comme par exemple des ordres de production déterminés à l'avance qui ne réagissent pas aux aléas possibles du marché) ont peu de chance d'être optimales. Clairement, l'expérience acquise par la connaissance des événements passés et l'observation de l'état présent de la CPF (i.e. le niveau de remplissage des stocks de couverture, la vitesse instantanée de production et la quantité présente des demandes) doivent être à la base de la construction d'une politique optimale d'ordonnancement. Nous comprenons donc qu'une telle politique devra nécessairement s'adapter aux aléas du marché (i.e. une politique d'ordonnancement en temps réel). Malgré une utilisation grandissante des CPF dans le monde industriel actuel, le problème général de déterminer sa politique optimale d'ordonnancement reste un des problèmes ouverts dans le domaine de la recherche opérationnelle. Dans le but d'apporter quelques réponses à ce problème d'ordonnancement, nous allons discuter dans cette thèse deux modèles mathématiques connus sous le nom de "Problème du Bandit à plusieurs bras" (traduction de "Multi-Armed Bandit problem" (MABP)) et de "Problème du Bandit Agité" (traduction de "Restless Bandit problem" (RBP)) à l'aide desquels nous pourrons décrire et discuter la solution de notre CPF. Décrivons brièvement les propriétés principales du problème du Bandit : Dans sa version classique, le MABP considère une série de N processus stochastiques (aussi appelés projets dans la suite) qui évoluent en parallèle. A chaque instant t, un opérateur de décision (OD) doit engager exactement un des N projets (cette hypothèse reflète la capacité limitée de notre chaîne de production). Le projet engagé génère un coût et évolue en temps. Les projets qui restent inactifs ne coûtent rien et restent figés dans leur état jusqu'à ce qu'ils soient à nouveau engagés (dynamique figée des projets désengagés). Le problème d'ordonnancement dynamique de la MABP consiste à choisir, à chaque instant, lequel des N projets est à engagé afin de minimiser le coût global sur un horizon de temps donné. Une solution optimale pour les MABP a été apportée par Gittins en 1974. Cette politique d'ordonnancement est basée sur la construction d'un ensemble de N indices de priorités (connu sous le nom d'indices de Gittins). Ces indices indiquent l'urgence d'engager chaque projet. Sur la base de ces indices, l'ordonnancement optimal est comme suit : "A chaque instant, engager le projet possédant la plus petite valeur d'indice de Gittins" Pour pouvoir utiliser le formalisme des MABP afin de modéliser notre problème de chaîne de production flexible, nous devons nous débarrasser de la supposition que la dynamique des projets désengagés est figée. En effet, nous devons autoriser la situation suivante : Les projets qui sont désengagés évoluent en temps et génèrent des coûts. Cette généralisation est nécessaire pour notre CPF, en tenant compte que la demande des produits non fabriqués actuellement continue d'arriver. De plus, leurs stocks génèrent des coûts. L'hypothèse a) nous amène à étudier le problème connu sous le nom de "Bandit Agité" (RBP) pour lequel la politique optimale n'est pas encore connue. Comme il est écrit dans la (rare) littérature existante sur les RBP, une généralisation naïve de la politique d'indices de priorité conduit à un résultat loin de l'optimum. Néanmoins, des heuristiques (sous-optimales) apportant un résultat proche de l'optimum peuvent être obtenues à partir d'une généralisation adéquate des Indices de Priorité. L'utilisation de tels indices a l'avantage de fournir des heuristiques simples, ce qui est une condition essentielle pour pouvoir les appliquer aux problèmes industriels que nous avons à l'esprit. Un des buts rattachés à notre étude des CPF sera donc de construire de telles heuristiques. En particulier, nous nous efforcerons de trouver des modèles simples dont la politique optimale d'ordonnancement peut être dérivée explicitement. Ceci nous aidera à développer la perception nécessaire à la construction d'heuristiques fiables, applicables aux problèmes généraux. En conséquence, l'approche adoptée dans cette thèse est la suivante : Construire des classes de problèmes de Bandits (classiques et agités) pour lesquels la politique optimale d'ordonnancement peut être dérivée explicitement. Développer une heuristique permettant d'approcher la solution optimale pour le problème d'une chaîne de production flexible et tester son efficacité en la comparant aux politiques optimales dérivées au point ii). De plus, notons que la flexibilité dans les CPF génère la plupart du temps des coûts et du temps de set up lors du changement entre un type de production et un autre (tel que le coût de la main d'oeuvre supplémentaire nécessaire au lavage des machines) nous allons donc aussi : construire une classe de Bandits classiques avec pénalités de set up pour laquelle la politique d'ordonnancement peut être dérivée explicitement. Développer une heuristique permettant d'approcher la solution optimale pour le problème général des MABP avec des pénalités de set up et tester son efficacité en la comparant à la politique optimale dérivée au point iii). En résumer nos contributions sont les suivantes : Calcul explicite de l'indice de Gittins pour une nouvelle classe de MABP (sans coût de set up) : Nous avons été capables de construire explicitement la forme de l'indice de Gittins quand l'évolution sous-jacente est donnée par un processus déterministe par morceau. Un tel processus est intrinsèquement non-Markovien. Cette classe de MABP est une des première classes non-Markovienne que nous pouvons trouver dans la littérature pour laquelle l'indice de Gittins peut être calculé explicitement (M.-O. Hongler and F. Dusonchet, "Optimal stopping and Gittins indices for piecewise deterministic evolution process", Discrete Events Systems (2001) (11), 235--248). Discussion explicite du problème du Bandit Agité : Nous avons étudié plusieurs dynamiques stochastiques sous-jacentes directement utiles pour le contexte industriel (e.g. processus de diffusion et processus de naissance et de mort). Nous avons obtenu des formules explicites d'indices de priorité généralisés et l'heuristique en découlant a été comparée avec la politique optimale construite numériquement par Ha (Oper. Res. 45, 1994, 42-53). Finalement, en se basant sur les RBP, nous avons proposé une politique d'ordonnancement efficace pour une machine flexible pouvant fabriquer plusieurs types de produits, lorsque les pénalités de set up peuvent être négligées (F. Dusonchet and M.-O. Hongler, "Continuous Time Restless Bandit and Dynamic Scheduling for Make-to-Stock Production", accepted for publication by IEEE Trans. on Robo. and Auto., (2003)). Construction d'une heuristique d'ordonnancement sous-optimal pour le problème des MABP avec pénalités de set up : Tenir compte des pénalités induites par les set up accroît singulièrement la difficulté de la recherche d'une politique optimale. De ce fait, il existe très peu de résultats sur ces sujets et la recherche de la politique optimale des problèmes de décision avec pénalités de changement reste un problème peu exploré. Pour la fin de cette thèse, nous avons donc concentré nos efforts sur le problème des MABP avec coûts et temps de set up. Un progrès significatif a été obtenu étant donné que nous avons pu construire une nouvelle classe de MABP avec pénalités de set up pour laquelle la politique optimale d'ordonnancement peut être calculée explicitement. Sur la base de cette politique optimale, nous avons pu proposer une heuristique approchant la solution générale des MABP avec pénalités de set up. Cette heuristique est basée sur une généralisation de la politique d'indices de priorité (F. Dusonchet and M.-O. Hongler, "Optimal Policy for Deteriorating Two-Armed Bandit Problems with Switching Costs", accepted by Automatica, (2003)).
    Zusammenfassung
    Dem zunehmenden Bedürfnis der Industrie Produkte mit immer mehr Rücksicht auf die fluktuierende (d.h. zufällig schwankende) Nachfrage herzustellen, begegnet die industrielle Produktion mit dem Konzept flexibler Fabrikationssysteme (FFS). Dabei versteht man in diesem Zusammenhang unter Flexibilität die Fähigkeit einer einzelnen Produktionszelle mehrere (sagen wir N) verschiedene Teil- oder Fertigprodukte (folgend kurz Produkte genannt) herzustellen. Gewöhnlich ist die Produktionskapazität limitiert, so dass höchstens K < N verschiedene Produkte gleichzeitig gefertigt werden können. Jedes Produktionsgut sieht sich dabei einem entsprechenden Absatzmarkt gegenüber der, wie bereits erwähnt, zufälligen Fluktuationen unterliegt. Um auf diese Schwankungen rasch zu reagieren sind effiziente Produktionsstrategien für FFS unabdingbar. Solche Strategien beinhalten im wesentlichen zwei Punkte: Endproduktlager. Fluktuationen im Produktionsfluss (auf Grund fehleranfälliger Produktionsinstallationen) und in der Nachfrage können durch einen entsprechenden Lagerbestand fertiger Produkte (LFP) partiell aufgefangen werden. Eine Strategie die sich auf ein Endproduktlager abstützt, muss das durch den Lagerbestand gebundene Kapital mit den Vorteilen einer dadurch gewonnenen hohen Reaktivität in ein günstiges Verhältnis stellen. Das resultierende Optimierungsproblem ist komplex und die optimale Lösung beinhaltet in der Regel hybride Produktionsregeln (d.h. verschiedene Produkte verlangen verschiedene Produktionsstrategien). Dynamische Strategien. Die naturgemäss vorhandenen Fluktuationen haben zur Folge, dass einfache, deterministische Produktionsregeln (wie z.B., "fertige periodisch jedes Produkt während einer gewissen Zeitspanne") einen sehr bescheidenen Leistungsnachweis erbringen. Eine gute Strategie bedient sich zum Einen, vorhandenen Erfahrungswerten und zum Anderen, dem aktuellen Zustand des Produktionssystems und der Nachfrage (z.B., Information über LFP, Produktionsflüsse und Bestelleingänge). Eine optimale Strategie wird demzufolge einen zeitabhängigen adaptiven Charakter aufweisen müssen ("Real-time" Strategie). Trotz seiner unbestrittenen Relevanz für industrielle Anwendungen bilden real-time Optimierungsprobleme für FFS nach wie vor ein weites, keineswegs abgeschlossenes Forschungsfeld. Die vorliegende Doktorarbeit platziert sich in diesem Arbeitsfeld mit zwei mathematischen Modellen bekannt unter den Namen "Multi-Armed Bandit Problems" (MABP) und "Restless Bandit Problem" (RBP). Dieser "Bandit"-Formalismus erlaubt die Beschreibung einer FFS. Er sei hier folgend inhaltlich kurz zusammengefasst. In seiner Grundversion besteht das MABP aus N stochastischen Prozessen (auch "Projekte" genannt), die sich zeitlich parallel entwickeln. Zu jedem Zeitpunkt t kann höchstens ein (Teil)-Projekt aktiv sein (sprich, hergestellt werden). Die Herstellung eines Projekts generiert entsprechende Herstellungskosten doch wird angenommen, dass während dieser Herstellzeit die übrigen Projekte weder Kosten verursachen noch ihren Zustand ändern (nicht aktive Projekte sind in ihrem Ist-Zustand "erstarrt"). Das dynamische Grundproblem besteht nun darin zu jedem Zeitpunkt aufs neue zu entscheiden welches Projekt herzustellen ist, so dass die globalen Produktionskosten während eines gegebenen Produktionszeitraums minimiert werden. Dieses Grundproblem wurde 1974 von Gittins exakt gelöst. Seine Lösung basiert auf der Konstruktion von N Index-Funktionen (Gittins-Index) welche jedem Produkt eine "Dringlichkeitsfunktion" zuweist und mit deren Hilfe die optimale dynamische Produktionsstrategie wie folgt zusammengefasst werden kann: "Stelle zu jedem Zeitpunkt das Produkt mit kleinster Dringlichkeitsstufe her." Um den MABP-Formalismus auf industrielle Produktionssysteme anwenden zu können muss die oben genannte Grundhypothese -- nicht-aktive Projekte sind "erstarrt" -- aufgeweicht werden. Tatsächlich sollte sie wie folgt verallgemeinert werden: (H) Auch nicht aktive Projekte können ihren Zustand ändern und Kosten verursachen. Die Verallgemeinerung ist notwendig um der sich verändernden Nachfrage eines (nicht notwendigerweise aktiven) Projekts zu begegnen und seine Lagerkosten zu berücksichtigen. Lagerkosten und allgemein Kosten die nicht direkt produktionsbedingt sind, werden folgend kurz als Zusatzkosten angesprochen. Diese Annahme veranlasste uns die in diesem Fall adäquateren "Restless-Bandit" Probleme anzugehen für die jedoch im allgemeinem noch keine optimalen Lösungen vorliegen. Die spärliche Literatur zum mathematischen Problem beinhaltet im wesentlichen ein "negatives" Resultat welches zeigt, dass eine naive Erweiterung der oben erwähnten Index-Lösung zwangshalber sub-optimal ist. Trotzdem können durch generalisierte Index-Strategien gute Produktionsregeln aufgestellt werden die nahe der optimalen Lösung sind. Der entscheidende, die Sub-Optimalität überwiegende Vorteil von Index-Strategien ist ihre sehr einfache Implementierung was mit Blick auf unsere industrielle Anwendung in der Tat essentiell ist. Die Konstruktion einfacher, optimal lösbarer "Bandit" Probleme soll dabei helfen, die sub-optimalen generalisierten Index-Strategien auf ihre Verwendbarkeit hin zu untersuchen. Entsprechend wurde der vorliegenden Arbeit folgendes Programm zu Grunde gelegt: Konstruktion einer Klasse von explizit lösbaren Bandit Problemen. Entwicklung heuristischer Methoden für FFS und Studium ihrer Verwendbarkeit auf Grund numerischer Simulationen. Darüber hinaus soll mit Blick auf die industrielle Anwendung im Bereich FFS die Arbeitshypothese (H) wie folgt integriert werden: Konstruktion einer Klasse von explizit lösbaren MABP mit Zusatzkosten. Entwicklung heuristischer Methoden für MABP mit Zusatzkosten und Studium ihrer Verwendbarkeit basierend auf einem Vergleich mit den explizit konstruierten Modellen in (iii). Unser Beitrag zu diesem Forschungsprogramm ist: Explizite Berechnung des Gittins-Index für MABP ohne Zusatzkosten. Für eine nicht-Markovsche, stückweise deterministische Projektdynamik wurden die Gittins-Index Funktionen explizit berechnet. Es ist dies das erste nicht-Markovsche Model mit expliziter Lösung und bereits publiziert unter "Optimal Stopping and Gittins indices for picewise deterministic evolution process", M.-O. Hongler und F. Dusonchet in "Discrete Events Systems" (2001) Vol. 11, 235-248. Explizite Teillösungen für "Restless-MAB" Prozesse. Verschiedene, für die industrielle Produktion relevante, stochastische Projektdynamiken (z.B. Diffusionsprozesse) wurden untersucht. Wir konstruierten explizite (generalisierte) Index-Funktionen und verglichen die resultierende Produktionsstrategie mit den numerischen Resultaten der implizit gegebenen optimalen Lösungen von A. Ha (Oper. Res. 45, 1994, 42-53). Schlussendlich wurde mit Hilfe des "Restless-Bandit" Formalismus eine heuristische Lösung für das "Multi-Item Make-to-Stock" Produktionsproblem vorgeschlagen. Dieser Beitrag ist zur Publikation in IEEE "Transactions on Robotics and Automation" (2003) unter dem Titel "Continuous Time Restless Bandit and Dynamic Scheduling for Make-to-Stock Production" (F. Dusonchet und M.-O. Hongler) freigegeben. Konstruktion einer Heuristik für MABP mit Setup Kosten. Werden zusätzlich Setup Kosten (z.B., die Kosten die beim Aktivieren eines passiven Projekts anfallen) in das Optimierungsproblem aufgenommen, wird ein singuläres Lösungsverhalten immer wahrscheinlicher und eine allfällige Lösung wird sehr kompliziert ausfallen. Es ist deshalb nicht verwunderlich, dass bis heute kaum Resultate existieren die solche Kosten miteinbeziehen. Unsere Anstrengungen konzentrierten sich auf MAB-Probleme mit Setup Kosten und ein signifikanter Fortschritt wurde durch die Identifizierung einer Klasse von MABP erzielt für die die optimale Strategie durch rekursive Konstruktion explizit angegeben werden kann. Mit Hilfe dieser speziellen optimalen Lösung wurde anschliessend eine heuristische Strategie für das generelle MAB-Problem mit Zusatzkosten abgeleitet. Dieser Beitrag ist zur Publikation in "Automatica" (2003) unter dem Titel "Optimal Policy for Deteriorating Two-Armed Bandit Problems with Switching Costs" (F. Dusonchet und M.-O. Hongler) freigegeben.