Dissertationen zum Thema „Generalized Assignment Problems“

This thesis considers optimization techniques with applications in assignment and generalized linear regression problems. The first part of the thesis investigates the worst-case robust counterparts of combinatorial optimization problems with least squares (LS) cost functions, where the uncertainty lies on the linear transformation of the design variables. We consider the case of ellipsoidal uncertainty, and prove that the worst case robust LS optimization problem, although NP-hard, is still amenable to convexrelaxation based on semidefinite optimization. We motivate our proposed relaxation using Lagrangian duality, and illustrate that the tightness of the Lagrange bidual relaxation is strongly dependent on the description of the feasible region of the worst-case robust LS problem. The results arising from this analysis are applicable to a broad range of assignment problems. The second part of the thesis considers combinatorial optimization problems arising specifically in the context of conference program formation. We start by arguing that both papers and reviewers can be represented as feature vectors in a suitable keyword space. This enables rigorous mathematical formulation of the conference formation process. The first problem, paper-to-session assignment, is formulated as a capacitatedk-means clustering problem. We formally prove that it is NP-hard and propose a variety of approximate solutions, ranging from alternating optimization to semidefinite relaxation. Suitable convex relaxation methods are proposed for the paper-to-reviewer assignment problem as well. Our methods are tested using real conference data for both problems, and show very promising results. In a related but distinct research direction, the third part of the thesis focuses on preference measurement applications: Review profiling, i.e., determining the reviewer’s expertise (and thus identifying the associated feature vector for the reviewer) on the basis of their past and present review preferences, or ‘bids’, is an excellent example of preference measurement. We argue that the need for robust preference measurement is apparent in modern applications. Using conjoint analysis (CA) as a basis, we propose a new statistical model for choice-based preference measurement, a part of preference analysis where data are only expressed in the form of binary choices. The model uses deterministic auxiliary variables to account for outliers and to detect the salient features that influence decisions. Contributions include conditions for statistical identifiability, derivation of the pertinent Cramér-Rao Lower Bound (CRLB), and ML consistency conditions for the proposed nonlinear model. The proposed ML approach lends itself naturally to ℓ1-type convex relaxations which are well-suited for distributed implementation, based on the alternating direction method of multipliers (ADMM). A particular decomposition is advocated which bypasses the apparent need for outlier variable communication, thus maintaining scalability. In the last part of the thesis we argue that this modeling has greater intellectual merits than preference measurement, and explain how related ideas can be put in the context of generalized linear regression models, drawing links between ℓ1-methods, stochastic convex optimization, and the field of robust statistics.

QC 20140902

In this thesis a method for solving the Generalized Assignment Problem (GAP) is described. It is based on a reformulation of the original problem into a Set Partitioning Problem (SPP), in which the columns represent partial solutions to the original problem. For solving this problem, column generation, with systematic overgeneration of columns, is used. Conditions that guarantee that an optimal solution to a restricted SPP is optimal also in the original problem are given. In order to satisfy these conditions, not only columns with the most negative Lagrangian reduced costs need to be generated, but also others; this observation leads to the use of overgeneration of columns.

The Generalized Assignment Problem has shown to be NP-hard and therefore efficient algorithms are needed, especially for large problems. The application of the proposed method decomposes GAP into several knapsack problems via Lagrangian relaxation, and enumerates solutions to each of these problems. The solutions obtained from the knapsack problems form a Set Partitioning Problem, which consists of combining one solution from each knapsack problem to obtain a solution to the original problem. The algorithm has been tested on problems with 10 agents and 60 jobs. This leads to 10 knapsack problems, each with 60 variables.

Cette thèse explore l'optimisation des services d'éducation spécialisée et de soins à domicile en France. Elle aborde les défis pratiques rencontrés dans ces domaines, en se concentrant principalement sur l'affectation et la planification des professionnels pour répondre aux divers besoins des personnes souffrant, par exemple, de déficiences visuelles ou auditives. La recherche s'articule autour de trois configurations : les problèmes d'affectation et de planification dans les services d'éducation spécialisée, l'intégration des services d'éducation spécialisée et de soins à domicile avec les défis d'affectation, de planification et d'ergonomie, et l'optimisation des scénarios multicentriques. Chaque configuration est abordée à l'aide de modèles mathématiques et d'approches multi-objectifs, dans le but de parvenir à une allocation équitable des ressources et d'améliorer l'efficacité des services. Dans la première configuration, un modèle de programmation linéaire en nombres entiers mixtes avec deux approches multi-objectifs (une méthode de somme pondérée et un modèle basé sur les contraintes epsilon) est utilisé pour équilibrer la charge de travail entre les éducateurs et assurer la satisfaction des étudiants. La deuxième configuration étend cette approche à l'intégration des services d'éducation spécialisée et de soins à domicile et à la résolution de leurs problèmes d'affectation et de planification sur plusieurs jours tout en considérant les temps des trajets et les distances. Nous avons fourni une solution exacte en utilisant un modèle de programmation linéaire en nombres entiers mixtes pour résoudre le problème étudié. En outre, nous avons mis en œuvre une heuristique gourmande et deux approches métaheuristiques (un algorithme génétique et un algorithme d'optimisation invasive discrète des mauvaises herbes) pour résoudre surtout les instances de grande taille. Nous avons pris en compte sept objectifs : la spécialisation des affectations, la répartition équitable des heures improductives et des heures supplémentaires entre les employés, l'équilibre des distances parcourues entre les employés et la minimisation de la distance totale parcourue, de la distance la plus élevée parcourue et du nombre d'heures improductives et d'heures supplémentaires. En outre, les contraintes d'affectation, de planification et d'ergonomie ont été prises en compte, telles que la qualification des compétences, les pauses déjeuner, les restrictions de quotas, les heures supplémentaires tolérées et le temps de déplacement. La configuration finale se concentre sur l'optimisation des scénarios multicentriques. Une approche en deux phases a été mise en œuvre. La première phase attribue les missions aux centres sur la base d'un modèle mathématique hiérarchique multi-objectif, en tenant compte des contraintes de qualification et de capacité. La seconde phase attribue les missions aux employés de chaque centre et optimise la planification des horaires
This thesis explores the optimization of specialized education and home care services in France. It addresses the practical challenges encountered in these fields, focusing primarily on the allocation and planning of professionals to meet the diverse needs of people with, for example, visual or hearing impairments. The research is structured around three configurations: assignment and planning issues in specialized education services, the integration of specialized education and home care services with assignment, planning, and ergonomic challenges, and the optimization of multi-center scenarios. Each configuration is addressed using mathematical models and multi-objective approaches, with the aim of achieving equitable resource allocation and improving service efficiency. In the first configuration, a mixed integer linear programming model with two multi-objective approaches (a weighted sum method and an epsilon-constraint-based model) is employed to balance the workload among educators and ensure student satisfaction. The second configuration extends this approach to the integration of specialized education and home care services and the resolution of their multi-day assignment and planning problems while considering travel times and distances. We provided an exact solution using a mixed integer linear programming model to solve the problem studied. In addition, we implemented a greedy heuristic and two metaheuristic approaches (a genetic algorithm and a discrete invasive weed optimization algorithm) to solve large-size instances. We considered seven objectives: specialization of assignments, equitable distribution of unproductive hours and overtime hours among the employees, balancing of traveled distances among the employees and minimization of total distance traveled, highest distance traveled, and number of unproductive and overtime hours. In addition, assignment, planning, and ergonomic constraints were taken into account, such as skill qualification, lunch breaks, quota restrictions, tolerated overtime, and travel time. The final configuration focuses on the optimization of multi-center scenarios. A two-phase approach has been implemented. The first phase allocates missions to centers on the basis of a hierarchical multi-objective mathematical model, taking into account qualification and capacity constraints. The second phase assigns missions to employees in each center and optimizes the planning of schedules

In this thesis, we consider the Multi Resource Agent Bottleneck Generalized Assignment Problem. We aim to minimize the maximum load over all agents. We study the Linear Programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our Branch and Bound algorithm while defining lower and upper bounds and branching schemes. We find that our Branch and Bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes. To find approximate solutions, we define a tabu search algorithm and an &
#945
approximation algorithm. Our computational results have revealed that these procedures can find high quality solutions to large sized instances very quickly.

Thesis (Ph. D.)--West Virginia University, 2007.
Title from document title page. Document formatted into pages; contains xi, 86 p. : ill. Includes abstract. Includes bibliographical references (p. 82-86).

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
Esta dissertação estuda modelos e algoritmos para o Problema de Alocação Generalizada (PAG) . A motivação para este estudo foi uma nova aplicação do PAG: o Problema de Carregamento de Caminhões (PCC) . A pesquisa desenvolvida concentra-se no estudo e na proposta de algoritmos aproximados (metaeurísticas) e exatos para a resolução do PAG. Os algoritmos aproximados propostos baseiam-se em um conceito recentemente criado por Fischetti e Lodi (2003), que utiliza programação matemática inteira para a exploração eficiente de vizinhanças mais abrangentes. Os resultados obtidos foram comparáveis aos melhores conhecidos, com a vantagem de exigir um esforço pequeno de implementação e um menor tempo de processamento. O algoritmo exato proposto é um algoritmo de branch-and-cut- and-price, que tem como ponto de partida o algoritmo de branch-and-price de Savelsbergh (1997). Técnicas de estabilização da geração de colunas similares às propostas por Du Merle, Villeneuve, Desrosiers e Hansen (1999), foram estudadas no âmbito desta dissertação, que experimenta com diferentes implementações deste mecanismo. O algoritmo de branch-andcut-and-price estabilizado demonstrou sua eficiência ao resolver à otimalidade instâncias que se encontravam em aberto na literatura. Finalmente, experiências com PCC permitiram que os códigos desenvolvidos pudessem ser avaliados em problemas reais.
This dissertation tackles the Generalized Assignment Problem (PAG), models and algorithms are studied and proposed. This work was motivated by a real world application: the Truck Loading Problem (PCC). Research was done on approximated (metaheuristics) and exact algorithm for solving the PAG. The approximated algorithms proposed were based on a recent idea from Fischetti and Lodi (2003). It uses integer programming to explore wider neighborhoods. The results were compared to the best known, while demanding much less implementation effort and using less cpu time. The exact algorithm proposed is a branch-and-cut- and-price developed from the branch-and-price algorithm of Savelsbergh (1997). We used stabilized column generation techniques similar to the one by Du Merle, Villeneuve, Desrosiers and Hansen (1999), and devised experiments with different implementations of this mechanism. The resulting algorithm proved its efficiency by solving to optimality open instances from the literature. Finally, experiments with the PCC turned possible the evaluation of the codes developed on real problems.

The research reported in this thesis considers the classical combinatorial optimization problem known as the Generalized Assignment Problem (GAP). Since the mid 1970's researchers have been developing solution approaches for this particular type of problem due to its importance both in practical and theoretical terms. Early attempts at solving GAP tended to use exact integer programming techniques such as Branch and Bound. Although these tended to be reasonably successful on small problem instances they struggle to cope with the increase in computational effort required to solve larger instances. The increase in available computing power during the 1980's and 1990's coincided with the development of some highly efficient heuristic approaches such as Tabu Search (TS), Genetic Algorithms (GA) and Simulated Annealing (SA). Heuristic approaches were subsequently developed that were able to obtain high quality solutions to larger and more complex instances of GAP. Most of these heuristic approaches were able to outperform highly sophisticated commercial mathematical programming software since the heuristics tend to be tailored to the problem and therefore exploit its structure. A new approach for solving GAP has been developed during this research that combines the exact Branch and Bound approach and the heuristic strategy of Tabu Search to produce a hybrid algorithm for solving GAP. This approach utilizes the mathematical programming software Xpress-MP as a Branch and Bound solver in order to solve sub-problems that are generated by the Tabu Search guiding heuristic. Tabu Search makes use of memory structures that record information about attributes of solutions visited during the search. This information is used to guide the search and in the case of the hybrid algorithm to generate sub problems to pass to the Branch and Bound solver. The new algorithm has been developed, imp lemented and tested on benchmark test problems that are extremely challenging and a comprehensive report and analysis of the experimentation is reported in this thesis.

COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
Métodos que combinam estratégias normalmente encontradas em algoritmos metaeurísticos com técnicas para resolver problemas de programação inteira mista (MIP) têm apresentado ótimos resultados nos últimos anos. Este trabalho propõe dois novos algoritmos nessa linha: um algoritmo que faz pós-processamento nas soluções encontradas pelo resolvedor MIP. Os dois algoritmos utilizam um novo tipo de vizinhança, chamada de vizinhança elipsoidal, que possui fortes semelhanças com as técnicas de relinking de algoritmos PR e que neste trabalho é generalizada e extendida para múltiplas soluções. O problema generalizado de alocação (GAP) é usado para os experimentos. São testados também um resolvedor MIP puro (ILOG CPLEX versão 11) e um algoritmo branch and price que utiliza as heurísticas RINS e guided dives. Os algoritmos testados são comparados entre e com heurísticas específicas para o GAP. Os resultados são satisfatórios e indicam que as vizinhanças elipsoidais conseguem frequentemente melhorar as soluções encontradas pelo resolvedor MIP, encontrando a melhor solução para algumas instâncias.
Methods that mix strategies usually found in metaheristic algorithms with techniques to solve mixed integer programming problems (MIPs) have had great results over the past few years. This wprk proposes two new algorithms in this philosophy: one is based on the Path Relink (PR) metaheuristc, while the other one is a simple algorithm that does post-processing in the solutions found by the MIP solver. Both algorithms use a new neighborhood structure, called ellipsoidal neighborhood, that has strong resemblances with the relinking step from PR algorithms and that, in this work, is generalized and extended for multiple solutions. The generalized assignment problem (GAP) is used for the computational experiments. Also tested are MIP solver (ILOG CPLEX version 11) and a branch and price algorithm that uses the RINS and guides dives heuristics. The tested algorithms are compared among themselves and with GAP-specific heuristics. The results are satisfactory and show that the ellipsoidal neighborhood can frequently improve the solutions found by the MIP solver, even finding the best result for some instances.

The work presented in this dissertation has been focused on exploiting the branch-and-price (BNP) method for the solution of various stochastic mixed integer programming problems (MIPs). In particular, we address the stochastic generalized assignment problem (SGAP), a hospital staff scheduling problem (HSSP), a stochastic hospital staff scheduling problem (SHSSP), and a stochastic short-term personnel planning problem (SSTPP). The BNP method has been developed in concert with the dual stabilization technique and other enhancements of this method for each of these problems. In view of an excessive number of scenarios that arise for these problems, we also implement the Monte Carlo method within the BNP scheme. The superiority of the BNP-based method over the branch-and-cut (BNC) method is demonstrated for all of these problems. The first problem that we address is the SGAP for which the processing time of a job on a machine is assumed to be stochastic. Even though the generalized assignment problem (GAP) has been solved using the BNP method, yet no study has been reported in the literature on the use of the BNP method for the solution of the SGAP. Our work has been motivated by the desire to fill this gap. We begin by showing that it is better to solve the SGAP as a stochastic program in contrast to solving it by using the expected values of the times required to process the jobs on the machines. Then, we show that the stochastic model of the SGAP is a complete recourse model â a useful property which permits the first stage decisions to produce feasible solutions for the recourse problems. We develop three BNP-based methods for the solution of the SGAP. The first of these is BNP-SGAP, which is a combination of branch-and-bound and column generation methods. The pricing problem of BNP-SGAP is separable with regard to each machine, and it is a multiple-constraint knapsack problem. The second method is BNP-SGAP implemented in concert with the dual stabilization technique (DST), and it is designated as BNPDST-SGAP. We have introduced a new DST by modifying the Boxstep method of Pigatti et al. [76]. We have shown that our method performs better than the method of Pigatti et al. [76] resulting in over two-fold savings in cpu times on average. The third method that we develop for the solution of the SGAP is BNPDST-SGAP implemented with an advanced start to obtain an initial feasible solution. We use a greedy heuristic to obtain this solution, and this heuristic is a modification of a similar method used for the knapsack problem. It relies on the information available at a node of the underlying branch-and-bound tree. We have shown that this procedure obtains an initial feasible solution, if it exists at that node. We designate this method as BNPDSTKP-SGAP. We have also developed a BNC method to solve the SGAP using CPLEX 9.0. We have compared the performances of the BNP and BNC methods on various problem instances obtained by varying the number of machines, the ratio of the number of machines to the number of jobs, the machine capacity, and the penalty cost per unit of extra resource required at each machine. Our results show that all BNP-based methods perform better than the BNC method, with the best performance obtained for BNPDSTKP-SGAP. An issue with the use of the scenario-based methods that we have employed for the solution of the SGAP is that the number of scenarios generally grows exponentially in problem parameters, which gives rise to a large-size problem. To overcome the complexity caused by the presence of a large number of scenarios for the solution of the SGAP, we introduce the use of the Monte Carlo method (MCM) within the BNP scheme. We designate this method as BNPDSTKP-SGAP with MCM. It affords the use of a small subset of scenarios at a time to estimate the â trueâ optimal objective function value. Replications of the subsets of scenarios are carried out until the objective function value satisfies a stopping criterion. We have established theoretical results for the use of the MCM. These pertain to determining unbiased estimates of: (i) lower and upper bounds of the â trueâ optimal objective function value, (ii) the â trueâ optimal solution, and (iii) the optimality gap. We have also provided the 100(1-ï ¡) confidence interval on the optimality gap. Our experimental investigation has shown the efficacy of using this method. It obtains almost optimal solutions, with the objective function value lying within 5% of the â trueâ optimal objective function value, while giving almost ten-fold savings in cpu time. Our experimentation has also revealed that an increment in the number of scenarios in each replication makes a greater impact on the quality of the solution obtained than an increment in the number of replications. We have also observed the impact of a change in the variance of a processing time distribution on cpu time. As expected, the optimal objective function value increases with increment in processing time variability. Also, by comparing the results with the expected value solution, it is observed that the greater the variability in the data, the better it is to use the stochastic program. The second problem that we study is the hospital staff scheduling problem. We address the following three versions of this problem: HSSP (General): Implementation of schedule incorporating the four principal elements, namely, surgeons, operations, operating rooms, and operation times; HSSP (Priority): Inclusion of priority for some surgeons over the other surgeons regarding the use of the facility in HSSP (General); HSSP (Pre-arranged): Implementation of a completely pre-fixed schedule for some surgeons. The consideration of priority among the surgeons mimics the reality. Our BNP method for the solution of these problems is similar to that for the SGAP except for the following: (i) a feasible solution at a node is obtained with no additional assignment, i.e., it consists of the assignments made in the preceding nodes of that node in the branch-and-bound tree; (ii) the columns with positive reduced cost are candidates for augmentation in the CGM; and (iii) a new branching variable selection strategy is introduced, which selects a fractional variable as a branching variable by fixing a value of which we enforce the largest number of variables to either 0 or 1. The priority problem is separable in surgeons. The results of our experimentation have shown the efficacy of using the BNP-based method for the solution of each HSSP as it takes advantage of the inherent structure of each of these problems. We have also compared their performances with that of the BNC method developed using CPLEX. For the formulations HSSP (General), HSSP (Priority), and HSSP (Pre-arranged), the BNP method gives better results for 22 out of 30, 29 out of 34, and 20 out 32 experiments over the BNC method, respectively. Furthermore, while the BNC method fails to obtain an optimal solution for 15 experiments, the BNP method obtains optimal solutions for all 96 experiments conducted. Thus, the BNP method consistently outperforms the BNC method for all of these problems. The third problem that we have investigated in this study is the stochastic version of the HSSP, designated as the Stochastic HSSP (SHSSP), in which the operation times are assumed to be stochastic. We have introduced a formulation for this formulation, designated as SHSSP2 (General), which allows for overlapping of schedules for surgeons and operating rooms, and also, allows for an assignment of a surgeon to perform an operation that takes less than a pre-arranged operation time, but all incurring appropriate penalty costs. A comparison of the solution of SHSSP2 (General) and its value with those obtained by using expected values (the corresponding problem is designated as Expected-SHSSP2 (General)) reveals that Expected-SHSSP2 (General) may end up with inferior and infeasible schedules. We show that the recourse model for SHSSP2 (General) is a relatively complete recourse model. Consequently, we use the Monte Carlo method (MCM) to reduce the complexity of solving SHSSP2 (General) by considering fewer scenarios. We employ the branch-and-cut (BNC) method in concert with the MCM for solving SHSSP2 (General). The solution obtained is evaluated using tolerance ratio, closeness to optimality, length of confidence interval, and cpu time. The MCM substantially reduces computational effort while producing almost optimal solutions and small confidence intervals. We have also considered a special case of SHSSP2 (General), which considers no overlapping schedules for surgeons and operating rooms and assigns exactly the same operation time for each assignment under each scenario, and designate it as SHSSP2 (Special). With this, we consider another formulation that relies on the longest operation time among all scenarios for each assignment of a surgeon to an operation in order to avoid scheduling conflicts, and we designate this problem as SHSSP (Longest). We show SHSSP (Longest) to be equivalent to deterministic HSSP, designated as HSSP (Equivalent), and we further prove it to be equivalent to SHSSP (General) in terms of the optimal objective function value and the optimal assignments of operations to surgeons. The schedule produced by HSSP (Equivalent) does not allow any overlap among the operations performed in an operating room. That is, a new operation cannot be performed if a previous operation scheduled in that room takes longer than expected. However, the schedule generated by HSSP (Equivalent) may turn out to be a conservative one, and may end up with voids due to unused resources in case an operation in an operating room is completed earlier than the longest time allowed. Nevertheless, the schedule is still a feasible one. In such a case, the schedule can be left-shifted, if possible, because the scenarios are now revealed. Moreover, such voids could be used to perform other procedures (e.g., emergency operations) that have not been considered within the scope of the SHSSP addressed here. Besides, such a schedule can provide useful guidelines to plan for resources ahead of time. The fourth problem that we have addressed in this dissertation is the stochastic short-term personnel planning problem, designated as Stochastic STPP (SSTPP). This problem arises due to the need for finding appropriate temporary contractors (workers) to perform requisite jobs. We incorporate uncertainty in processing time or amount of resource required by a contractor to perform a job. Contrary to the SGAP, the recourse model for this problem is not a relatively complete recourse model. As a result, we cannot employ a MCM method for the solution of this problem as it may give rise to an infeasible solution. The BNP method for the SSTPP employs the DST and the advanced start procedure developed for the SGAP, and due to extra constraints and presence of binary decision variables, we use the branching variable selection strategy developed for the HSSP models. Because of the distinctive properties of the SSTPP, we have introduced a new node selection strategy. We have compared the performances of the BNC-based and BNP-based methods based on the cpu time required. The BNP method outperforms the BNC method in 75% of the experiments conducted, and the BNP method is found to be quite stable with smaller variance in cpu times than those for the BNC method. It affords solution of difficult problems in smaller cpu times than those required for the BNC method.
Ph. D.

Negli ultimi anni la popolazione residente nella regione Emilia-Romagna sta andando incontro ad un progressivo invecchiamento, con un conseguente aumento della domanda di servizi sempre più efficaci. Al tempo stesso, però, a causa della crisi, è stato necessario porre particolare attenzione all’utilizzo efficiente delle risorse. Uno dei tentativi di bilanciare entrambi questi obiettivi è Gastropack, ovvero un nuovo paradigma di presa in carico congiunta, fra curante e specialista, del paziente con bisogno di cura gastroenterologico, creato all’interno dell’AUSL di Bologna dal Dott. Vincenzo Cennamo. Tale sistema, che nasce allo scopo di risolvere le criticità insite in quello basato su CUP, si fonda su tre principi operativi: presa in carico condivisa fra curante e specialista, con progettazione del percorso di cura; mancanza di prenotazione a CUP; molteplicità di prestazioni durante un singolo accesso. Il progetto pilota di Gastropack è stato lanciato nel Distretto bolognese di Porretta-Vergato il 4 maggio 2016, ma il sistema sarà presto esteso ad altre zone del capoluogo. In quest’ottica è stato necessario condurre un processo di Analytics, in modo da fare una valutazione completa del nuovo paradigma diagnostico. L'analisi si è articolata in tre parti: una prima reportistica sui risultati ottenuti; una seconda analisi di processo attraverso l’utilizzo del Process Mining; infine lo sviluppo di un modello di programmazione lineare intera volto all’assegnamento dei pazienti alle strutture dei nuovi comuni, coinvolti nel progetto. Tutto ciò a dimostrazione dell’importanza, per il futuro, della costruzione di una sanità impostata sul percorso del paziente, piuttosto che sulle precedenti unità funzionali scollegate, in modo da raggiungere quegli obiettivi necessari di efficienza ed efficacia.

A key challenge for manufacturing companies is to store parts in an efficient way atthe lowest cost possible. As the demand of differentiated products increases, togetherwith the fact that old products are not phased out at the same pace, the need of usingstorage space as dynamically as possible becomes vital.Scania’s engine assembly manufactures engines for various automotive vehicles andmarine & industry applications. The variation in engine range in Scania’s offeringleads to the need of holding a vast, and increasing, assortment of parts in the produc-tion. As a consequence, this puts more pressure on the logistics and furnishing withinthe engine assembly.This master thesis aims to facilitate the process of assigning parts’ storage locationsin the most profitable manner through an optimization model, the Location Model, inExcel VBA. Together with the model, suggestions of work methods are presented.By implementing the Location Model at Scania’s engine assembly, 4,98 % of all keptparts are recommended location changes, while resulting in cost savings, for the chosen30-day period. These location changes result in a cost saving of 6,73 % of the totallogistic costs for the same time period.

Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire
This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem

В роботі побудовано моделі для задачі про оптимальне призначення виконавцям (бібліотекам) робіт (сканування книг) за наявності обмежень на ресурси виконавців (час реєстрації для виконання робіт, обмежена кількість робіт на день) та обмеженні загального часу. Задача розв’язується з залученням евристичних алгоритмів, що застосовні для задач великого розміру. Побудовані алгоритми, що ґрунтуються на принципі оптимальності з динамічного програмування, та ітераційних послідовностях перестановок робіт з сортуванням. Наводяться результати програмної реалізації.
В роботі побудовано моделі для задачі про оптимальне призначення виконавцям (бібліотекам) робіт (сканування книг) за наявності обмежень на ресурси виконавців (час реєстрації для виконання робіт, обмежена кількість робіт на день) та обмеженні загального часу. Задача розв’язується з залученням евристичних алгоритмів, що застосовні для задач великого розміру. Побудовані алгоритми, що ґрунтуються на принципі оптимальності з динамічного програмування, та ітераційних послідовностях перестановок робіт з сортуванням. Наводяться результати програмної реалізації.

碩士
國立高雄第一科技大學
運籌管理所
95
The manufacturing industry has to utilize resources in order to lower costs while meeting market demand, and then improve the competitive advantage. Under the environment of production of many product categories, the paper considers that the management must to consider the consumptive condition of equipment available hours、material demand and auxiliary resources. So the distribution of producible resources and whole benefit has closely relationship. The management hopes to balance the main resources during the long-term application, and reduces the mechanics wastage to keep optimal production capacity. The paper applies resource leveling/smoothing problem and lot splitting to define a MRGAP mathematical programming model, and to establish the algorithm which to calculate simply. The permutation of Equipments and product apply in accordance with resource supply and demand, and constraints of multi-resources limitation to assign. Let Equipment which has more resources products order which has more resources demand is a top priority. The consumptive condition of all resources can balance, and avoid resources uses not enough or stocks too much during the long-term application. This research uses different problem example to experiment. When solving the large-scale problem, the algorithm has absolute advantage in solve time even if it has the difference with the optimal solution. The quality of single assignment for algorithm is not the first purpose. To assign many times during the long- term plan still obtain perfect result. The research also conducts a 10-years simulation based on the Fleet Scheduling Problem. The simulation result shows that our algorithm not only meets the product order demand（mission requirements）consistently but also effectively controls the available equipment（flight） hours and the auxiliary resources（airframe degradation）throughout the time span. It will increase assignable flexibility, and the reduction of the maintain costs to meet the longer economical life.

碩士
明志科技大學
工業管理研究所
97
The Generalized Assignment Problem (GAP) combines limited resource capacity and multi-dimensional knapsack problems to construct a combinatorial optimization problem; and it has extensive application in the areas of resource scheduling, factory selection, vehicle routing problem, etc. Capacity utilization has been used as an important indicator for effective allocation of limited resources to ensure that the total cost of all possible combinations can be minimized. The GAP assumes that each job is assign to one and only one agent (machine), but each agent may simultaneously perform multiple jobs, and each agent has its own capacity limitations. The capacity and cost of each agent vary according to the type of job performed. Since the GAP is classified as NP-complete, the solving time needed for a GAP would expand exponentially as the problem expanding its scope. This study developed a hybrid genetic heuristic algorithm to solve the GAP within a reasonable number of iterations to find a near-optimal solution but with significant savings in computation time. To avoid blind random search within a vast solution space, the solution space is prescreened by applying the select smallest capacity method to obtain an initial feasible solutions. Most of the traditional genetic algorithm significantly changes the value of the fitness function of mating chromosomes when using the one-point crossover operator, this study developed an improved mating-type single-point rule that incorporates heuristic algorithm which would rapidly satisfy the fitness function. The developed algorithm is tested on different sizes of randomly generated problems, and the results show that the solution would achieve convergence within a reasonable number of generations.

Deux approches principales existent pour évaluer la robustesse des codes génétiques et des séquences de codage. L'approche statistique est basée sur des estimations empiriques de probabilité calculées à partir d'échantillons aléatoires de permutations représentant les affectations d'acides aminés aux codons, alors que l'approche basée sur l'optimisation repose sur le pourcentage d’optimisation, généralement calculé en utilisant des métaheuristiques. Nous proposons une méthode basée sur les deux premiers moments de la distribution des valeurs de robustesse pour tous les codes génétiques possibles. En se basant sur une instance polynomiale du Problème d'Affectation Quadratique, nous proposons un algorithme vorace exact pour trouver la valeur minimale de la robustesse génomique. Pour réduire le nombre d'opérations de calcul des scores et de la borne supérieure de Cantelli, nous avons développé des méthodes basées sur la structure de voisinage du code génétique et sur la comparaison par paires des codes génétiques, entre autres. Pour calculer la robustesse des codes génétiques naturels et des génomes procaryotes, nous avons choisi 23 codes génétiques naturels, 235 propriétés d'acides aminés, ainsi que 324 procaryotes thermophiles et 418 procaryotes non thermophiles. Parmi nos résultats, nous avons constaté que bien que le code génétique standard soit plus robuste que la plupart des codes génétiques, certains codes génétiques mitochondriaux et nucléaires sont plus robustes que le code standard aux troisièmes et premières positions des codons, respectivement. Nous avons observé que l'utilisation des codons synonymes tend à être fortement optimisée pour amortir l'impact des changements d'une seule base, principalement chez les procaryotes thermophiles.
There are two main approaches to assess the robustness of genetic codes and coding sequences. The statistical approach is based on empirical estimates of probabilities computed from random samples of permutations representing assignments of amino acids to codons, whereas, the optimization-based approach relies on the optimization percentage frequently computed by using metaheuristics. We propose a method based on the first two moments of the distribution of robustness values for all possible genetic codes. Based on a polynomially solvable instance of the Quadratic Assignment Problem, we propose also an exact greedy algorithm to find the minimum value of the genome robustness. To reduce the number of operations for computing the scores and Cantelli’s upper bound, we developed methods based on the genetic code neighborhood structure and pairwise comparisons between genetic codes, among others. For assessing the robustness of natural genetic codes and genomes, we have chosen 23 natural genetic codes, 235 amino acid properties, as well as 324 thermophilic and 418 non-thermophilic prokaryotes. Among our results, we found that although the standard genetic code is more robust than most genetic codes, some mitochondrial and nuclear genetic codes are more robust than the standard code at the third and first codon positions, respectively. We also observed that the synonymous codon usage tends to be highly optimized to buffer the impact of single-base changes, mainly, in thermophilic prokaryotes.