Scheduling problems can be found in almost any field of application in the real world. These problems may not only have different characteristics but they also imply more or less complex requirements. One specific class within this domain is the cyclic job-shop problem. It occurs in various areas reaching from industrial production planning down to the systems architecture of computers. With manufacturers in particular, one can find increasing demand for effective solution methods in order to tackle these scheduling problems efficiently. This thesis will deal with the Cyclic Job-Shop Problem with Blocking and Transportation. It arises in modern manufacturing companies, where the products move automatically between the different workstations, for instance. The problem itself is not new to the research community, but hardly any work has been done in solving it. Within this thesis we will try to close this gap and present some first approaches, discussing the structure of the problem and how it can be solved. As a result, we will provide three different solution methods, including an integer programming formulation, which is solved with a commercial solver, a branch and bound algorithm and a tabu search heuristic. All algorithms are tested on a range of data sets and compared with each other. Additionally, we have worked on a polynomial solvable subproblem, which has gained more interest in the literature. As a result, a new polynomial algorithm, that outperforms the existing ones in theory as well as in empirical tests (except for some special cases) is presented. This thesis concludes with a discussion about ideas of how to improve the presented methods and some other extensions to the investigated problem.

Business Process Modelling Notation (BPMN) is a standardised diagram notation for modelling interactive workflow processes graphically at the design stage. The primary objective of this thesis is to provide a framework for precise specifications and formal verifications of workflow processes modelled as BPMN diagrams. We provide two behavioural semantics for BPMN in the process algebra Communicating Sequential Processes (CSP). We apply existing CSP refinement orderings to both the refinement of business process diagrams and the verification of behavioural compatibility of business process collaborations. The first semantic model is an untimed model, focusing on the control flow and communication of business processes. The second semantic model extends the first one to capture the timing aspect of behaviour. We also consider the applications of the semantic models. The secondary objective of this thesis is to apply BPMN and the semantic models to reason about long running empirical studies (e.g. laboratory experiments, clinical trials). We introduce a declarative workflow model Empiricol for recording trials and experiments precisely, and define bidirectional transformation functions between BPMN and Empiricol. Using the transformation functions, we make graphical specification, simulation, automation and verification of trials and experiments possible. We provide two case studies on the applications of BPMN’s formalisations.

An important and challenging problem that Process Engineers frequently encounter is the determination of appropriate control structures that minimize the loss of process performance under the effect of uncertainties. This can be achieved by selecting subsets of controlled and manipulated variables and designing their interconnection (controller synthesis). This is known as the Control Structure Selection Problem (CSSP) In this Thesis, a systematic optimization methodology, based on the back-off concept proposed by Prof J. D. Perkins and co-workers, is presented for the CSSP. The proposed formulation offers the following improvements: a) improves the accuracy of calculations and b) reduces computational time and effort. Specifically, the error involved in the approximation of the nonlinear constraint that defines the magnitude of the back-off vector (needed for control structure selection) is reduced by the introduction of a more accurate linear approximation. In addition, the methodology is able to track the effect of simultaneously occurring disturbances at the same time and estimate their worst impact on process economics. The reduction of computational time is achieved by eliminating the state variables from the final formulation. In this way, the number of equations needed for the CSSP solution is significantly reduced and allows the algorithm to locate the solution faster without affecting the performance. The proposed methodology is firstly applied in a classical distillation column (medium scale) and in a complex and highly nonlinear reactive distillation column (large scale). The results obtained from these case studies made the way for the application of the methodology on the plantwide problem of the benchmark Vinyl Acetate monomer production plant in order to demonstrate the benefits of the proposed algorithm. / Η παρούσα εργασία παρουσιάζει μια συστηματική μεθοδολογία για την εύρεση βέλτιστων δομών ρύθμισης σε συστήματα μεγάλης κλίμακας, όπως για παράδειγμα ολοκληρωμένες μονάδες παραγωγής και βασίζεται στην ελαχιστοποίηση των επιπτώσεων των διαταραχών στην οικονομική απόδοση μιας διεργασίας. Το κύριο στοιχείο της μεθοδολογίας είναι το διάνυσμα υποχώρησης από τους ενεργούς περιορισμούς (μ), το οποίο προτάθηκε από τον Prof. J.D. Perkins και την ερευνητική του ομάδα. Η προτεινόμενη μεθοδολογία ενσωματώνει τα κύρια χαρακτηριστικά της μεθοδολογίας του διανύσματος (μ) και παρουσιάζει μια σειρά βελτιώσεων με στόχο τον περιορισμό των μειονεκτημάτων που απέτρεπαν την εφαρμογή της σε συστήματα μεγάλης κλίμακας. Οι βελτιώσεις επικεντρώνονται σε δύο ζητήματα: α) αύξηση της ακρίβειας των υπολογισμών και β) μείωση του υπολογιστικού φόρτου και χρόνου. Η αύξηση της ακρίβειας των υπολογισμών εντοπίζεται στην κατασκευή ενός βελτιωμένου προσεγγιστικού προβλήματος για την κατασκευή κάτω φραγμάτων για τη βέλτιστη λύση. Η βασική ιδέα πίσω από τη προτεινόμενη βελτίωση βασίζεται στη προσέγγιση των μη γραμμικών όρων που εμφανίζονται με ένα σύνολο γραμμικών εξισώσεων. Επίσης για πιο ακριβείς υπολογισμούς, εξετάζεται κάθε διαταραχή ξεχωριστά σε ένα εύρος συχνοτήτων και στη συνέχεια η μέγιστη επίδραση της καθεμίας χρησιμοποιείται από τον αλγόριθμο έτσι ώστε να υπολογιστεί η μέγιστη δυνατή επίπτωση τους στην οικονομική απόδοση της διεργασίας Η μείωση του υπολογιστικού φόρτου και χρόνου επιτυγχάνεται μέσω της απαλοιφής των μεταβλητών κατάστασης. Με αυτό τον τρόπο, ο αριθμός των εξισώσεων που απαιτείται για την επίλυση του προβλήματος μειώνεται σημαντικά και εντοπίζει τη βέλτιστη λύση σε μικρότερο αριθμό επαναλήψεων της μεθόδου, γεγονός που επιτρέπει την εφαρμογή της σε προβλήματα μεγάλης κλίμακας. Τέλος, η προτεινόμενη μεθοδολογία έχει εφαρμοστεί σε δύο αποστακτικές στήλες και τα αποτελέσματα άνοιξαν το δρόμο για την εφαρμογή της μεθόδου σε μια μονάδα παραγωγής οξικού μεθυλεστέρα, όπου τα πλεονεκτήματα της μεθόδου είναι περισσότερο ορατά και πρακτικά χρήσιμα.

Η παρούσα εργασία αποσκοπεί στη μελέτη του προβλήματος του χρονοπρογραμματισμού γεγονότων, την τοποθέτηση δηλαδή των γεγονότων σε υποδοχείς χρόνου και χώρου, με τη χρήση Γενετικών Αλγορίθμων. Μελετήσαμε τo πρόβλημα του χρονοπρογραμματισμού στην Εκπαίδευση και ειδικότερα σε ένα Πανεπιστήμιο, που εμφανίζεται σε δύο εκδοχές: το πρόβλημα χρονοπρογραμματισμού εξετάσεων και το πρόβλημα χρονοπρογραμματισμού διαλέξεων, καθώς και τα αντίστοιχα πειράματα και τα αποτελέσματα αυτών. Χρησιμοποιώντας το λογισμικό FET που βασίζεται στους Γενετικούς Αλγόριθμους κατασκευάσαμε χρονοδιαγράμματα για το ωρολόγιο πρόγραμμα του Μεταπτυχιακού Προγράμματος του Διατμηματικού του Πανεπιστημίου Πατρών "Μαθηματικά των Υπολογιστών και των Αποφάσεων" των τμημάτων Μαθηματικών και Μηχανικών Η/Υ και Πληροφορικής και παρουσιάσαμε τα αποτελέσματα αυτών. / The aim of this paper is the study of the timetabling problem, meaning the allocation of events in time-slots and space-slots, using Genetic Algorithms. We studied the Education Timetabling problem for a University which appears in two versions, timetabling of exams and timetabling of lectures and its corresponding experiments and results. Using the open source free software FET which is based on the Genetic Algorithms, we scheduled timetables for the weekly program of Postgraduate Program of University of Patras "Mathematics of Computers and Decision" in which participate two departments, the department of Mathematics and the department of Engineering Computing and Information Technology and we presented the results of those.

Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en définissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c.-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà finies. Ces contraintes représentent une subdivision des tâches en sous tâches pouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons défini les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème afin de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c.-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation afin d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut. Nous avons analysé les résultats obtenus afin de déterminer les inégalités les plus intéressantes afin de résoudre ce problème. Enfin dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En effet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes définies précédemment afin d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons fini par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances / The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . .). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specificities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specific system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect different technical rules (constraints) and to provide the maximum of effectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientific level in addition to their high practical relevance. In particular, we aimed to build new efficient combinatorial methods for solving parallel-machine scheduling problems where resources have different speeds and tasks are linked by precedence constraints. In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods. We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with different constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with different techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this comparison has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. [...]

L’évolution continue des environnements de production et l’augmentation des besoins des clients, demandent un processus de production plus rapide et efficace qui contrôle plusieurs paramètres en même temps. Nous nous sommes intéressés au développement de méthodes d’aide à la décision qui permettent d’améliorer l’ordonnancement de la production. L’entreprise partenaire (Norelem) fabrique des pièces de précision mécanique, il faut donc prendre en compte les différentes contraintes de ressources (humaines et d’outillage) existantes dans l’atelier de production.Nous avons abordé l’étude d’un atelier d’ordonnancement de type open shop ou chemin ouvert, où une tâche peut avoir de multiples séquences de production puisque l’ordre de fabrication n’est pas fixé et l’objectif à minimiser est le temps total de séjour. Des contraintes d’affectation de ressources humaines (multi-compétences) et de disponibilité d’outillage ont été prises en compte.Des modèles mathématiques linéaires et non-linéaires ont été développés pour décrire la problématique. Etant donné que les méthodes exactes sont limitées aux instances de petites tailles à cause des temps de calcul, des méthodes de résolution approchées ont été proposées et comparées. De plus, nous avons abordé l’optimisation multi-objectif en considérant trois objectifs, la minimisation du temps total de séjour et l’équilibrage de charge des ressources (humaines et machines).L’efficacité des méthodes est prouvée grâce à des tests sur des instances théoriques et l’application au cas réel / The continuous evolution of manufacturing environments and the growing of customer needings, leads to a faster and more efficient production process that controls an increasing number of parameters. This thesis is focused on the development of decision making methods in order to improve the production scheduling. The industrial partner (Norelem) produces standardized mechanical elements, so many different resource constraints (humans and tools) are presented in its workshop.We study an open shop scheduling problem where one job can follow multiple production sequences because there is no fixed production sequence and the objective function is to minimize the total flow time. In addition, multi-skilled personnel assignment and tool’s availability constraints are involved.Mathematical models: linear and non-linear formulations have been developed to describe the problem. Knowing the exact method limitations in terms of instance sizes because of the duration, heuristics methods have been proposed and compared. Besides that, the multi-objective optimization was exposed to deal with three objectives as total flow time minimization and workload balancing concerning both, humans and machines.The efficiency of these methods was proved by several theoretical instance tests and the application on the real industrial case