Scheduling for Timed Context-Aware Flexible Manufacturing Systems
Authors
Nykjær, Daniel Overvad ; Hansen, Rasmus Høyer
Term
4. term
Education
Publication year
2024
Submitted on
2024-06-21
Pages
38
Abstract
As Industry 4.0 advances, factories need flexible manufacturing systems that can reconfigure quickly while keeping production safe, correct, and on time. A key challenge is planning and controlling processes so that products are made correctly without compromising safety or deadlines. We introduce a formal model for Context-Aware Timed Flexible Manufacturing Systems (CATFMS). The model captures: (1) product protocols—the allowed sequence of steps each product must follow, (2) deadlines for parts of those protocols, (3) machines that are active and have internal state (stateful), and (4) robot arms that can reach only specific subsets of machines. In this way, the model accounts for timing, equipment state, and physical reach. Based on this model, we define precise semantics (formal rules that give the model an unambiguous meaning) and build two tools: a verifier that checks whether a schedule is correct and safe, and a schedule synthesizer that automatically generates production schedules from requirements and deadlines. Using the semantics and the verifier, we show that an existing schedule synthesizer does not always produce correct schedules. We then present a new schedule synthesis algorithm tailored to CATFMS, together with four heuristic functions (rules of thumb) that guide the search for schedules. We implement the algorithm, verifier, and heuristics, and compare the heuristics with each other and with an unguided depth-first search (a method that explores one option path at a time). One heuristic is selected for deeper analysis, and we compare a guided depth-first algorithm using this heuristic with an unguided depth-first algorithm. Our results show that even when prioritizing synthesis speed over guaranteed optimality, the guided approach can find schedules that are more optimal than those produced by the unguided search. We discuss and evaluate the results in terms of both schedule quality and the time needed to synthesize a solution.
I takt med Industry 4.0 får fabrikker brug for fleksible produktionssystemer, der kan omstilles hurtigt og køre sikkert og rettidigt. En central udfordring er at planlægge og styre processer, så produkter laves korrekt, uden at gå på kompromis med sikkerhed eller deadlines. Vi præsenterer en formel model for Context-Aware Timed Flexible Manufacturing Systems (CATFMS). Modellen beskriver: (1) produktprotokoller – de tilladte trin et produkt skal igennem, (2) deadlines for dele af disse trin, (3) maskiner, der kan være aktive og har interne tilstande (stateful), og (4) robotarme, der kun kan nå bestemte grupper af maskiner. På den måde tager modellen højde for både tid, udstyrstilstand og fysisk rækkevidde. Med udgangspunkt i modellen definerer vi præcise semantikker (de formelle regler, der giver modellen entydig betydning) og udvikler to værktøjer: en verifikator, der kontrollerer om en plan er korrekt og sikker, og en plansyntetisator, der automatisk fremstiller produktionsplaner (schedules) ud fra krav og deadlines. Ved hjælp af semantikken og verifikatoren viser vi, at en eksisterende plansyntetisator ikke altid producerer korrekte planer. Vi præsenterer derefter en ny algoritme til plansyntese, skræddersyet til CATFMS, samt fire heuristikker (praktiske tommelfingerregler), der guider søgningen efter en plan. Vi implementerer algoritmen, verifikatoren og heuristikkerne og sammenligner heuristikkerne indbyrdes og med en ikke-guidet depth-first-søgning (en metode, der udforsker én mulighed ad gangen i dybden). En af heuristikkerne udvælges til nærmere analyse, og vi sammenligner en guidet depth-first-algoritme baseret på denne heuristik med en ikke-guidet depth-first-algoritme. Resultaterne viser, at selv når vi prioriterer syntesehastighed over garanteret optimalitet, kan den guidede tilgang finde planer, der er mere optimale end dem fundet af en ikke-guidet søgning. Vi diskuterer resultaterne med fokus på både planernes kvalitet og den tid, det tager at syntetisere en løsning.
[This apstract has been rewritten with the help of AI based on the project's original abstract]