In the Department of Pathology and Laboratory Medicine, at the beginning of each month, the clinical managers use expert knowledge to assign pathologists to expected daily specimens based on the criteria of workload restrictions, clinical sub-specialties, and availability. Since the size of the pathologists’ assignment problem is large, finding a feasible assignment manually is a very time-consuming process that takes a number of iterations over a number of days to complete. Moreover, every time there is a need to make a revision, a new assignment needs to be developed taking into account all the above criteria. The goal of this research is to develop an optimization model and a decision support tool that will help with monthly staffing of pathologists based on the criteria outlined above. The developed model is rooted in the classical operations research assignment problem and it is extended to account for the following requirements: each pathologist should be assigned to a similar specimen type throughout a week; for a given pathologist, there should be a rotation of the specimen types between the weeks; and the clinical managers’ preferences in terms of assigning a particular specimen type to a particular pathologist on a specific day need to be considered. A monthly assignment model covering 36 pathologists and 26 specimen types was solved using IBM ILOG CPLEX Optimization Studio. It is embedded in a decision support tool that helps clinical managers to make staffing decisions. The decision support tool has been validated using data from The Ottawa Hospital (TOH).

In this report we compare three different assignment algorithms in how they can be used to assign a set of drones to get to a set of goal locations in an as resource efficient way as possible. An experiment is set up to compare how these algorithms perform in a somewhat realistic simulated environment. The Robot Operating system (ROS) is used to create the experimental environment. We found that by introducing a threshold for the Hungarian algorithm we could reduce the total time it takes to complete the problem while only sightly increasing total distance traversed by the drones.

Thesis (M.S.)--West Virginia University, 2002. / Title from document title page. Document formatted into pages; contains xi, 87 p. : ill. Includes abstract. Includes bibliographical references (p. 84-87).

One of the most popular and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of a graph is an assignment of integers to the vertices of a graph as before with the restriction that the integers must come from specific lists of available colors at each vertex. For a physical application of this problem, consider a wireless network. Due to hardware restrictions, each radio has a limited set of frequencies through which it can communicate, and radios within a certain distance of each other cannot operate on the same frequency without interfering. We model this problem as a graph by representing the wireless radios by vertices and assigning a list to each vertex according to its available frequencies. We then seek a coloring of the graph from these lists. In this thesis, we give an overview of the last thirty years of research in list colorings. We begin with an introduction of the list coloring problem, as defined by Erdös, Rubin, and Taylor in [6]. We continue with a study of variations of the problem, including cases when all the lists have the same length and cases when we allow different lengths. We will briefly mention edge colorings and overview some restricted list colors such as game colorings and L(p, q)-labelings before concluding with a list of open questions. / Master of Science

In this thesis, we defined a new assignment problem and named it as the artillery target assignment problem(ATAP). The artillery target assignment problem is about assigning artillery weapons to targets at different time instances while optimizing some objectives. Since decisions at a time instance may affect decisions at other time instances, solving this assignment problem is harder than the classical assignment problem. For constructing a solution approach, we defined a base case and some variations of the problem which reflects subproblems of the main problem. These sub-problems are investigated for possible solutions. For two of these sub-problems, genetic algorithm solutions with customized representations and genetic operators are developed. Experiments of these solutions and related results are presented in this thesis.

The study of Stochastic Local Search (SLS) algorithms is becoming more pivotal these days, due to their vast number of applications in decision making. Prior to the implementation of algorithmic knowledge for decision making, many decisions were made based on manual calculation, on the fly, or even based on guts feeling. Nowadays, such an approach is more rarely seen, especially when the decisions that need to be made are high-risk, cost intensive, or time-consuming. The increasingly often used SLS algorithms are one of the options available to assist the decision making process these days.The work discussed in this thesis concerns the study of SLS algorithms for solving the Quadratic Assignment Problem (QAP), a prominent combinatorial optimization problem, which until today is very hard to solve. Our interest is to study the behavior and performance of SLS algorithms for solving QAP instances of different characteristics, such as size, sparsity, and structure. In this study, we have also proposed new variants of SLS algorithms, inspired by existing, well-performing SLS algorithms for solving the QAP. The new variants of SLS algorithms are then further extended for solving the bi-objective QAP (bQAP).One main focus in this study is to see how the performance of algorithms scales with instance size. We have considered instances that are much larger than the ones usually used in the studies of algorithms for solving the QAP. By understanding how the algorithms perform when the instance size changes, we might be able to solve other problems effectively by considering the similarity in their characteristics to the ones of the QAP, or by seeing common trends in the relative performance of the various available SLS methods. For single objective QAP instances we found that the structure and size of instances do have a significant impact on the performance of SLS algorithms. For example, comparisons between Tabu Search (TS) and Simulated Annealing (SA) on instances with randomly generated matrices show that the overall performance of TS is better than SA, irrespective the size of instances considered. The results on a class of structured instances however show that TS performs well on small-sized instances, while on the larger ones, SA shows better results. In another experiment, Hierarchical Iterated Local Search (HILS) has shown very good results compared to several Iterated Local Search (ILS) variants. This experiment was done on a class of structured instances of size from 100 to 500. An extensive experiment on a class of structured instances of size 30 to 300 using tuned parameter settings shows that population based algorithms perform very well on most of the instance classes considered. SA however, shows very good performance especially on large-sized instances with low sparsity level. For the bQAP, the correlation between the flow matrices does have a strong effect that determines the performance of algorithms for solving them. Hybrid Simulated Annealing (HSA) clearly outperforms Hybrid Iterative Improvement (HII). When compared to Multi Objective Ant Colony Optimization (MOACO) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), HSA shows very good performance, where HSA outperforms MOACO and SPEA2, especially on instances of large size, thus, offering a better scaling behavior. Based the results obtained in this study, it is possible to come up with a general idea on the suitability of SLS algorithms for solving instances with a certain characteristic. Given an unknown QAP instance, one can guess the most suitable algorithm for solving it depending on the type, size, and sparsity of the instance, while for a bQAP instance the most suitable algorithm can be guessed based on its size and correlation between the flow matrices. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

This thesis is focused on the topic of assignment problems. The theoretical part presents a summary of the most important previously published findings on linear and quadratic assignment problem. The basic formulations of both problems are introduced, as well as the outline of some methods developed for their solution. Finally both problems are illustrated by practical applications that have appeared in the literature. The practical part gives insight into the issue of assignment of transport orders to drivers in a company and proposes a suitable model that speeds up the process of distributing the orders. The transfers conducted by the company start at the airport and terminate in a hotel in the city centre of Prague or vice versa. When proposing order schedules for the drivers, it is necessary to take into account not only the time of the transfers, but additionally the capacity and the category of the vehicle.

MSc(Eng),Faculty of Engineering and the Built Environment, University of the Witwatersrand, 2010 / This dissertation presents two important results: a novel algorithm that approximately solves the optimal assignment problem as well as a novel method of projecting matrices into the doubly stochastic polytope while preserving the optimal assignment. The optimal assignment problem is a classical combinatorial optimisation problem that has fuelled extensive research in the last century. The problem is concerned with a matching or assignment of elements in one set to those in another set in an optimal manner. It finds typical application in logistical optimisation such as the matching of operators and machines but there are numerous other applications. In this document a process of iterative weighted normalization applied to the benefit matrix associated with the Assignment problem is considered. This process is derived from the application of the Computational Ecology Model to the assignment problem and referred to as the OACE (Optimal Assignment by Computational Ecology) algorithm. This simple process of iterative weighted normalisation converges towards a matrix that is easily converted to a permutation matrix corresponding to the optimal assignment or an assignment close to optimality. The document also considers a method of projecting a matrix into the doubly stochastic polytope while preserving the optimal assignment. Various methods of projecting square matrices into the doubly stochastic polytope exist but none that preserve the assignment. This novel result could prove instrumental in solving assignment problems and promises applications in other optimisation algorithms similar to those that Sinkhorn’s algorithm finds.

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.

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).